无法 insert/print 出整个二叉搜索树

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

除非插入第一项，否则不会将 link 存储到树中的新节点。当您 return 时，您的局部变量 temp 和 tree 超出范围。您必须将 link 存储到树的现有结构中的新节点，作为新根或作为新节点的 löeft 或 right link 之一节点的父节点。

一种方法是：

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;
}

节点指针prev存储当前节点的父节点。如果为空，则树最初为空，您必须在根部插入。 whence标志告诉你是否通过left或right分支到达当前节点，让你知道这里要更新。

（还要注意分配是如何仅在我们确定要插入的节点之后才发生的。否则，return过早会泄漏新分配的节点。）

这个解决方案引入了两个额外的变量。您可以通过使用指向节点指针的指针来减少它：首先，该指针 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;
}

您仍然必须重新调整节点。这段代码更短，因为它不必处理插入第一个节点的特殊情况，也不必在插入新节点时显式区分叶分支和右分支。

如果您愿意更改函数签名，可以进行一项改进：将指针传递给头指针而不是 returning。这样，调用函数中的头指针将通过 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) 的冗余消失了，您不会不小心忘记通过省略存储 return 值来更新根指针。

无法 insert/print 出整个二叉搜索树

Unable to insert/print out the whole Binary Search Tree

c

binary-tree

binary-search-tree

data-structures