java - 二叉树的后序遍历

Question

我正在学习编写二叉树的树遍历。到目前为止，我已经从网上的许多教程中提出了这一点。但是，当我尝试进行任何遍历时，我会陷入无限循环。我哪里错了？

class Node {
int value;
String name;

Node lchild = null;
Node rchild = null;

Node(int key, String name) {
    this.value = key;
    this.name = name;
    }
}

public class genTrees {

Node root;

public void addNode(int key, String s) {
    Node newnode = new Node(key, s);
    if (root == null) {
        System.out.println("Added Root");
        root = newnode;
    } else {
        Node focusNode = root;
        Node parent;
        while (true) {
            parent = focusNode;
            if (key <= focusNode.value) {
                focusNode = focusNode.lchild;
                if (focusNode == null) {
                    System.out.println("Added on Left" + key);
                    parent.lchild = newnode;
                    return; // All done
                }
            }
            if (key > focusNode.value) {
                focusNode = focusNode.rchild;
                if (focusNode == null) {
                    System.out.println("Added on Right" + key);
                    parent.rchild = newnode;
                    return;
                }
            }
        }
    }
}

void inOrder(Node n) {
    while (n != null) {
        inOrder(n.lchild);
        System.out.println(n);
        inOrder(n.rchild);
    }
}

谢谢！

Answer 1

以下循环：

while (n != null) {
    inOrder(n.lchild);
    System.out.println(n);
    inOrder(n.rchild);
}

如果 . 将永远运行n == null。并将在每次迭代中继续调用递归方法。也许，您应该将其更改为：

if (n != null) {
    inOrder(n.lchild);
    System.out.println(n);
    inOrder(n.rchild);
}