java - 无法计算出预序遍历

Question

 public void traverse(ListItem root) {
        //preorder traversal - going to left childs first
        ListItem focusNode;
        ListItem parentNode;
        if (root == null) {
            System.out.println("Empty tree");
        } else {
            if (root.leftLink != null) {
                System.out.println(root.getValue());
                parentNode = root;
                while (parentNode.leftLink != null) {
                    focusNode = parentNode.leftLink;
                    System.out.println(focusNode.getValue());
                    parentNode = focusNode.leftLink;
                }
            }
        }
    }

这就是我到目前为止所得到的。我认为这能够打印出树左侧的所有节点，但我还没有找到一种方法，因为缺乏更好的术语跳回先前的条目并测试是否有左侧节点(如果没有)转到正确的节点。

Answer 1

使用递归你可以做这样的事情:

public void traverse(ListItem node) {
    if (node== null) {
        System.out.println("Empty tree");
    } else {
        if (node.leftLink != null) {
            traverse( node.leftLink );
        }
        if (node.rightLink != null) {
            traverse( node.rightLink );
        }

        System.out.println( node.getValue());               
    }
}

这将检查左子树是否存在，并递归调用左子树(子树)的方法，然后对右子树执行相同的操作。打印完所有子节点后，将打印节点自己的值。

示例:

假设下面的树

    A
   / \
  B   C
 / \   \
D   E    F

调用traverse(A)将产生以下输出:

D
E
B
F
C
A