【数据结构和算法】树表的查找算法（二叉排序树与平衡二叉树）

2022-11-10 722

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构和算法】树表的查找算法（二叉排序树与平衡二叉树）

二叉排序树

1、二叉排序树查的定义

二叉排序树有称为二叉搜索树，二叉查找树

二叉排序树的定义：

二叉排序树的例子

二叉排序树性质：中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。
二叉排序树结果出现的原因：二叉排序树的左节点的数字比根节点要小，而右节点的数字要比根节点要大。而中序遍历是先左子树，然后再跟，在右子树，所以便得到一个递增的有序序列。

2、二叉排序树查找算法

二叉树的查找

分析：

如上例子中，需要进行对105进行查找，首先105比122小，所以查找根节点的左子树99，然后发现99小于105，所以查找左子树的根节点99的右子树110，但110比105大，再查找110根节点的左子树，发现110的左子树就是105，查找成功。

二叉排序树的存储结构

typedef struct{
  KeyType key;  //关键字项
  InfoType otherInfo; //其他数据域
}ElemType;
typedef struct BSTNode{
  ElemType data;  //数据域
  struct BSTNode *lchild,*rchild; //左右孩子指针
}BSTNode,*BSTree;
BSTree T;    //定义二叉排序树T

算法思路

算法的代码实现

BSTree SearchBST(BSTree T,KeyType key){
  if( !T || key == T->data.key) //如果树为空或者找到了，就返回这个T
  return T;     //为空就返回了NULL，否则返回找到的根节点
  else if(key < T->data.key)  //小于根节点，在左子树中继续查找
  return SearchBST(T->lchild,key);
  else        //大于根节点，在右子树中继续查找
  return SearchBST(T->rchild,key);
}

3、二叉排序树的算法分析

二叉排序树的平均查找长度法分析

（其中，右边的二叉排序树退化成顺序查找法）

（含有n个节点的二叉排序树的平均查找长度和树的形态有关）

二叉排序树的改进：针对树的形态会影响时间的复杂度，如何提高形态不均航的二叉排序树的查找效率？

解决方法：做“平衡化”处理，既尽量让二叉树的形状均衡。（也就是平衡二叉树）

4、二叉排序树的插入与生成

二叉排序树的插入思路

（插入的元素一定在叶节点上）

二叉排序树插入的例子

分析：

以40为例，首先40与根节点45比较，但是小于根节点，所以进入到根节点的左孩子12,；40比左孩子12大，再进入根节点12的右孩子37，此时40比根节点37大而且根节点没有右孩子，所以40就成为了根节点的右孩子。

二叉排序树插入算法

int InsertBST(BSTree T,KeyType key){
  if( !T) {    //如果树为空，说明应该在此空位插入
  T = (BSTree*)malloc(sizeof(BSTree));  //创建一个节点
  T->data.key = key;  //赋值
  .....     //其他操作
  return 0;
  }
  else if( key == T->data.key)
  return -1;      //等于根节点，啥也不做，结束函数
  else if(key < T->data.key )
  InsertBST(T->lchild,key); //小于根节点，递归查找左子树
  else  
  InsertBST(T->rchild,key); //大于根节点，递归查找又子树
}