我最近完成了为我正在进行的项目实现二进制搜索树 . 它进展顺利,我学到了很多东西 . 但是,现在我需要实现一个常规的二进制树...由于某种原因我难以理解 .
我正在寻找一种方法来做我的InsertNode函数..
通常在BST中,您只需检查数据<root然后向左插入,反之亦然 . 但是,在普通的二进制树中,它只是从左到右填充,一次一个级别 .
任何人都可以帮我实现一个函数,只是从左到右添加一个新的节点没有特定的顺序?
这是我为BST插入的:
void Insert(Node *& root, int data)
{
if(root == nullptr)
{
Node * NN = new Node;
root = NN;
}
else
{
if(data < root->data)
{
Insert(root->left, data);
}
else
{
Insert(root->right, data);
}
}
}
5 回答
我拿了bknopper代码,修改了一下并翻译成了C语言 . 正如他所说,令人惊讶的是,这并没有很好的记录 .
这是节点结构和插入函数:
你这样称呼它:
inserta(&root, val);
作为指向节点结构的指针,并指定要插入的整数值 .
希望它可以帮到某人 .
Javascript implementation (copy-paste ready for your web console):
ES6实现(带有class关键字的更新的javscript语法)
伪经典模式实现
如果你知道这意味着什么,你应该尝试使用递归方法,如x = new(x) . 这样,您就不必担心根节点 . 我要为你写一些伪代码:
我做了一个关于在C中实现BST的教程,here
对代码进行一些修改后,我希望这有助于:
因此,此函数返回更新的BST的根节点 .
我知道这是前一段时间发布的一个问题,但我仍想分享我对它的看法 .
我会做什么(因为这确实没有很好地记录)是使用广度优先搜索(使用队列)并将孩子插入我遇到的第一个空 . 这将确保您的树在进入另一个级别之前首先填充级别 . 使用正确数量的节点,它将始终完整 .
我没有用c做过那么多,所以为了确保它是正确的我用Java做了,但你明白了: