C语言 在二叉树中插入一个元素
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16292786/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Inserting an element in Binary Tree
提问by Raa
Tried exploring a lot over the net, but could get any help, Everywhere its like adding a node to the Binary Search tree.
尝试通过网络进行大量探索，但可以得到任何帮助，无处不在就像向二叉搜索树添加节点一样。
Question: Requesting for algorithm and code snippet for adding a node to the Binary tree. ( or point me to correct URL )
问题：请求用于向二叉树添加节点的算法和代码片段。（或指向我正确的 URL）
Assumption: As per my understanding, Binary Treeand Binary Search Treeis different? Correct me if I am wrong.
假设：根据我的理解，二叉树和二叉搜索树是不同的？如果我错了，请纠正我。
( request: if you are writing your code snippet please use proper variable name, that helps in understanding )
（要求：如果您正在编写代码片段，请使用正确的变量名称，这有助于理解）
Eg: Binary Tree
例如：二叉树
5 7 3 x1 x2 x3
5 7 3 x1 x2 x3
5
7 3
x1 x2 x3
Binary Search Tree 5 7 3 2 4 6
二叉搜索树 5 7 3 2 4 6
5
3 7
2 4 6
insert(int key, struct node **root)
{
if( NULL == *root )`
{
*root = (struct node*) malloc( sizeof( struct node ) );`
(*root)->data = key;
(*root)->left = NULL;
(*root)->right = NULL;
}
else if(key < (*root)->data)
{
insert( key, &(*root)->left );
}
else if(key > (*root)->data)
{
insert( key, &(*root)->right );
}
}
回答by sbru
The difference between a Binary Tree and a Binary Search Tree is that though they both have restrictions that each node can have at most 2 child nodes, a Binary Search Tree (BST) also must have its left child be of equal or lesser value and the its right child must be of greater or equal value. This is why it is called a "Search" tree because everything is ordered numerically and it has an O(logn) run time for searching.
二叉树和二叉搜索树的区别在于，虽然它们都有每个节点最多只能有 2 个子节点的限制，但二叉搜索树 (BST) 也必须让它的左子节点等于或小于它的右孩子必须具有更大或相等的价值。这就是为什么它被称为“搜索”树的原因，因为一切都是按数字排序的，并且它的搜索运行时间为 O(logn)。
Because there isn't the requirement of being a BST, a Binary Tree can be stored in a vector (array). As you insert into the vector you build the Binary Tree in level-order fashion. The code is below:
因为没有成为 BST 的要求，所以二叉树可以存储在向量（数组）中。当您插入向量时，您以级别顺序方式构建二叉树。代码如下：
// typedef the node struct to NODE
// nodeVector similar to STL's vector class
insert(int key, NODE** nodeVector)
{
NODE *newNode = (NODE*) malloc( sizeof( NODE ) );
newNode->data = key;
newNode->left = NULL;
newNode->right = NULL;
// add newNode to end of vector
int size = nodeVector->size();
nodeVector->push_back(newNode);
// if newNode is not root node
if(nodeVector->size() > 1)
{
// set parent's child values
Node* parent = (size/2)-1; // take advantage of integer division instead of using floor()
if (parent->left == NULL)
{
parent->left = newNode;
}
else
{
parent->right = newNode;
}
}
}
回答by user905
A Queue data structure can be used for inserting element in to a Binary Tree, since in Binary Tree the order of nodes is not maintained so we will insert the node as soon as we find any null. Using Queue we will be traversing the Binary Tree in Level Order Traversal.
队列数据结构可用于将元素插入到二叉树中，因为在二叉树中不维护节点的顺序，因此我们将在发现任何空值时立即插入节点。使用 Queue 我们将在 Level Order Traversal 中遍历二叉树。
struct Treenode* temp;
Q = CreateQueue();
EnQueue(Q,root);
while(!IsEmptyQueue(Q))
{
temp = DeQueue(Q);
if(temp->left)
EnQueue(Q,temp->left);
else
{
temp->left=newNode;
DeleteQueue(Q);
return;
}
if(temp->right)
EnQueue(Q,temp->right);
else
{
temp->right=newNode;
DeleteQueue(Q);
return;
}
}
回答by codeFreak
Since, I cannot comment I am writing this.
The above answer for binary tree insert function is wrong.
Suppose for 0, 1, 2 , 3, 4 , 5 passed in sequence to insert function,
its generating tree like
因为，我不能评论我正在写这篇文章。
上面二叉树插入函数的答案是错误的。
假设 0, 1, 2 , 3, 4 , 5 依次传递给插入函数，
其生成树如
0
/
1
\
2
/
3
\
4
/
5`<br/>
of which inorder traversal will be 1 3 5 4 2 0
while answer should be
其中中序遍历将是 1 3 5 4 2 0
而答案应该是
0
/ \
1 2
/ \ /
3 4 5
of which inorder traversal will be 3 1 4 0 5 2.
其中中序遍历为 3 1 4 0 5 2。
回答by anonymous
Since I also face the same problem, I came up with following solution over the net :-
由于我也面临同样的问题，因此我通过网络提出了以下解决方案：-
You can use a queue to store the current node where we want to place the new node as we do in level order traversal and then we insert the nodes level by level.
您可以使用队列来存储我们想要放置新节点的当前节点，就像我们在级别顺序遍历中所做的那样，然后我们逐级插入节点。
Following link might help you :-
以下链接可能对您有所帮助：-
http://www.geeksforgeeks.org/linked-complete-binary-tree-its-creation/
http://www.geeksforgeeks.org/linked-complete-binary-tree-its-creation/
回答by takesavy
I am posting this as answer because I dont have the necessary reputation to post a comment. Except for bagelboy all others have misunderstood the tree as either Binary Search Tree or Complete Binary Tree. The question is simple Binary Tree and Bagelboy's answer looks correct.
我将此作为答案发布，因为我没有发表评论所需的声誉。除了 bagelboy 之外，所有其他人都将这棵树误解为二叉搜索树或完全二叉树。问题是简单的二叉树，Bagelboy 的答案看起来是正确的。
