在二叉树中插入元素

Question

在二叉树中插入元素

ctreebinary-treebinary-search-tree

10

在网上尝试了很多探索，但没有得到任何帮助，无论哪里都是像将节点添加到二叉查找树中。

问题：请求添加节点到二叉树的算法和代码片段（或指向正确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 < (*root)->data)
    {
        insert( key, &(*root)->left );
    }
    else if(key > (*root)->data)
    {
        insert( key, &(*root)->right );
    }
}

- Raa

如果你在讨论二叉搜索树，并且想做一些插入操作，也许这个链接可以帮到你：http://en.wikipedia.org/wiki/Binary_search_tree#Insertion - CLearner

@AbdullahShoaib 请告诉我二叉搜索树的正确顺序。 - Raa

顺便提一下：我认为问题中的示例看起来像是二叉搜索树。 - wildplasser

1

@wildplasser：是的，这是二叉搜索树，我正在寻找普通二叉树...但是找不到相应的算法。 - Raa

@wildplasser：谢谢，但我不知道如何修改我的代码以在二叉树中插入节点。 - Raa

显示剩余4条评论

5个回答

2

队列数据结构可以用于向二叉树插入元素，因为在二叉树中节点的顺序未被保持，所以我们将在找到任何空节点时立即插入节点。使用队列，我们将按层次遍历方式遍历二叉树。

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;
     }
}

- user905

0

我发表这篇回答是因为我没有足够的声望来发表评论。除了bagelboy之外，所有其他人都误解了树的类型，将其视为二叉搜索树或完全二叉树。问题很简单，只是二叉树，而Bagelboy的答案看起来是正确的。

- takesavy

0

由于我无法评论，所以我写下了这篇文章。
上述的二叉树插入函数答案是错误的。
假设按顺序传递0、1、2、3、4、5给插入函数，
它生成的树如下：

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

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

- codeFreak

1

您说得对，回到这个答案时，我已经在我的学位中进一步了1.5年，我看到了我的错误：）。我会尝试解决这个问题。谢谢。 - sbru

1

好的，我已经做了一些修改，你现在的想法是什么？ - sbru

@bagelboy：我仍然对你的代码有问题。我会直接在你的帖子下面评论。 - Ravi

0

由于我也遇到了同样的问题，我在网上想出了以下解决方案：

您可以使用队列来存储当前节点，就像我们在层序遍历中所做的那样，然后逐层插入节点。

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

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

- anonymous

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sbru · Accepted Answer

二叉树和二叉搜索树的区别在于，虽然它们都有限制，每个节点最多只能有两个子节点，但是二叉搜索树还必须满足左子节点的值小于或等于当前节点，右子节点的值大于或等于当前节点。这就是为什么它被称为“搜索”树，因为所有的内容都按数字顺序排列，搜索的运行时间为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;
        }
    }
}