二叉搜索树的建立

￡神魔★判官ぃ 2024-04-17 18:57 91阅读 0赞

建立二叉搜索树的过程，就是将一个一个数插入数集的过程，只不过数集的结构是一棵二叉树。红黑树就是一棵平衡二叉搜索树。

插入一个数，开始将该数与树中的结点比较，从根节点开始。**如果根结点就是空的，直接将该数放在根的位置；否则，与根节点的值相比较，比其小则该数肯定插在根节点的左子树上，比其大则该数肯定插在根节点的右子树上**。

以以上算法为依据写出插入函数的代码如下（color代表节点的颜色，**true**为**黑**，**false**为**红**）：

//建树插入函数
    node* Insert(node *root,int v,bool color)
    {
        if(root==NULL)
        {
            root=new node;
            root->val=v;
            root->isBlack=color;
            root->left=NULL;
            root->right=NULL;
        }
        else
        {
            if(v<root->val)
            {
                //继续往左子树插
                root->left=Insert(root->left,v,color);
            }
            else if(v>root->val)
            {
                //继续往右子树插
                root->right=Insert(root->right,v,color);
            }
        }
        return root;
    }

调用Insert函数部分的代码（**正数**表示**黑节点**，**负数**表示**红节点**）：

for(i=0;i<n;i++)
    {
        scanf("%d",&temp);
        bool isBlack=true;
        if(temp<0)
        {
            temp=-temp;
            isBlack=false;
        }
        root=Insert(root,temp,isBlack);
    }
    //建树完成

**欢迎大家关注/订阅我的微信公众号Code Art Online，我会在我的公众号分享个人见闻，发现生活趣味；这里不仅有0和1，还有是诗和远方↓↓↓**

![20200227123106884.jpg][]

[20200227123106884.jpg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/e058b123a6754a289170f6966b8e4a53.jpg