树的定义
树(tree):n(n>=0)个结点构成的有限集合.
- 当n=0时,称为空树;
- 对于任一棵非空树(n>0),它具备以下性质:
- 树中有一个称为"根(root)"的特殊结点,用r表示;
- 其余结点可分为m(m>0)个互不相交的有限集T1,T2,....Tm,其中每个集合本身又是一棵树,称为原来树的"子树"(SubTree)
- 子树是不相交的;
- 除了根结点外,每个结点有且仅有一个父结点;
- 一颗N个结点的树有N-1条边.
树的一些基本术语
- 结点的度(Degree):结点的子树个数
- 树的度:树的所有结点中最大的度数
- 叶结点(Leaf):度为0的结点
- 父结点(Parent):有子树的结点是其子树的根节点的父结点
- 子节点(Child):若A结点是B结点的父结点,则称B结点是A结点的子节点;子节点也称孩子结点.
- 兄弟结点(Sibling):具有同一父结点的各节点彼此是兄弟结点.
- 路径和路径长度:从结点n1到nk的路径为一个结点序列n1,n2,...,nk, ni是ni+1的父结点.路径所包含边的个数为路径的长度.
- 祖先结点(Ancestor):沿树根到某一结点路径上的所有结点都是这个结点的祖先结点.
- 子孙结点(Descendant):某一结点的子树中的所有结点是这个结点的子孙.
- 结点的层次(Level):规定根节点在1层,其他任一结点的层数是其父结点的层数加1.
- 树的深度(Depth):树中所有结点中的最大层次是这棵树的深度.
二叉树的定义
二叉树T:一个有穷的结点集合.
- 这个集合可以为空
- 若不为空,则它是由根节点和称为其左子树TL和右子树TR的两个不相交的二叉树组成.
二叉树几个重要性质
- 一个二叉树第i层的最大结点数为:2^(i-1),i>=1
- 深度为k的二叉树的最大结点总数为:2^k-1,k>=1
- 对任何非空二叉树T,若n0表示叶结点的个数,n2是度为2的非叶结点个数,那么两者满足关系n0=n2+1
二叉树的抽象数据类型定义
- 类型名称:二叉树
- 数据对象集:一个有穷的结点集合.
- 若不为空,则由根节点和其左右二叉子树组成.
- 操作集:BT∈BinTree,Item∈ElementtType,重要操作有:
- Boolean IsEmpty(BinTree BT):判别BT是否为空
- void Traversal(BinTree BT):遍历,按某顺序访问每个结点
- BinTree CreatBinTree():创建一个二叉树.
- 常用的遍历方法有:
- void PreOrderTraversal(BinTree BT):先序---根,左子树,右子树
- void InOrderTraversal(BinTree BT):中序---左子树,根,右子树
- void PostOrderTraversal(BinTree BT):后序---左子树,右子树,根
- void LevelOrderTraversal(BinTree BT):层次遍历,从上到下,从左到右
二叉树的存储结构
- 顺序存储结构
- 完全二叉树:按从上到下,从左到右顺序存储n个结点的完全二叉树的结点父子关系
- 非根结点(序号i>1)的父结点的序号是[i/2];
- 结点(序号为i)的左孩子结点的序号是2i,(若2i<=n,否则没有左孩子);
- 结点(序号为i)的右孩子结点的序号是2i+1,(若2i+1<=n,否则没有右孩子);
- 一般二叉树也可以采用这种结构,但会造成空间浪费....
- 完全二叉树:按从上到下,从左到右顺序存储n个结点的完全二叉树的结点父子关系
- 链表存储
typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode{
ElementType Data;
BinTree Left;
BinTree Right;
}
二叉树的遍历
- 先序遍历
- 遍历过程为:
- 访问根节点;
- 先序遍历其左子树;
- 先序遍历其右子树;
- 遍历过程为:
void PreOrderTraversal(BinTree BT) {
if (BT != NULL) {
printf("%d", BT->Data);
PreOrderTraversal(BT->Left);
PreOrderTraversal(BT->Right);
}
}
- 中序遍历
- 遍历过程为
- 中序遍历其左子树;
- 访问根节点;
- 中序遍历其右子树
- 遍历过程为
void InOrderTraversal(BinTree BT) {
if (BT != NULL) {
InOrderTraversal(BT->Left);
printf("%d", BT->Data);
InOrderTraversal(BT->Right);
}
}
- 后序遍历
- 遍历过程为
- 后序遍历其左子树
- 后序遍历其右子树
- 访问根节点
- 遍历过程为
void PostOrderTraversal(BinTree BT) {
if (BT != NULL) {
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
printf("%d", BT->Data);
}
}
二叉树的非递归遍历
- 中序遍历非递归遍历算法
非递归算法是实现的基本思路:使用堆栈
- 遇到一个结点,就把他压栈,并去遍历它的左子树;
- 当左子树遍历结束后,从栈顶弹出这个结点并访问它;
- 然后按其右指针再去中序遍历该结点的右子树
void InOrderTraversal(BinTree BT) {
BinTree T = BT;
Stack S = CreateStack(MaxSize); /*创建并初始化堆栈S*/
while (T != NULL || !IsEmpty(S)) {
while (T != NULL) { /*一直向左并将沿途结点压入堆栈*/
Push(S, T);
T = T->Left;
}
if (!IsEmpty(S)) {
T = Pop(S); /*结点弹出堆栈*/
printf("%5d", T->Data); /*(访问)打印结点*/
T = T->Right; /*转向右子树*/
}
}
}
层序遍历
二叉树遍历的核心问题:二维结构的线性化
- 从结点访问其左右儿子结点
- 访问左儿子后,右儿子结点怎么办?
- 需要一个存储结构保存暂时不访问的结点
- 存储结构:堆栈,队列
队列实现
循环从根节点开始,首先将根节点入队,然后执行循环:结点出队,访问该节点,其左右儿子入队
层序基本过程:先根节点入队,然后:
- 从队列中取出一个元素;
- 访问该元素所指结点;
- 若该元素所指结点的左右孩子结点非空,则将其左右孩子的指针顺序入队
void LevelOrderTraversal(BinTree BT) {
Queue Q;
BinTree T;
if (BT == NULL) {
return; /*若是空树则直接返回*/
}
Q = CreateQueue(MaxSize);
AddQ(Q, BT);
while (!IsEmpty(Q)) {
T = DeleteQ(Q);
printf("%d\n", T->Data); /*访问取出队列的结点*/
if (T->Left != NULL) {
AddQ(Q, T->Left);
}
if (T->Right != NULL) {
AddQ(Q, T->Right);
}
}
}
二叉搜索树
什么是二叉搜索树
- 查找问题
- 静态查找与动态查找
- 针对动态查找,数据如何组织?
二叉搜索树也称二叉排序树或二叉查找树
二叉搜索树:一颗二叉树,可以为空;如果不为空,满足以下性质:
- 非空左子树的所有键值小于其根结点的键值.
- 非空右子树的所有键值小于其根结点的键值.
- 左右子树都是二叉搜索树.
二叉搜索树的特别函数:
Position Find(ElementType X, BinTree BST); //从二叉搜索树BST中查找元素X,返回其所在结点的地址;
Position FindMin(BinTree BST); //从二叉搜索树BST中查找并返回最小元素所在结点的地址;
Posion FindMax(Bintree BST); //从二叉搜索树BST中查找并返回最大元素所在结点的地址;
BinTree Insert(ElementType X, BinTree BST);
BinTree Delet(ElementType X, BinTree BST);
二叉搜索树的查找操作:Find
- 查找从根结点开始,如果树为空,返回NULL
- 若搜索树非空,则根节点关键字和X进行比较,并进行不同处理:
- 若X小于根节点键值,只需再左子树中继续搜索;
- 如果X小于根结点的键值,只需在右子树中继续搜索;
- 若两者比较结果相等,搜索完成,返回指向此结点的指针.
代码实现:
Position 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 Find(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; /*查找失败*/
}
查找的效率决定于树的高度
查找最大和最小元素
- 最大元素一定是在树的最右分枝的端结点上
- 最小元素一定是在树的最左分枝的端结点上
/*查找最小元素的递归函数*/
Position FindMin(BinTree BST) {
if (!BST) {
return NULL; /*空的二叉搜索树,返回NULL*/
} else if (!BST->Left) {
return BST; /*找到最左叶节点并返回*/
} else {
return FindMin(BST->Left); /*沿左分支继续查找*/
}
}
/*查找最大元素的迭代函数*/
Positon 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;
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); /*递归插入右子树*/
}
/*else X已经存在,什么都不做*/
}
return BST;
}
二叉搜索树的删除
- 考虑三种情况:
- 要删除的是叶结点:直接删除,并在修改其父结点指针---置为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;
}
平衡二叉树
平衡因子 (Balance Factor,简称BF):BF(T) = hL - hR, 其中hL和hR分别为T的左右子树的高度．
平衡二叉树(Balance Binary Tree)(AVL树)
空树,或者任一结点左右子树高度差的绝对值不超过1,即|BF(T)| <= 1
给定结点数为n的AVL数的最大高度为
$O(log_2n)$!
平衡二叉树的调整
"麻烦结点"在发现者右子树的右边,因而叫RR插入,需要RR旋转(右单旋);同理还有一个LL插入,需要LL旋转(左单旋);麻烦结点在左子树的右边,因而叫LR插入,需要LR旋转;同理还有一个RL插入,需要RL旋转
- 懵逼
