插入二叉树

问题描述 投票:0回答:1

嗨,我正在阅读Binary Tree中的值插入,但我发现使用Java理解树的递归遍历有困难。这是代码:

// Java program to insert element in binary tree 
import java.util.LinkedList; 
import java.util.Queue; 
public class GFG { 

/* A binary tree node has key, pointer to  
left child and a pointer to right child */
static class Node { 
    int key; 
    Node left, right; 

    // constructor 
    Node(int key){ 
        this.key = key; 
        left = null; 
        right = null; 
    } 
} 
static Node root; 
static Node temp = root; 

/* Inorder traversal of a binary tree*/
static void inorder(Node temp) 
{ 
    if (temp == null) 
        return; 

    inorder(temp.left); 
    System.out.print(temp.key+" "); 
    inorder(temp.right); 
} 

/*function to insert element in binary tree */
static void insert(Node temp, int key) 
{ 
    Queue<Node> q = new LinkedList<Node>(); 
    q.add(temp); 

    // Do level order traversal until we find 
    // an empty place.  
    while (!q.isEmpty()) { 
        temp = q.peek(); 
        q.remove(); 

        if (temp.left == null) { 
            temp.left = new Node(key); 
            break; 
        } else
            q.add(temp.left); 

        if (temp.right == null) { 
            temp.right = new Node(key); 
            break; 
        } else
            q.add(temp.right); 
    } 
} 

// Driver code 
public static void main(String args[]) 
{ 
    root = new Node(10); 
    root.left = new Node(11); 
    root.left.left = new Node(7); 
    root.right = new Node(9); 
    root.right.left = new Node(15); 
    root.right.right = new Node(8); 

    System.out.print( "Inorder traversal before insertion:"); 
    inorder(root); 

    int key = 12; 
    insert(root, key); 

    System.out.print("\nInorder traversal after insertion:"); 
    inorder(root); 
} 
}

有人可以解释这个inorder()方法是如何工作的吗?对我来说,它应该永远不会终止,因为它将继续一次又一次地传递空值,并且如果循环中的返回语句将只循环出循环而不是整个方法。

java recursion data-structures binary-tree insertion
1个回答
3
投票

inorder被称为recursively

在任何给定的方法调用中,我们首先在树的左边节点中传递,然后在第二个节点中传递。然后,这些调用将调用左节点或右节点的方法 - 如果节点为null,则它会提前返回。树不是无限的 - 所以在某一点上,节点的左右节点必须为空,此时该方法返回早期并且不继续。因此,递归在某些时候被安全地破坏了。

if也不是一个循环 - 它是一个条件语句。在if中调用return从整个方法返回并且不仅仅是if语句。你必须与之混淆的是break

© www.soinside.com 2019 - 2024. All rights reserved.