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);
}