插入二叉树

Question

您好，我正在阅读二叉树中的值插入，但我发现很难理解使用 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() 方法是如何工作的？根据我的说法，它永远不应该终止，因为它会一次又一次地传递空值，并且 if 循环中的 return 语句只会循环出循环而不是整个方法。

Answer 1

inorder 正在调用 recursively。

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

此外 if 不是循环 - 它是条件语句。在整个方法的 if returns 中调用 return 并且不只是超出 if 语句。你一定把它和 break.

混淆了

插入二叉树

Insertion Binary Tree

java

recursion

data-structures

binary-tree

insertion