java - 二叉树遍历不起作用

Question

我正在尝试创建一棵二叉树并遍历它。
问题是，CreateBT() 正确地创建了树，但 TreeTraverse(BTNode node) 只打印树及其 2 个子节点的 root我使用哪种遍历。

我什至使用(在代码中注释)检查了节点及其子节点

//btn is binaryTreeNode
System.out.println("btn : "+btn.getData()+" - right : "+btn.getRight()+" - left "+btn.getLeft());

输出符合预期:

btn : 0 - right : Data_S.BTNode@1ba0281 - left Data_S.BTNode@fa6824
btn : 1 - right : Data_S.BTNode@1cb1d37 - left Data_S.BTNode@1eb424b
btn : 2 - right : Data_S.BTNode@4d8040 - left Data_S.BTNode@1f14fd
btn : 3 - right : null - left Data_S.BTNode@9b04ac
btn : 4 - right : null - left null
btn : 5 - right : null - left null
btn : 6 - right : null - left null

我真的很难找到错误，有人可以帮助我吗？

代码

void CreateBT()
    {
        int nodeCnt = 0;
        BTNode leftN, rightN;
        while(!BTq.isQueueEmpty())
        {
            BTNode btn = new BTNode(BTq.deQueue());

            if(root == null)
                root = btn;

            int leftNodeIndex = getLeftIndex(nodeCnt);
            int rightNodeIndex = getRightIndex(nodeCnt++);

            if(leftNodeIndex >= BTq.queueArray.length)
                btn.setLeft(null);
            else
            {
                leftN = new BTNode(BTq.queueArray[leftNodeIndex]);
                btn.setLeft(leftN);
            }


            if(rightNodeIndex >= BTq.queueArray.length)
                btn.setRight(null);
            else
            {
                    rightN = new BTNode(BTq.queueArray[rightNodeIndex]);
                    btn.setRight(rightN);
            }

        //System.out.println("btn : "+btn.getData()+" - right : "+btn.getRight()+" - left "+btn.getLeft());
        }

        TreeTraverse(root);
    }


public void TreeTraverse(BTNode node)
    {
        if(node == null)
            return;
            TreeTraverse(node.left);
    System.out.println(node.getData());
    TreeTraverse(node.right);

    }

输出

1
0
2

输入数组数据

0 1 2 3 4 5 6 7

Answer 1

当您设置节点的子级时，如代码中所示

leftN = new BTNode(BTq.queueArray[leftNodeIndex]);
btn.setLeft(leftN);

您创建一个节点，并在下一个 while 循环中通过
创建另一个节点BTNode btn = new BTNode(BTq.deQueue());

这两个节点不同，但它们应该是相同的，因此您可以将 root 的子节点设置为 right，但在下一个循环中，您将子节点添加到您创建的节点中，即 btn 而不是您在上一个循环中创建的 lefttN。

更新:
如果打印节点及其子节点，例如 System.out.println("btn : "+btn+"- right : "+btn.getRight()+"- left "+btn.getLeft()); 你可能会发现 root 的左节点与你在第二行中打印的内容不同。

问题是您创建了一个节点 a(0) 例如，并设置了它的子节点 b(1) 和 c(2)，并在下一个循环中创建一个节点 d(1) 并设置其子节点 .... 而 b 是 a< 的左子节点 和 d 也应该是 a 的左 child ，但是 b 和 d 不同，您设置了 d 的 children 而不是 b，因此 b 没有子级，并且当您调用TreeTraverse ，会停在第二层。

您需要做的是设置 b 的子级而不是 d