首页 > 其他分享 >09. 二叉搜索树

09. 二叉搜索树

时间:2023-03-31 19:22:50浏览次数:39  
标签:结点 Right return BST 09 二叉 搜索 else

一、什么是二叉搜索树

  二叉搜索树(Binary Search Tree,BST)也称 二叉排序树二叉查找树二叉搜索树 是一颗特殊的二叉树,它可以为空,如果不为空,满足以下性质:

  1. 非空 左子树 的所有 键值小于其根节点的键值
  2. 非空 右子树 的所有 键值大于其根节点的键值
  3. 左、右子树 都是 二叉搜索树

二、二叉搜索树操作的特别函数

Position Find(ElementType X,BinTree BST);       // 从二叉搜索树BST中查找元素X,返回其所在的结点的地址
Positon FindMin(BinTree BST);                   // 从二叉搜索树BST中查找并返回最小元素所在结点的地址
Postion FindMax(BinTree BST);                   // 从二叉搜索树BST中查找并返回最大元素所在结点的地址
BinTree Insert(ElementType X,BinTree BST);      // 在二叉搜索树BST中插入一个新的结点
BinTree Delete(ElementType X,BinTree BST);      // 在二叉搜索树BST中删除一个结点

【1】、二叉搜索树的查找操作:Find

  • 查找从根节点开始,如果 树为空,返回 NULL
  • 若搜索树非空,则根据 关键字 和 X 进行比较,并进行不同处理:
    • X 小于根节点键值,只需在 左子树 中继续搜索;
    • X 大于根节点键值,只需在 右子树 中继续搜索
    • 若两者笔比较结果是 相等,搜索完成,返回指向此结点的指针
Positon Find(ElementType X,BinTree BST)
{
    if(!BST)                            // 查找失败
    {
        return NULL;
    }

    if(X > BST->Data)
    {
        return Find(X,BST->Right);      // 在右子树中继续查找
    }
    else if(X < BST->Data)
    {
        return Find(X,BST->Left);       // 在左子树中继续查找
    }
    else
    {
        return BST;                     // 查找成功,返回结点的找到结点的地址
    }
}

  由于非递归函数的执行效率高,可将尾递归函数改为迭代函数。

Position IterFind(ElementType X,BinTree BST)
{
    while(BST)
    {
        if(X > BST->Data)
        {
            BST = BST->Right;       // 向右子树移动,继续查找
        }
        else if(X < BST->Data)
        {
            BST = BST->Left;        // 向右子树移动,继续查找
        }
        else
        {
            return BST;             // 查找成功,返回结点的找到结点的地址
        }
    }

    return NULL;                    // 查找失败
}

查找的效率决定于树的高度

【2】、最小元素 一定是在树的 最右分支的端结点 上。

// 查找最小元素的递归函数
Position FindMin(BinTree BST)
{
    if(!BST)                            // 空的二叉搜索树,返回NULL
    {
        return NULL;
    }
    else if(!BST->Left)
    {
        return BST;                     // 找到最左叶节点并返回
    }
    else
    {
        return FinMin(BST->Left);       // 沿做分支继续查找
    }
}

【3】、查找最大元素

  最大元素 一定是在树的 最右分支的端结点 上。

Position FindMax(BinTree BST)
{
    if(BST)
    {
        while(BST->Right)
        {
            BST = BST->Right;       // 沿右分支继续查找,直到最右叶结点
        }
    }

    return BST;
}

【4】、二叉搜索树插入一个新的结点

