数据结构——再赏“树“,关于搜索二叉树(BST树)和平衡二叉树(AVL树)那点事儿~(1)

简介: 数据结构——再赏“树“,关于搜索二叉树(BST树)和平衡二叉树(AVL树)那点事儿~(1)

二叉搜索树(BST树)


什么是二叉搜索树


二叉搜索树(BST,Binary Search Tree),也称二叉排序树或二叉查找树


二叉搜索树:一棵二叉树,可以为空;如果不为空,满足以下性质:


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

举个栗子:

二叉搜索树:

微信图片_20221017163132.jpg


非二叉搜索树:微信图片_20221017163141.png

二叉搜索树的特别函数


Find函数


从二叉搜索树BST中查找元素X,返回其所在结点的地址


实现逻辑:


⏩从根节点开始,树为空,返回NULL


⏩若树不为空,将根节点和传入的数据X进行比较:


  1. 若X小于根节点的键值,进入左子树继续搜索
  2. 若X大于根节点的键值,进入右子树继续搜索
  3. 若两者比较结果相等,搜索完成,返回此结点的指针

常言道:一图值前言

微信图片_20221017163147.jpg

所需结构体

//为了简化后文重复代码的书写,用typedef对指向树结构的指针取两个别名位置类型的"Position"和搜索二叉树类型的"SearchTree"
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
struct TreeNode{
    ElementType Element;
    SearchTree Left;
    SearchTree Right;
};

具体实现的参考代码

Position Find(ElementType X, SearchTree T)
{
    if(T == NULL) return NULL;
    if(X < T->Element) return Find(X,T->Left);//带着X进入左子树
    if(X > T->Element) return Find(X,T->Right);//带着X进入右子树
    else return T;//搜索成功
}

Find函数的性质挖掘


从二叉搜索树的特性来看,它的左子树总是比根节点的键值小,所以最小值只能出现在左子树,一个结点它下面没有比它小的左子树了,那它就是最小的了。最大值同理,右子树总是比根节点的键值大,一个结点它下面没有比它大的右子树了,那它就是最大的了。


FindMin函数


从二叉搜索树BST中查找并返回最小元素所在结点的地址。


具体实现的参考代码


Position FindMin(SearchTree T)
{
    if(T == NULL) return NULL;
    else
    {
        if(T->Left == NULL) return T;//搜索成功,没有比它小的了
        else return FindMin(T->Left);//继续到左子树的左子树中查找
    }
}

FindMax函数


从二叉搜索树BST中查找并返回最大元素所在结点的地址。


具体实现的参考代码


上述两份代码都是使用的递归的方式实现的。这里变一下~。用函数迭代法

//函数迭代法
Position FindMax(SearchTree T)
{
    if(T == NULL) return NULL;
    while(T->Right) return T->Right;
    return T;
}

闲谈一刻


递归常常被称为—— “一种优雅的解决问题的方式”。对于它的态度,分为了三种阵营,恨之入骨,爱不释手,恨了又爱


因为递归写代码可以让方案更整洁喔。比如在dfs中,只用写好当前这一步的逻辑,下一步则递归进去,实现和当前这步一样的操作就好。但是递归在性能上是不及循环的喔~!


每个递归函数都有两部分,基线条件和递归条件。递归条件是指函数自己调用自己,而基线条件(⊙o⊙)…,则是指函数不再自己调用自己了,可以获得其他值回溯回去了,从而避免形成无限循环。典型例子:斐波那契数列


Insert函数


因为二叉搜索树独特的性质,导致了插入一个数据以后,仍然要保证左子树比根节点小,右子树比根节点大。所以对于插入而言,最主要的确认插入的位置

微信图片_20221017163633.jpg

具体实现的参考代码


SearchTree Insert(ElementType X,SearchTree T)
{
    //如果树为空,生成并返回一个有一个结点的二叉搜索树
    if(T ==NULL)
    {
        T = malloc(sizeof(struct TreeNode));
        T->Element = X;
        T->Left = T->Right = NULL;
    }else
    {
     if(X < T->Element) T->Left = Insert(X,T->Left);//如果比根节点小,就向左子树的方向进行插入
     else 
     if(X > T->Element) T->Right = Insert(X,T->Right);//如果比根节点大,就向右子树的方向进行插入
    }
     return T;
}

Delete函数(难点)


情况一


要删除的是叶结点:直接删除,并再修改其父结点指针—置为NULL

微信图片_20221017163802.jpg

情况二


要删除的结点只有一个孩子结点: 将其父结点的指针指向要删除结点的孩子结点

微信图片_20221017163815.jpg

情况三


要删除的结点有左、右两棵子树: 用另一结点替代被删除结点:用 右子树的最小元素 或者 左子树的最大元素

微信图片_20221017163815.jpg

具体实现的参考代码


SearchTree Delete(ElementType X, SearchTree T)
{
  Position TmpCell;
  //找到要删除的位置在哪里 
  if(T == NULL) printf("Element not found\n");
  else
  if(X < T->Element) T->Left = Delete(X,T->Left);
  else
  if(X > T->Element) T->Right = Delete(X,T->Right) ;
  //具体的开始执行删除操作了 
  //两个儿子都存在的情况
  else
  if(T->Left && T->Right)  //两个孩子
  {
    TmpCell = FindMin(T->Right) ;//找到右子树的最小值或者左子树的最大值来代替那个要被删除的节点
    T->Element = TmpCell->Element;
    //删除右边那个被抽上去替代的节点 
    T->Right =  Delete(T->Element,T->Right);
  }else //一个或者没有孩子 
  {
    TmpCell = T;
    if(T->Left == NULL) T = T->Right;//结合上图,只有一个孩子的时候,是让这孩子挪到要删除结点的位置,也就实现了 将其父结点的指针指向要删除结点的孩子结点
}
    else if(T->Right == NULL) T = T->Left;
    free(TmpCell);
  }
  return T;
}
相关文章
|
20天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
14 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
20天前
|
存储 算法 数据管理
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
这篇文章通过需求分析、代码实现和测试验证,详细介绍了二叉排序树的创建、遍历和删除操作,以及二叉平衡树(AVL)的自平衡特性和单旋转操作,旨在提高树结构在数据管理中的效率和性能。
19 0
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
|
17天前
|
Java C++
【数据结构】探索红黑树的奥秘:自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理,介绍其五大原则,并通过图解和代码示例展示其内部机制。同时,对比红黑树与二叉查找树的性能差异,帮助读者更好地理解这两种数据结构的特点和应用场景。
22 0
|
19天前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
20天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
1天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
20天前
初步认识栈和队列
初步认识栈和队列
47 10
|
14天前
数据结构(栈与列队)
数据结构(栈与列队)
15 1
|
20天前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
34 3