精华内容
下载资源
问答
  • 二叉排序树插入算法

    2021-06-20 22:27:49
    首先执行查找算法,找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。 注意:新插入的结点总是叶子结点。 ...

    首先执行查找算法,找出被插结点的父亲结点。
    判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。
    若二叉树为空。则首先单独生成根结点。
    注意:新插入的结点总是叶子结点。

    展开全文
  • struct Node { int value; Node *left; Node *right; Node(int value) : value(value), left(NULL), right(NULL) {} }; void Insert(Node *&root, int number) { if (root == NULL) ... }
    struct Node
    {
        int value;
        Node *left;
        Node *right;
        Node(int value) : value(value), left(NULL), right(NULL) {}
    };
    
    void Insert(Node *&root, int number)
    {
        if (root == NULL)
        {
            root = new Node(number);
            return;
        }
    
        Node *temp = root;
        //因为要修改该结点的孩子结点,所以要使用双重指针指向孩子结点对应的内存
        Node **child = nullptr; 
        Node *node = new Node(number);
        while (1)
        {
            if (number == temp->value)
                return;
            child = number < temp->value ? &temp->left : &temp->right;
            if (*child == NULL)
            {
                *child = node;
                //这里不能用child = &node;
                //child中存储的是孩子结点指针存放的内存地址,*child才是存放具体下一个结点的地址
                return;
            }
            else
            {
                temp = *child;
            }
        }
    }
    

    示意图
    在这里插入图片描述


    如有错误请指正

    展开全文
  • 二叉排序树 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树 性质:左子树<根<右子树。(比较的是值)。 中序遍历结果是有序的。 示例图 (图来自小甲鱼学习视频) ...

    二叉排序树

    二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树
    性质:左子树<根<右子树。(比较的是值)。
    中序遍历结果是有序的。

    示例图

    在这里插入图片描述
    (图来自小甲鱼学习视频)

    插入操作

    1:若二叉树为空,首先单独生成根节点。
    2:插入值与根值比较,若前者小插入到左子树当中。若前者大,插入到右子树当中。
    代码:

    void insert(BiTree* tree, int value)//创建树
    {
        BiTNode* node=(BiTNode*)malloc(sizeof(BiTNode));//创建一个节点
        node->data = value;
        node->left = NULL;
        node->right = NULL;
        if (tree->root == NULL)//判断树是不是空树
        {
            tree->root = node;
        }
        else {//不是空树
            BiTNode* temp = tree->root;//从树根开始
            while (temp != NULL)
            {
                if (value < temp->data)//小于就进左儿子
                {
                    if (temp->left == NULL)
                    {
                        temp->left = node;
                        return;
                    }
                    else {//继续判断
                        temp = temp->left;
                    }
                }
                else {//否则进右儿子
     
                    if (temp->right == NULL)
                    {
                        temp->right = node;
                        return;
                    }
                    else {//继续判断
                        temp = temp->right;
                    }
                }
            }
        }
        return;
    }
    

    查找操作

    1:若查找值等于根节点值,查找成功。
    2:若小于根节点值,递归查左子树。
    3:若大于根节点值,递归查右子树。
    4:若子树为空,查找不成功。
    代码:

    // 递归查找二叉排序树T中是否存在key
    // 指针F指向T的双亲,其初始值调用值为NULL
    // 若查找成功,则指针P指向该数据元素结点,并返回TRUE
    // 否则指针P指向查找路径上访问的最后一个结点,并返回FALSE
    Status SearchBST(BiTNode* T,int key,BiTNode *f,BiTNode *p)
    {
        if(!T)//查找不成功
        {
            p = f;
            return false;
        }
        else if (key == T->data)//查找成功
        {
            p = T;
            return true;
        }
        else if(key <T->data)
        {
            return SearchBST(T->left,key,T,p);//在左子树上继续查找
        }
        else
        {
            return SearchBST(T->right,key,T,p);//在右子树上继续查找
        }
    }
    

    删除操作

    1:若删除结点右子树为空,将左子树接上去就行了。
    2:若删除结点左子树为空,将右子树接上去就行了。
    3:若删除结点左右子树都不为空。
    这里选择,用直接前驱(中序遍历)替换删除结点,然后删除直接前驱结点。
    删除时,为保证二叉排序树性质不变,需要作出判断。若删除结点左子树是一颗斜树,则将直接前驱的左子树接上已经变换的删除结点上。若删除结点左子树中包含包含右子树,则将直接前驱结点的左子树接到直接前驱结点父节点右子树上。
    代码:

    //删除结点
    Status DeleteBST(BiTNode* T,int key)
    {
        if(T == NULL)
        {
            printf("该树为空,不能删除。");
            return false;
        }
        else
        {
            if(key == T->data)
            {
                return Delete(T);
            }
            else if(key < T->data)
            {
                return DeleteBST(T->left,key);
            }
            else
            {
                return DeleteBST(T->right,key);
            }
        }
    }
    
    Status Delete(BiTNode* p)
    {
        BiTNode* q;
        BiTNode* s;
        if(p->right == NULL)
        {
            //右子树为空的时候,将左子树接上去就行了。
            q = p;
            p = p->left;
            free(q);
        }
        else if(p->left == NULL)
        {
            //左子树为空的时候,将右子树接上去就行了。
            q = p;
            p = p->right;
            free(q);
        }
        else
        {
            //直接前驱data替换要删除结点data
            //直接前驱的左子树接到原直接前驱那里
            q = p;
            s = p->left;
            while(s->right)
            {
                //通过迭代,找出,s子树的最大值,即最右子树。
                q = s;
                s = s->right;
            }
    
            p->data = s->data;
            if(q != p)
            {
                //若删除结点左子树是一颗斜树。
                q->right = s->left;
            }
            else
            {
                //若删除结点左子树中包含包含右子树,则将直接前驱结点的左子树接到直接前驱结点父节点右子树上。
                q->left = s->left;  
            }
            free(s);
        }
        return true;
    }
    
    

    测试结果

    在这里插入图片描述

    完整代码

    /* BST:Binary Sort Tree二叉排序树  */
    /* 二叉排序树的插入,查找,删除  */
    
    
    /*测试例子: 
    *请先输入树的结点个数:12
    *请先输入树的结点数值:70 67 46 105 100 99 104 103 115 110 108 112
    *中序遍历结果:46 67 70 99 100 103 104 105 108 110 112 115
    *请先输入要查找的数值:70
    *查找成功!
    
    *请先输入要删除的数值:105
    *删除成功!
    *中序遍历结果:46 67 70 99 100 103 104 108 110 112 115 请按任意键继续. . .
     */
    #include<stdio.h>
    #include<stdlib.h>
    typedef int ElemType;
    
    #define Status bool
    
    //树的结点
    typedef struct BiTNode
    {
        ElemType data;
        struct  BiTNode *left,*right;
    }BiTNode;
    
    //声明树根
    typedef struct 
    {
       BiTNode* root;
    }BiTree;
    
    
    Status Delete(BiTNode* p);//声明一下
    
    //构建二叉树,插入
    void insert(BiTree* tree, int value)//创建树
    {
        BiTNode* node=(BiTNode*)malloc(sizeof(BiTNode));//创建一个节点
        node->data = value;
        node->left = NULL;
        node->right = NULL;
        if (tree->root == NULL)//判断树是不是空树
        {
            tree->root = node;
        }
        else {//不是空树
            BiTNode* temp = tree->root;//从树根开始
            while (temp != NULL)
            {
                if (value < temp->data)//小于就进左儿子
                {
                    if (temp->left == NULL)
                    {
                        temp->left = node;
                        return;
                    }
                    else {//继续判断
                        temp = temp->left;
                    }
                }
                else {//否则进右儿子
     
                    if (temp->right == NULL)
                    {
                        temp->right = node;
                        return;
                    }
                    else {//继续判断
                        temp = temp->right;
                    }
                }
            }
        }
        return;
    }
    
    
    
    
    // 递归查找二叉排序树T中是否存在key
    // 指针F指向T的双亲,其初始值调用值为NULL
    // 若查找成功,则指针P指向该数据元素结点,并返回TRUE
    // 否则指针P指向查找路径上访问的最后一个结点,并返回FALSE
    Status SearchBST(BiTNode* T,int key,BiTNode *f,BiTNode *p)
    {
        if(!T)//查找不成功
        {
            p = f;
            return false;
        }
        else if (key == T->data)//查找成功
        {
            p = T;
            return true;
        }
        else if(key <T->data)
        {
            return SearchBST(T->left,key,T,p);//在左子树上继续查找
        }
        else
        {
            return SearchBST(T->right,key,T,p);//在右子树上继续查找
        }
    }
    
    void inorder(BiTNode* node)//树的中序遍历
    {
        if (node != NULL)
        {
            inorder(node->left);
            printf("%d ",node->data);
            inorder(node->right);
        }
    }
    
    // bool SearchBST(BiTNode* T,int key)
    // {
    //     if(T == NULL)//查找不成功
    //     {
    //         return false;
    //     }
    //     else if (key == T->data)//查找成功
    //     {
    //         return true;
    //     }
    //     else if(key <T->data)
    //     {
    //         return SearchBST(T->left,key);//在左子树上继续查找
    //     }
    //     else
    //     {
    //         return SearchBST(T->right,key);//在右子树上继续查找
    //     }
    // }
    
    
    
    //删除结点
    Status DeleteBST(BiTNode* T,int key)
    {
        if(T == NULL)
        {
            printf("该树为空,不能删除。");
            return false;
        }
        else
        {
            if(key == T->data)
            {
                return Delete(T);
            }
            else if(key < T->data)
            {
                return DeleteBST(T->left,key);
            }
            else
            {
                return DeleteBST(T->right,key);
            }
        }
    }
    
    Status Delete(BiTNode* p)
    {
        BiTNode* q;
        BiTNode* s;
        if(p->right == NULL)
        {
            //右子树为空的时候,将左子树接上去就行了。
            q = p;
            p = p->left;
            free(q);
        }
        else if(p->left == NULL)
        {
            //左子树为空的时候,将右子树接上去就行了。
            q = p;
            p = p->right;
            free(q);
        }
        else
        {
            //直接前驱data替换要删除结点data
            //直接前驱的左子树接到原直接前驱那里
            q = p;
            s = p->left;
            while(s->right)
            {
                //通过迭代,找出,s子树的最大值,即最右子树。
                q = s;
                s = s->right;
            }
    
            p->data = s->data;
            if(q != p)
            {
                //若删除结点左子树是一颗斜树。
                q->right = s->left;
            }
            else
            {
                //若删除结点左子树中包含包含右子树,则将直接前驱结点的左子树接到直接前驱结点父节点右子树上。
                q->left = s->left;  
            }
            free(s);
        }
        return true;
    }
    
    int main()
    {
    
        BiTree tree;
        tree.root = NULL;//创建一个空树
        int n,key;
        bool flag,flag2;
    
        BiTNode *f,*p;
        printf("请先输入树的结点个数:");
        scanf("%d",&n);
        printf("请先输入树的结点数值:");
        for(int i=0;i<n;i++)//输入n个数并创建这个树
        {
            int temp;
            scanf("%d",&temp);
            insert(&tree,temp);
        }
        printf("中序遍历结果:");
        inorder(tree.root);//中序遍历
    
        printf("\n请先输入要查找的数值:");
        scanf("%d",&key);
        flag = SearchBST(tree.root,key,f,p);
        // flag = SearchBST(tree.root,key);
        if(flag == true)
        {
            printf("查找成功!\n");
        }
        else
        {
            printf("查找失败!\n");
        }
      
    
        printf("\n请先输入要删除的数值:");
        scanf("%d",&key);
        flag2 = DeleteBST(tree.root,key);
        if(flag == true)
        {
            printf("删除成功!\n");
        }
        else
        {
            printf("删除失败!\n");
        }
    
        printf("中序遍历结果:");
        inorder(tree.root);//中序遍历
    
        system("pause");
        return 0;
    }
    
    
    
    
    
    展开全文
  • 二叉排序树建立(插入)出现相同值的处理 什么是二叉排序树(二叉搜索树) 二叉排序树(二叉搜索树)(Binary Sort Tree)或者是一颗空树;或者是具有下列性质的二叉树: (1)若左子树不为空,则左子树上所有结点的值...

    二叉排序树建立(插入)出现相同值的处理
    什么是二叉排序树(二叉搜索树)
    二叉排序树(二叉搜索树)(Binary Sort Tree)或者是一颗空树;或者是具有下列性质的二叉树:
    (1)若左子树不为空,则左子树上所有结点的值均小于它的根节点的值
    (2)若右子树不为空,则右子树上所有结点的值均大于它的根节点的值
    (3)左右子树自己也是二叉排序树

    下面问题:

    依序列(54,25,36,47,36,88,11,86,60),建立二叉排序树。

    其中出现了36,47,36这一片段,出现了两个相同的值该如何处理呢?
    在查找资料后得到:

    “二叉树是一种动态查找表。特点是,树的结构不是一次生成的,而是在查找过程中,当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点,并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。”

    所以根据上面所得,第二个36在树中存在,所以在建立时不需要再次插入。
    所以需要去掉一个值为36的结点,得到的二叉排序树如下(蓝色为建立顺序)

    展开全文
  • 已结贴√问题点数:5回复次数:4 二叉排序树算法 插入好像不成功~输入格式第一行:准备建树的结点个数n第二行:输入n个整数,用空格分隔第三行:输入待查找的关键字第四行:输入待查找的关键字第五行:输入待插入的...
  • 二叉排序树又称二叉查找树,它是一种对排序和查找都有用的特殊二叉树。 二叉排序树的定义: 二叉排序树或者是一颗空树,或者具有下列性质的二叉树: (1)、若它的左子树不空,则左子树上所有结点的值均小于它的根...
  • /*** 二叉排序树(又称二叉查找树)* (1)能够是一颗空树* (2)若左子树不空,则左子树上全部的结点的值均小于她的根节点的值* (3)若右子树不空,则右子树上全部的结点的值均大于她的根节点的值* (4)左、右子树也分别为...
  • 非递归实现三、二叉排序树插入四、二叉排序树的删除 参考博文:《二叉排序树的查找、插入、删除》 一、定义 二叉排序树(BST)(二叉查找树)或者是一棵空树,或者是具有下列特性的二叉树: 1)若左子树非空,则左子树...
  • 文章目录二叉排序树二叉排序树-定义二叉排序树-查找二叉排序树-插入二叉排序树-建立二叉排序树-遍历二叉排序树-删除二叉排序树-性能分析 二叉排序树-定义 ​ 空树或者是具有如下特性的二叉树被称为二叉
  • (数据结构)二叉排序树插入、删除

    千次阅读 2021-11-26 15:20:40
    合适的一个节点代替它,根据二叉排序树的特点,可以找P的左子树中最大 的或者右子树中最小的,这里我们讲讲前者。 假设一个二叉排序树如图: 我们要删除节点47,执行玩第50行时P,q,s分别指向47,47,35 跳出while循环...
  • //二叉排序树插入新节点 int BST_Insert(BiTree& T, ElemType x) { //这里引用指针T,不然本函数需返回指针 if (T == NULL) { //新建节点 T = (BiTree)malloc(sizeof(BTNode)); T->data = x; T->lchild = T->...
  • 一、二叉排序树(二叉查找树)的概念 (1)若左子树非空,则左子树上所有结点的值均小于根节点的值 (2)若右子树非空,则右子树上所有结点的值均大于根节点的值 (3)左右子树分别也是一棵二叉排序树 tip:可以...
  • 二叉排序树(二叉搜索树)的算法实现 二叉排序树有以下五个特征: ...以下是二叉排序树的构造,插入结点,遍历(中序)的代码部分。 #include <iostream> #include <string.h> using namespace s
  • 二叉排序树(查找、结点增加、删除) 定义 或是空树 或具有下列性质: 若左子树不为空,则左子树上所有结点的值均小于根结点的值 若右子树不为空,则右子树上所有结点的值均大于根结点的值 左右子树本身也是一...
  • 二叉排序树

    2021-08-02 18:21:39
    二叉排序树查找非递归递归插入二叉排序树的构造中序遍历删除完整测试代码测试样例 查找 非递归 左子树结点值 < 根节点值 < 右子树结点值 若树非空,目标值与根节点的值比较,相等则查找成功 若小于根节点,则...
  • 今天学习到二叉排序树,课本上提到了二叉排序树的非递归实现,我写了下 // // Created by gxj on 2021/4/19. // #include <stdio.h> #include <stdlib.h> #include <string.h> typedef int ...
  • if(node->valuevalue){ //左结点为空就插入左结点,否则往左走 if(this->left==nullptr){ this->left=node; }else{ this->left->add(node); } }else{ //右节点为空,直接放入插入结点 if(this->right==nullptr){ ...
  • 1、二叉排序树(Binary Sort Tree)性质: 或是一颗空树,或是具有如下性质的二叉树: (1) 若它的左子树不空,则 左子树 上所有结点的值 均小于 它的根结点的值; (2) 若它的右子树不空,则 右子树 上所有结点的值 ...
  • 二叉排序树的定义和性质二叉排序树又称二叉排序树。它或者是一个空树,或者是一个具有下列性质的二叉树:若它的左子树不空,则左子树上所有节点的值均小于它的根结构的值若它的右子树不空,则右子树上所有结点的值均...
  • 二叉排序树插入删除

    2021-06-20 22:27:17
    与次优二叉树相对,二叉排序树是一种动态树表。其特点是:树的结构通常不是一次生成的,而是在查找过程中,当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点,并且是查找不...
  • 二叉排序树 1.1 二叉排序树的定义 中序遍历有序的二叉树为二叉排序树(简称BST) 定义一个二叉树: struct TreeNode { int val;...2.1.1 二叉排序树插入操作 每次插入操作必然都是往树的叶结点插入
  • 针对前面需求所给出的数组 arr = {7,3,10,12,5,1,9} 对应的二叉排序树如下图所示: 插入一个结点 2 后的图示: 3. 二叉排序树的创建和遍历 3.1. 思路分析 插入新的结点的时候与调用插入方法的结点进行比较 如果小于...
  • 《数据结构》实验报告班级:姓名:学号:E-mail:日期:◎实验题目: 建立二叉排序树,并中序遍历输出,输入一个关键字进行查找。 ◎实验目的:熟悉并掌握二叉排序树的建立及遍历输出以及非递归查找。◎实验内容:输入一...
  • 二叉排序树插入和删除(C语言)

    万次阅读 2021-04-21 20:30:38
    } } void InsertBinTree(BinTreeNode **T,int elem)//插入二叉排序树结点(因为要从上往下一步一步找,所以一次只能插一个,不能递归) { if(*T==NULL) { *T=(BinTreeNode*)malloc(sizeof(BinTreeNode));...
  • 文章目录二叉排序树的定义二叉排序树的查找二叉排序树插入二叉排序树的构造二叉排序树的删除 二叉排序树的定义 二叉排序树(Binary Sort Tree, BST),也称二叉查找树。 二叉排序树或者是一棵空树,或者是一棵...
  • 1、 二叉排序树的定义 2、 二叉排序树的查找:二叉排序树的查找时从根结点开始,沿某一个分支逐层向下进行比较的过程。若相等,则查找成功;若不等,则当根节点的关键字大于给定关键字值时,在根结点的左子树中查找...
  • 在分析treemap时,分析到了红黑树,而红黑树是由二叉排序树变体产生的,因此学习二叉排序树是常用树的基础;本篇文章主要分析二叉排序树的构建 ,及原理解析,遍历方式。
  • 什么是二叉排序树(BST) 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。在一般情况下,查询效率比链表结构要高。 要求:对于二叉树中的任何一个非叶子结点,要求左子结点...
  • 二叉排序树的创建遍历及删除 输出结果: 中序遍历:1 2 4 5 6 7 9 10 14 15 17 18 19 20 25 30 35 40 层序遍历:20 14 25 5 15 35 4 10 17 30 40 2 6 19 1 9 18 7 Treeheight = 7 请输入待寻找的数字:5 找到了5. 请...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,434
精华内容 20,173
关键字:

二叉排序树的插入