二叉搜索树

查找问题：

• 静态查找与动态查找
• 针对动态查找，数据如何组织

什么是二叉搜索树(Binary Search Tree, BST)

又叫 二叉查找树，二叉排序树

二叉树不为空时，性质：

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

typedef struct TreeNode *BinTree;//结构指针
typedef BinTree Position;//结构指针重命名为Position
struct TreeNode{ElementType Data;BinTree Left;BinTree Right;
}

二叉搜索树的查找操作：Find

思路

• 查找从根结点开始，如果树为空，返回NULL

• 若搜索树非空，则根节点关键字和X比较，并进行不同的处理：

  1. 若X小于根结点键值，只需要在左子树中继续搜索
  2. 若X大于根结点的键值，在右子树中继续搜索
  3. 若两者比较结果相等，搜索完成。返回指向该结点的指针

Position Find(ElementType X, BinTree BST)
{if(!BST)return NULL;//查找失败if(X > BTS->Data)return Find(X, BTS->Right);//右子树继续查找,尾递归Else if(X < BTS->Data)return Find(X, BTS->Left);//左子树继续查找else//X == BTS->Datareturn BST;//查找成功，返回找到结点的地址
}

非递归函数的执行效率更高，可将“尾递归”函数改为循环函数

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

查找最大和最小元素

• 最大元素一定在树的最右分支的端结点上
• 最小元素一定在树的最左分支的端结点上

Position FindMin(BinTree BST)
{if(!BST)return NULL;//空的二叉树，返回NULLelse if(!BST->)return BST;//找到最左结点并返回elsereturn FindMin(BST->Left);//沿着左分支继续查找
}

//查找最大元素的递归函数
Position FinMax(BinTree BST)
{if(!BST)return NULL;else if(!BST->Right)return BST;elsereturn FinMax(BST->Right);
}

//查找最大元素的迭代函数
Position FindMax(BinTree BST)
{if(BST)while(BST->Right)BST = BST->Right;//沿着右分支查找，直到找到最右结点return BST;
}

二叉搜索树的插入

思路：找到元素应该插入的位置。可以采用与Find类似的方法

BinTree Insert(ElementType X, BinTree BST)
{if(!BST)//若原树为空，生成并返回一个结点的二叉搜索树{BST = malloc(sizeof(struct TreeNode));//申请空间BST->Data = X;//把这个值设为XBST-Left = BST->Right = NULL;//左右两边都设为NULL}elseif(X < BST->Data)BST->Left = Insert(X, BST->Left);else if(X > BST->Data)BST->Right = Insert(X, BST->Right);return BST;
}

二叉搜索树的删除

三种情况：

1. 要删除的结点是叶结点
2. 要删除的结点只有一个子树
3. 要删除的结点有左右两颗子树
   1. 去右子树中的最小值替代
   2. 去左子树中找最大值替代

//
BinTree Delete(ElementType X, BinTree BST)
{Position tmp;if(!BST)printf("not find");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;
}

平衡二叉树

什么是平衡二叉树

结点不同的插入次序，将导致不同的深度和不同的查找效率及平均查找长度ASL

平衡因子(Balance Factor BF)：BF(T) = h_L - h_R，其中h_L，h_R分别是T的左右子树的高度。

平衡二叉树(Balance Binary Tree)(AVL树)：

空树，或者任一结点左右子树高度差的绝对值不超过1，即**|BF(T)| <= 1**

平衡二叉树的高度

斐波那契数列：

平衡二叉树的调整

RR旋转

LL旋转

LR旋转

RL旋转

专场：判别是不是同一个二叉搜索树

1. 分别建两棵搜索树的判别方法
2. 不建树的判别方法
3. 建一棵树，再判别其他序列是否与该树一致

搜索树的表示

typedef struct TreeNode *Tree;
struct TreeNode{int v;//表示结点的基本信息Tree Left, Right;int flag;//判别序列是不是跟树一致；没被访问为0；访问过为1
};

如何建搜索树

不是同一个二叉搜索树

1. 分别建两棵搜索树的判别方法
2. 不建树的判别方法
3. 建一棵树，再判别其他序列是否与该树一致

搜索树的表示

typedef struct TreeNode *Tree;
struct TreeNode{int v;//表示结点的基本信息Tree Left, Right;int flag;//判别序列是不是跟树一致；没被访问为0；访问过为1
};

如何建搜索树