在二叉树中插入元素

Question

试图通过网络进行大量探索,但可以得到任何帮助,Everywhere就像在Binary Search树中添加一个节点一样.

问题:请求用于将节点添加到二叉树的算法和代码片段.(或指向我更正网址)

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

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

例如:二叉树

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)的左子节点也必须具有相同或更小的值,并且其正确的孩子必须具有更大或相等的价值.这就是为什么它被称为"搜索"树,因为所有内容都是按数字排序的,并且它有一个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;
        }
    }
}