递归遍历二叉树

Question

在涉及递归函数时,我绝望地迷失了.我需要创建一个递归函数来遍历二叉树并在特定值之间插入一个新节点.我需要重新复制我的遍历函数并在我使用它的其他所有函数中修改它吗？有人请评估遍历功能吗？

我认为我的遍历代码没问题.

Node traverse (Node currentNode){
    if (!currentNode.left.equals(null)){
        traverse (currentNode.left);
        return currentNode.left;
    }
    if (!currentNode.right.equals(null)){
        traverse (currentNode.right);
        return currentNode.right;
    }
    return currentNode;
}

Answer 1

当谈到二叉树时,有几种不同类型的遍历可以递归完成.它们按照它们被引用然后访问的顺序编写(L =左子,V =访问该节点,R =右子).

• 有序遍历(LVR)
• 反向顺序遍历(RVL)
• 预订遍历(VLR)
• 后序遍历(LRV)

你的代码似乎正在执行postorder遍历方法,但是你得到了一些混乱的东西.首先,节点是你想要遍历的; 该数据是您要访问的内容.其次,您没有理由以实现此方式的方式返回节点本身.你的代码不允许条件说'我正在寻找这个特定的数据,你有没有Node @ 0xdeadbeef先生？',这可以通过某种额外的搜索参数找到.

学术BST遍历仅打印节点本身.如果您想添加搜索功能,它只需要一个参数,以及对正确节点的额外检查.

这是一个片段:

// Academic

public void traverse (Node root){ // Each child of a tree is a root of its subtree.
    if (root.left != null){
        traverse (root.left);
    }
    System.out.println(root.data);
    if (root.right != null){
        traverse (root.right);
    }
}

// Search with a valid node returned, assuming int

public Node traverse (Node root, int data){ // What data are you looking for again?
    if(root.data == data) {
        return root;
    }
    if (root.left != null && data < root.data) {
        return traverse (root.left, data);
    }
    if (root.right != null && data > root.data) {
        return traverse (root.right, data);
    }
    return null;
}