二叉搜索树的建立

￡神魔★判官ぃ 2024-04-17 18:57 73阅读 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

发表评论取消回复

表情：

评论列表（有 0 条评论，73人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉搜索树的建立

立二叉搜索树的过程，就是将一个一个数插入数集的过程，只不过数集的结构是一棵二叉树。红黑树就是一棵平衡二叉搜索树。插入一个数，开始将该数与树中的结点比较，从根节点开始。...

￡神魔★判官ぃ/ 2024年04月17日 18:57/ 0 赞/ 74 阅读

相关二叉搜索树、平衡二叉树

一、二叉搜索树这里我们不用太多书面化的语言来定义，笔者认为在讨论数据结构、算法相关的内容时用太多书面化、学术化的语言是一种让人很烦的事情。咬文嚼字，不便于读者理解。

阳光穿透心脏的1/2处/ 2023年10月18日 22:26/ 0 赞/ 53 阅读

相关二叉树的建立

文章目录中序和后序建立题目（106-中等）思考位置

╰半橙微兮°/ 2022年12月10日 14:35/ 0 赞/ 140 阅读

相关二叉搜索树

在计算机术语中，二叉搜索树又叫二叉查找树、二叉排序树。二叉搜索树（Binary Search Tree）的定义：它或者是一棵空树，或者是具有下列性质的二叉树：若它的

Myth丶恋晨/ 2022年09月30日 06:45/ 0 赞/ 216 阅读

相关二叉搜索树

二叉搜索树的特征定义就是：一个节点的左子节点的关键字值小于这个节点，右子节点的关键字大于或等于这个父节点 package Trees; import java.ut

客官°小女子只卖身不卖艺/ 2022年05月31日 00:50/ 0 赞/ 294 阅读

相关二叉搜索树

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于

ゝ一世哀愁。/ 2022年04月24日 11:20/ 0 赞/ 256 阅读

相关根据数组建立平衡二叉搜索树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉（搜索）树。二分：用有序数组中中间的数生成搜索二叉树的头节点，然后对数组的左右部分

迈不过友情╰/ 2022年04月13日 02:55/ 0 赞/ 188 阅读

相关二叉搜索树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RqaDYy

た入场券/ 2022年03月17日 02:18/ 0 赞/ 288 阅读

相关二叉搜索树

思路二叉排序树，二叉搜索树好像都行，原理应该都懂，比较基础，但要写出来还是有相当大的难度的。查找查找比较简单，基本都是一个while就解决。但查前驱与后继较

短命女/ 2021年12月21日 09:15/ 0 赞/ 292 阅读

相关二叉搜索树

二叉搜索树基本概念二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: 1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

妖狐艹你老母/ 2021年11月22日 07:30/ 0 赞/ 370 阅读