BinTree Insert(ElementType X,BinTree BST)
{
    // 若原树为空,生成并返回一个一个结点的二叉搜索树
    if(!BST)
    {
        BST = malloc(sizeof(struct TreeNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }
    // 开始找要插入元素的位置
    else
    {
        if(X < BST->Data)
        {
            BST->Left = Insert(X,BST->Left);        // 递归插入左子树
        }
        else if(X > BST->Data)
        {
            BST->Right = Insert(X,BST->Right);      // 递归插入右子树
        }
    }

    return BST;
}

【5】、二叉搜索树的删除

  删除要考虑三种情况:

  • 要删除的是 叶节点直接删除,并在修改其 父节点指针 置为 NULL
  • 要删除的结点 只有一个孩子结点:将其 父节点的指针 指向 要删除结点的 孩子结点
  • 要删除的结点有 左、右两颗子树:用另一个结点替代被删除结点:右子树的最小元素 或者 左子树的最大元素
BinTree Delete(ElementType X,BinTree BST)
{
    Position Tmp;

    if(!BST)
    {
        printf("要删除的元素未找到");
    }
    else if(X < BST->Data)
    {
        BST->Left = Delete(X,BST->Left);                    // 左子树递归删除
    }
    else if(X > BST->Data)
    {
        BST->Right = Delete(X,BST->Right);                  // 右子树递归删除
    }
    else                                                    // 找到要删除的结点
    {
        if(BST->Left && BST->Right)                         // 被删除结点有左右两个子节点
        {
            Tmp = FindMin(BST->Right);                      // 在右子树中找最小的元素填充删除结点
            BST->Data = Tmp->Data;
            BST->Right - Delete(BST->Data,BST->Right);      // 在删除结点的右子中删除最小元素
        }
        else                                                // 被删除结点有一个或无子节点
        {
            Tmp = BST;
            if(!BST->Left)                                  // 有右孩子或无子节点
            {
                BST = BST->Right;
            }
            else if(!BST->Right)                            // 有左孩子或无子节点
            {
                BST = BST->Left;
            }
            free(Tmp);
        }
    }
    return BST;
}

三、判别是否是同一颗二叉搜索树

  给定一个插入序列就可以唯一确定一颗二叉搜索树。然而,一颗给定的二叉搜索树却可以由多种不同的插入序列得到。那我们如何判断两个序列是否对应相同的二叉搜索树呢?

  这里主要有三种方法:第一种方法是 根据两个序列分别建立两个二叉搜索树,再判别树是否一样;

  第二种方法是 先比较第一个整数是否一样,如果一样,则说明对应的根节点一样,然后根据这个根节点,将后面的数分为两对,一对比根节点大,一对比过根节点小,然后用同样的方法依次处理这两对数。

  第三种方法是建一棵树,再判别其它序列是否与该树一致。

3.1、搜索树表示

typedef struct TreeNode *Tree;

struct TreeNode
{
    int v;
    Tree Left,Right;
    // flag=0,表示这个结点没被访问过
    // flag=1,表示这个结点已经被访问过了
    int flag;
};

3.2、读入数据建搜索树T

Tree MakeTree(int N)
{
    Tree T;
    int i,V;

    printf("请输入树的元素:\n");
    scanf("%d",&V);
    T = NewNode(V);
    for(i = 1; i < N; i++)
    {
        scanf("%d",&V);
        T = Insert(T,V);
    }

    return T;
}
Tree NewNode(int V)
{
    Tree T =  (Tree)malloc(sizeof(struct TreeNode));
    T->v = V;
    T->Left = T->Right = NULL;
    T->flag = 0;
    return T;
}
Tree Insert(Tree T,int V)
{
    if(!T)                                          // 如果树为空,则创建根节点
    {
        T = NewNode(V);
    }
    else
    {
        if (V > T->v)                               // 如果要插入的数据大于当前结点的数据,则插入右子树
        {
            T->Right = Insert(T->Right,V);
        }
        else                                        // 如果要插入的数据小于当前结点的数据,则插入左子树
        {
            T->Left = Insert(T->Left,V);
        }
    }

    return T;
}

3.3、判别序列是否与T构成一样的搜索树

  那我们如何判别序列是否与 T 一致呢?我们可以在树 T 中按顺序搜索序列中的每个数,如果每次搜索所经过的结点在前面均出现过,则一致,否则(某次搜索中遇到前面没有出现的结点),则不一致。

int Judge(Tree T,int N)
{
    int i,V;
    // flag=0,代表目前还一致
    // flag=1,代表已经不一致
    int flag = 0;
  
    printf("请输入要比较的序列:\n");
    scanf("%d",&V);
    if(V != T->v)
    {
        flag = 1;
    }
    else
    {
        T->flag = 1;
    }

    for(i = 1; i < N; i++)
    {
        scanf("%d",&V);
        if((!flag) && (!check(T,V)))
        {
            flag = 1;
        }
    }

    if(flag)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}
int check(Tree T,int V)
{
    if(T->flag)                                     // 如果被访问过
    {
        if(V < T->v)                                // 到它的左子树找
        {
            return check(T->Left,V);
        }
        else if(V > T->v)                           // 到它的右子树找
        {
            return check(T->Right,V);
        }
        else                                        // 整数出现两次以上
        {
            return 0;
        }
    }
    else                                            // 如果没被访问过
    {
        if(V == T->v)                               // 正好是该结点
        {
            T->flag = 1;
            return 1;
        }
        else                                        // 以前没见过的结点
        {
            return 0;
        }
    }
}
// 清除T中各节点的flag标记
void ResetT(Tree T)
{
    if(T->Left)
    {
        ResetT(T->Left);
    }
    if(T->Right)
    {
        ResetT(T->Right);
    }
    T->flag = 0;
}
// 释放T的空间
void FreeTree(Tree T)
{
    if(T->Left)
    {
        FreeTree(T->Left);
    }
    if(T->Right)
    {
        FreeTree(T->Right);
    }
    free(T);
}

3.4、测试程序

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int N,L,i;
    Tree T;

    printf("请输入序列中元素的个数:\n");
    scanf("%d",&N);
    T = MakeTree(N);

    printf("请输入要比较的序列的个数:\n");
    scanf("%d",&L);

    for(i = 0; i < L; i++)
    {
        if(Judge(T,N)){
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
        ResetT(T);                  // 清除T中的标志flag
    }
    FreeTree(T);

    return 0;
}

标签:结点,Right,return,BST,09,二叉,搜索,else
From: https://www.cnblogs.com/kurome/p/17277272.html

相关文章

  • LeetCode 94 二叉树的中序遍历
    LeetCode|94.二叉树的中序遍历给定一个二叉树的根节点root,返回它的中序 遍历。示例1:输入:root=[1,null,2,3]输出:[1,3,2]示例2:输入:root=[]输出:[]示例3:输入:root=[1]输出:[1]提示:树中节点数目在范围[0,100]内-100<=Node.val<=100迭代实现:......
  • 0109 标识符
    命名规则要求1、不能以数字、关键字开头2、由数字、字母、下划线、和$组成建议1、小驼峰命名法:​ 只有一个单词时,全部小写;有两个以上单词时,除了第一个单词之外其他单词首字母大写2、大驼峰命名法:​ 只有一个单词时,首字母大写;有多个时,全部单词首字母都大写3、见名知意......
  • 209. 长度最小的子数组
    力扣题目链接给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥target 的长度最小的 连续子数组 [numsl,numsl+1,...,numsr-1,numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。示例1:输入:target=7,nums=[2,3,1,2,4......
  • 机器学习基础09DAY
    分类算法之逻辑回归逻辑回归(LogisticRegression),简称LR。它的特点是能够是我们的特征输入集合转化为0和1这两类的概率。一般来说,回归不用在分类问题上,因为回归是连续型模型,而且受噪声影响比较大。如果非要应用进入,可以使用逻辑回归。了解过线性回归之后再来看逻辑回归可以更好的......
  • 移动搜索到拐点了?
    最近的搜索数据表明,移动搜索广告已经在一个重要的拐点了,可能会在明年发生重大变化。在美国,移动搜索当前的份额大约占了整个搜索广告的6%,是去年的2.7倍。明年年底这个数据可能会达到16%或者22%。移动搜索的份额依然在不断增长,目前还只是保守估计,如果发展再快一点,那么可能会达到22%。......
  • 之子形打印二叉树
    classSolution{public:vector<vector<int>>res;voidbfs(TreeNode*root){queue<TreeNode*>q;q.push(root);intlevel=0;while(q.size()){intsize=q.size();......
  • 不分行从上往下打印二叉树
    classSolution{public:vector<int>res;voidbfs(TreeNode*root){queue<TreeNode*>q;q.push(root);while(q.size()){autop=q.front();q.pop();res.push_back(......
  • Bing全新改版为三栏显示 加入社交搜索
    微软在Bing官网上宣布,将对这个有着三年历史的搜索引擎进行重大改版,新版的搜索结果将以三栏(如下图)的形式显示,分为CoreSearchResults、Snapshot和Sidebar,让搜索结果更加清晰简洁:从左到右依次是网页为主的搜索结果、地图以及评价和其他信息、社交信息。社交信息应该是此次改版的重头......
  • MOD09A1(500 米地表反射率 8 天合成产品)计算水体指数
    MOD09A1(500米地表反射率8天合成产品)https://lpdaac.usgs.gov/products/mod09a1v006/MOD09A1提供了波段1-7的500米分辨率8天合成的数据产品,投影为正弦曲线投影。每一个MOD09A1的像素包含了8天之内最有可能的L2G观测数值,尽量考虑高观测覆盖、低视角、无云及云的阴影以及......
  • 数位DP (记忆化 暴力搜索!!)
    用于:统计数位于数位的相关信息的计数问题, 通常会问在某个区间内,利用减法思维,这样就会减少一个边界的判断此时就会只有一个边界,这个边界利用lim处理,在暴力枚举的时候不要超过lim就行了记忆化搜索的过程,就是一个完全的暴力,不过有记忆化搜索,所以他的时间复杂......