c - 在二叉树中插入一个元素

Question

尝试通过网络进行大量探索，但可以得到任何帮助，无处不在，就像在二叉搜索树中添加一个节点。

问题:请求将节点添加到二叉树的算法和代码片段。 (或指向我正确的 URL)

假设:据我了解，Binary Tree 和Binary Search Tree 有什么不同？如果我错了，请纠正我。

(要求:如果您正在编写代码片段，请使用正确的变量名，这有助于理解)

例如:二叉树

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

Answer 1

二叉树和二叉搜索树的区别在于，虽然它们都有每个节点最多可以有 2 个子节点的限制，但二叉搜索树 (BST) 的左子节点也必须等于或小于值及其右 child 必须具有更大或相等的值(value)。这就是它被称为“搜索”树的原因，因为所有内容都按数字排序，并且它的搜索运行时间为 O(logn)。

因为没有BST的要求，二叉树可以存储在 vector (数组)中。当您插入到 vector 中时，您将以级别顺序的方式构建二叉树。代码如下:

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