二叉搜索树前序遍历

Question

我有一个关于二叉搜索树的先序遍历的问题。我知道该算法必须是什么样的，它非常简单：

void preOrder(Node node) {
    print(node);

    if (node.left() != null)
        preOrder(node.left());
    if (node.right() != null)
        preOrder(node.right());
}

出于某种原因，我的函数仅打印出根节点的左侧子树，并打印出最低节点两次。我在右侧的一项上运行了 search 方法，它返回 true，所以我认为我的插入工作正常。为什么会发生这种情况？

我的代码如下。公共方法调用私有方法。在私有节点中，前两个 if 语句用于打印连接到该节点的左节点和右节点。最后两个执行实际的递归算法。

public void print() {

    if (root == null)
        System.out.println("Tree is empty");
    else
        print(root);
}


private void print(NodeBST node) {

        printOut(node);

        if (node.left() != null) {
            System.out.print("Left: ");
            printOut(node.left());
        }

        else
            System.out.println("No left");

        if (node.right() != null) {
            System.out.print("Right: ");
            printOut(node.right());
        }

        else
            System.out.println("No right");

        System.out.println("");

        if (node.left() != null) {
            node = node.left();
            print(node);
        }

        if (node.right() != null) {
            node = node.right();
            print(node);
        }
    }

Answer 1

好吧，您遇到的一个错误是您覆盖了第一个 print(node) 之前的行上的 node ，然后立即再次重用修改后的版本。想必您希望在执行 if(node.right() != null) 测试时将 node 设为原始值？

您可以通过在第一个 if 中调用 print(node.left()); 来避免这种情况。

Answer 2

struct node *MakeBst(int preOrder[],int str,int end)
{
    struct node *newnode;
    if(str>end)
        return NULL;
    newnode = malloc(sizeof(node));
    if(!newnode)
        return NULL;
    if(str == end)
        return newnode;
    newnode->data = preOrder[str];
    str++;
    x = search_Index(number>preOrder[str-1]);
    newnode->left = MAkeBst(preOrder,str,x-1);
    newnode->right = MAkeBst(preOrder,x-1,end);
}