我最近完成了为我正在从事的项目实施的二叉搜索树。进展顺利，我学到了很多。但是，现在我需要实现一个常规的二叉树......由于某种原因让我很难过。
我正在寻找一种方法来执行我的 InsertNode 功能..
通常在 BST 中，您只需检查 data < 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);
}
}
}
我知道这是前段时间发布的一个问题，但我仍然想分享我的想法。
我要做的（因为这确实没有很好的记录）是使用广度优先搜索（使用队列）并将孩子插入我遇到的第一个 null 中。这将确保您的树在进入另一个级别之前先填满各个级别。使用正确数量的节点，它将始终是完整的。
我没有用 C++ 做太多工作，所以为了确保它是正确的，我用 Java 做了，但你明白了：
public void insert(Node node) {
if(root == null) {
root = node;
return;
}
/* insert using Breadth-first-search (queue to the rescue!) */
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
while(true) {
Node n = queue.remove();
if(!n.visited) System.out.println(n.data);
n.visited = true;
if(n.left == null) {
n.left = node;
break;
} else {
queue.offer(n.left);
}
if(n.right == null) {
n.right = node;
break;
} else {
queue.offer(n.right);
}
}
}
Javascript 实现（为您的 Web 控制台准备好复制粘贴）：
ES6 实现（带有 class 关键字的较新的 javscript 语法）
class BinaryTree {
constructor(value){
this.root = value;
this.left = null;
this.right = null;
}
insert(value){
var queue = [];
queue.push(this); //push the root
while(true){
var node = queue.pop();
if(node.left === null){
node.left = new BinaryTree(value);
return;
} else {
queue.unshift(node.left)
}
if(node.right === null){
node.right = new BinaryTree(value);
return;
} else {
queue.unshift(node.right)
}
}
}
}
var myBinaryTree = new BinaryTree(5);
myBinaryTree.insert(4);
myBinaryTree.insert(3);
myBinaryTree.insert(2);
myBinaryTree.insert(1);
5
/ \
4 3
/ \ (next insertions here)
2 1
伪经典模式实现
var BinaryTree = function(value){
this.root = value;
this.left = null;
this.right = null;
}
BinaryTree.prototype.insert = function(value){
//same logic as before
}
通过对您的代码进行一些修改，我希望这会有所帮助：
Node * Insert(Node * root, int data)
{
if(root == nullptr)
{
Node * NN = new Node();
root = NN;
root->data = data;
root->left = root ->right = NULL;
}
else
{
if(data < root->data)
{
root->left = Insert(root->left, data);
}
else
{
root->right = Insert(root->right, data);
}
}
return root;
}
因此，该函数返回更新后的 BST 的根节点。
我拿了 bknopper 代码，稍作修改并翻译成 C++。正如他所说，令人惊讶的是，这没有很好的记录。
这是节点结构和插入函数：
struct nodo
{
nodo(): izd(NULL), der(NULL) {};
int val;
struct nodo* izd;
struct nodo* der;
};
void inserta(struct nodo** raiz, int num)
{
if( !(*raiz) )
{
*raiz = new struct nodo;
(*raiz)->val = num;
}
else
{
std::deque<struct nodo*> cola;
cola.push_back( *raiz );
while(true)
{
struct nodo *n = cola.front();
cola.pop_front();
if( !n->izd ) {
n->izd = new struct nodo;
n->izd->val = num;
break;
} else {
cola.push_back(n->izd);
}
if( !n->der ) {
n->der = new struct nodo;
n->der->val = num;
break;
} else {
cola.push_back(n->der);
}
}
}
}
你这样称呼它：
inserta(&root, val);
作为 root 指向节点结构的指针和 val 要插入的整数值。
希望它可以帮助某人。
如果您知道这意味着什么，您应该尝试使用递归方法，例如 x = new (x)。这样，您就不必担心根节点。我将为您编写一些伪代码：
//public function
add(data){
root = add(data, root)
}
//private helper function
Node add(data, currentNode){
if(currentNode = 0)
return new Node(data)
if(data less than currentNode's data)
currentNode.left = add(data, currentNode.left)
if(data more than currentNode's data)
currentNode.right = add(data, currentNode.right)
return currentNode
}
我做了一个关于在 C++ 中实现 BST 的教程，here