在二叉树中插入元素
试图通过网络进行大量探索，但可以得到任何帮助，Everywhere就像在二进制搜索树中添加一个节点一样。
问题：请求用于将节点添加到二叉树的算法和代码片段。 （或指向我更正url）
假设：根据我的理解， 二叉树和二叉搜索树是不同的？ 如果我错了，请纠正我。
（请求：如果您正在编写代码片段，请使用适当的变量名称，这有助于理解）
例如：二叉树
5 7 3 x1 x2 x3
5 7 3 x1 x2 x3 二进制搜索树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 data) { insert( key, &(*root)->left ); } else if(key > (*root)->data) { insert( key, &(*root)->right ); } }
二叉树和二进制搜索树之间的区别在于，尽管它们都具有每个节点最多可以包含2个子节点的限制，但二进制搜索树（BST）的左子节点也必须具有相等或更小的值，并且其正确的孩子必须具有更大或相等的价值。 这就是为什么它被称为“搜索”树，因为所有内容都是按数字排序的，并且它有一个O（logn）运行时间用于搜索。
因为不需要成为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; } } }
队列数据结构可用于将元素插入到二叉树中，因为在二进制树中，节点的顺序不会被维护，因此我们将在找到任何空值时立即插入节点。 使用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; } }
既然如此，我无法评论我写这篇文章。
二元树插入函数的上述答案是错误的。
假设0,1,2,3,4,5顺序通过插入函数，
它的生成树就像
0 / 1 \ 2 / 3 \ 4 / 5`
其中inorder遍历将是1 3 5 4 2 0
而答案应该是
0 / \ 1 2 / \ / 3 4 5
其中inorder遍历将是3 1 4 0 5 2。
既然我也面临同样的问题，我想通过网络提出以下解决方案： –
您可以使用队列来存储我们想要放置新节点的当前节点，就像我们在级别顺序遍历中那样，然后我们逐级插入节点。
以下链接可能会帮助您： –
http://www.geeksforgeeks.org/linked-complete-binary-tree-its-creation/
我发布这个作为答案，因为我没有发表评论的必要声誉。 除了bagelboy之外，所有其他人都误将树误解为二进制搜索树或完整二叉树。 问题是简单的Binary Tree和Bagelboy的答案看起来是正确的。