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

我想用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);
}

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

解决方案:

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

一种方法是

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 告诉你是否已经到达当前节点,通过 leftright 分支,这样你就知道在哪里更新了。

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

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

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) 已经消失了,你不能因为省略存储返回值而意外地忘记更新根指针。

给TA打赏
共{{data.count}}人
人已打赏
未分类

Pyththon--"把枯燥的东西自动化"--while循环

2022-9-21 4:02:29

未分类

在R中比较两个CSV文件的一些条件。

2022-9-21 4:13:16

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索