嗨,我正在阅读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()方法是如何工作的吗?对我来说,它应该永远不会终止,因为它将继续一次又一次地传递空值,并且如果循环中的返回语句将只循环出循环而不是整个方法。
inorder
被称为recursively。
在任何给定的方法调用中,我们首先在树的左边节点中传递,然后在第二个节点中传递。然后,这些调用将调用左节点或右节点的方法 - 如果节点为null,则它会提前返回。树不是无限的 - 所以在某一点上,节点的左右节点必须为空,此时该方法返回早期并且不继续。因此,递归在某些时候被安全地破坏了。
if
也不是一个循环 - 它是一个条件语句。在if中调用return
从整个方法返回并且不仅仅是if语句。你必须与之混淆的是break。