c - 在二叉树中插入元素

Question

尝试在网上进行了很多探索，但可以获得任何帮助，无处不在，就像在二叉搜索树中添加一个节点一样。

问题：请求向二叉树添加节点的算法和代码片段。（或指出我正确的网址）

假设：根据我的理解，二叉树和二叉搜索树是不同的？如果我错了，请纠正我。

（请求：如果您正在编写代码片段，请使用正确的变量名，这有助于理解）

例如：二叉树

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 < (*root)->data)
    {
        insert( key, &(*root)->left );
    }
    else if(key > (*root)->data)
    {
        insert( key, &(*root)->right );
    }
}

score 9 · Accepted Answer

二叉树和二叉搜索树之间的区别在于，尽管它们都有每个节点最多可以有 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;
        }
    }
}

score 2 · Accepted Answer

队列数据结构可用于将元素插入二叉树，因为在二叉树中，节点的顺序是不被维护的，所以我们会在找到任何空值时立即插入节点。使用队列，我们将在 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;
     }
}

score 0 · Accepted Answer

由于我也面临同样的问题，我在网上提出了以下解决方案：-

您可以使用队列来存储我们想要放置新节点的当前节点，就像我们在级别顺序遍历中所做的那样，然后我们逐级插入节点。

以下链接可能会对您有所帮助：-

http://www.geeksforgeeks.org/linked-complete-binary-tree-its-creation/

score 0 · Accepted Answer

因为，我无法评论我正在写这篇文章。
上面对二叉树插入函数的答案是错误的。
假设 0, 1, 2 , 3, 4 , 5 依次传递给 insert 函数，
其生成树形如

其中中序遍历将是 1 3 5 4 2 0
而答案应该是

其中中序遍历将是 3 1 4 0 5 2。

score 0 · Accepted Answer

我将其发布为答案，因为我没有发表评论的必要声誉。除了 bagelboy，所有其他人都将树误解为二叉搜索树或完全二叉树。问题很简单，二叉树和 Bagelboy 的答案看起来是正确的。

c - 在二叉树中插入元素

5 回答 5

Related

Reference