|
【数据结构——树表的查找（动态查找表）】
目录
【数据结构——树表的查找（动态查找表）】动态查找表（基于树的查找法）（一）二叉排序树1、定义2、查找算法3、插入算法4、创建算法5、删除算法
（二）平衡二叉树1、平衡二叉树的定义2、如何构造平衡二叉树3、AVL的插入
（三）B-树1、B-树的概念2、B-树的结点特点3、B-树的特点4、B-树的搜索算法
动态查找表（基于树的查找法）
当表插入、删除操作频繁时，为维护表的有序性，需要移动表中很多记录。 改用动态查找表——几种特殊的树 表结构在查找过程中动态生成。 对于给定值： 若表中存在，则返回成功； 否则，插入关键字等于key的记录
（一）二叉排序树
1、定义
二叉排序树又称二叉查找树 定义： 二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：  实例——判断二叉排序树  二叉排序树的存储结构：二叉链表表示
//二叉排序树的存储结构
typedef struct
{
KeyType key; //关键字项
InfoType otherinfo; //其他数据项
}ElemType; //每个结点的数据域的类型
typedef struct BSTNode
{ //结点结构
ElemType data; //数据域
struct BSTNode* lchild, * rchild; //左右孩子的指针
}BSTNode,*BSTree;
2、查找算法
算法思想  算法描述
typedef struct BSTNode
{ //结点结构
ElemType data; //数据域
struct BSTNode* lchild, * rchild; //左右孩子的指针
}BSTNode,*BSTree;
BSTree SearchBST(BSTree T, KeyType key)
{
//在指针T所指的二叉排序树中递归地查找某关键字等于key的数据元素
//若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
if (!T || key == T->data.key)
return T; //查找结束
else if (key data.key)
return SearchBST(T->lchild,key);//在左子树中继续查找
else
return SearchBST(T->rchild,key);//在右子树中继续查找
}
二叉排序树的查找分析： （1）在二叉排序树上查找其他关键字等于给定值的结点的过程，恰是走了一条从根结点到该结点的路径的过程。 比较的关键字次数=次结点所在的层次数 最多比较次数=树的深度 （2)但 二叉排序树平均查找长度和树的形态有关
 
3、插入算法
typedef struct BSTNode
{ //结点结构
ElemType data; //数据域
struct BSTNode* lchild, * rchild; //左右孩子的指针
}BSTNode, * BSTree;
//二叉排序树的插入
void InsertBST(BSTree& T, ElemType e)
{//当二叉排序树T中不存在关键字等于e.key的数据元素时，则插入该元素
if (!T) //T为空树
{ //找到插入位置，递归结束
BSTree S;
S = new BSTNode; //生成新结点*S
S->data = e; //新结点数据域置为e
S->lchild = S->rchild = NULL;//新结点*S作为叶子结点
T = S; //把新结点*S |