无法插入打印出整个二进制搜索树。

Question

我想用C语言建立自己的二进制搜索树（BST）库。但是，我发现很难插入或打印出整个二进制树。为了详细说明，这是每个二进制节点的结构，其中的 Object 已经被预定义。

struct BinaryNode
{
    Object item;
    BinaryNode *left;
    BinaryNode *right;
};

这是 insert 操作，正是遵循二进制搜索树的属性，如下。的 root 指针是存放二进制搜索树头部的全局变量，而 Newnode() 是创建一个新节点插入到二进制搜索树的函数。

BinaryNode *insert(BinaryNode *tree, Object datain)
{
    if (tree == NULL)
    {
        return Newnode(datain);
    }
    else
    {
        BinaryNode *temp = Newnode(datain);
        root = tree;
        while(tree != NULL)
        {
            if (datain.key < tree->item.key)
                tree = tree->left;
            else if (datain.key > tree->item.key)
                tree = tree->right;
            else
                  break; //Break to insert into the proper place
        }
        tree = temp;
        return root;
    }
}

以下是我的源代码 printTree() 函数，我保证我在这里没有弄错。但是，我还是在这里提供它来澄清我的问题。

oid printTree(BinaryNode *tree)
{
    if (tree == NULL)
        return;
    printTree(root->left);
    printf("(%d - %s)-> ", tree->item.key, tree->item.name);
    printTree(root->right);
}

我的问题：我的检查程序的输出是，它只打印出了树的第一个节点。当我调试我的源代码时，我发现除了第一个插入的节点外，它并没有包括新创建的节点。然而，我确实不知道如何解决这个问题，因为我认为我的程序在逻辑上还是有算法的。

Answer 1

除了当你插入第一项时，你不会在树中存储一个新节点的链接。你的本地变量 temp 和 tree 当你返回时，就会离开范围。你必须在树的现有结构中存储一个指向新节点的链接，可以是新的根节点，也可以是新的 löeft 或 right 新节点的父节点的链接。

一种方法是

BinaryNode *insert(BinaryNode *root, Object datain)
{
    BinaryNode *prev = NULL;
    BinaryNode *curr = root;
    int whence = 0;

    while (curr) {
        if (datain.key == curr->item.key) return root;

        if (datain.key < curr->item.key) {
            curr = curr->left;
            whence = 0;
        } else {
            curr = curr->right;
            whence = 1;
        }
    }

    BinaryNode *temp = Newnode(datain);

    if (prev == NULL) {
        root = temp;
    } else if (whence == 0) {
        prev->left = temp;
    } else {
        prev->right = temp;
    }

    return root;
}

Node指针 prev 存储当前节点的父节点。如果它是空的，那么树的初始值是空的，你必须在根节点插入。标志 whence 告诉你是否已经到达当前节点，通过 left 或 right 分支，这样你就知道在哪里更新了。

(还要注意只有在我们确定了要插入的节点之后，才会发生分配。否则，提前返回会泄露新分配的节点）。)

这个解决方案引入了两个额外的变量。你可以通过使用节点指针来减少。一开始，这个指针 p 指向头部指针，当下降树时，它指向你的来处，要么是 left 或 right 成员的父节点。

BinaryNode *insert(BinaryNode *root, Object datain)
{
    BinaryNode **p = &root;

    while (*p) {
        if (datain.key == (*p)->item.key) return root;

        if (datain.key < (*p)->item.key) {
            p = &(*p)->left;
        } else {
            p = &(*p)->right;
        }
    }

    *p = NewNode(datain);

    return root;
}

你仍然必须重新调整节点。这段代码比较短，因为它不用处理插入第一个节点的特殊情况，而且在插入新节点时也不用明确区分叶子和右枝。

如果你愿意改变函数签名，还有一个改进。传递一个指向头部指针的指针，而不是返回。这样一来，调用函数中的头部指针就会通过 proot:

void insert(BinaryNode **proot, Object datain)
{            
    while (*proot) {
        if (datain.key == (*proot)->item.key) return;

        if (datain.key < (*proot)->item.key) {
            proot = &(*proot)->left;
        } else {
            proot = &(*proot)->right;
        }
    }

    *proot = NewNode(datain);
}

你这样调用这个函数。

BinaryNode *root = NULL;

insert(&root, mydata);

冗余的 root = insert(root, data) 已经消失了，你不能因为省略存储返回值而意外地忘记更新根指针。