王道章节内容
知识框架
考纲内容
引入
因为要用到查找的部分知识,故简要引入。
要从数据中找到一个值,有静态查找(未发生插入和删除)和动态查找(发生插入和删除)两种方式。而静态查找有两种方法,一种是逐个按顺序查找,一种是高中就有介绍的二分查找。
自然而然,我们可以类似地有这样子的判定树:
ASL
“平均搜索长度”(Average Search Length),指在树中找到一个元素所需的平均比较次数。
这不禁启发我们,在计算机有没有类似的存储数据的方式?
树
定义
补充:
树与非树的判定
森林的定义
森林
- 森林是一组互不相交的树的集合。
- 森林中的每一棵树都是独立的,即不存在任何两棵树之间有边相连的情况。
- 森林中的所有节点和边构成了一个更大的图,但这个图本身不是一棵树,因为它包含了多棵树。
基本术语
存储结构
那么, 这样的结构在计算机中该如何表示呢?
双亲表示法
/* 树的双亲表示法结点结构定义 */
#define MAX_TREE_SIZE 100
typedef int TElemType; /* 树结点的数据类型,目前暂定为整型 */
typedef struct PTNode /* 结点结构 */
{
TElemType data; /* 结点数据 */
int parent; /* 双亲位置 */
} PTNode;
typedef struct /* 树结构 */
{
PTNode nodes[MAX_TREE_SIZE]; /* 结点数组 */
int r,n; /* 根的位置和结点数 */
} PTree;
关于
nodes[MAX_TREE_SIZE]
的解释
- 数组定义:
PTNode nodes[MAX_TREE_SIZE];
定义了一个固定大小的数组,该数组可以容纳最多MAX_TREE_SIZE
个PTNode
类型的结构体。数组的大小在编译时确定,不能更改。- 数组元素: 数组中的每个元素都是一个
PTNode
类型的结构体实例,因此每个元素都有自己的data
和parent
成员变量。- 数组用途: 这个数组用于存储树的所有节点。每个节点都有一个对应的索引位置,这个位置就是节点在数组中的位置。例如,根节点可能位于数组的第一个位置(假设从 0 开始计数),而其他节点根据它们在树中的位置和关系存储在数组的不同位置上。
孩子表达法
有两种“孩子法”:一种“指针域个数 = 树的度”,另一种“指针域个数 = 结点的度”(图中给出的是后者),前者会造成空间浪费,后者则需要区分“长子”与“兄弟”,这就要求有不同的结点结构:
/* 树的孩子表示法结构定义 */
#define MAX_TREE_SIZE 100
typedef int TElemType; /* 树结点的数据类型,目前暂定为整型 */
typedef struct CTNode /* 孩子结点 */
{
int child;
struct CTNode *next;
} *ChildPtr;
typedef struct /* 表头结构 */
{
TElemType data;
ChildPtr firstchild;
} CTBox;
typedef struct /* 树结构 */
{
CTBox nodes[MAX_TREE_SIZE]; /* 结点数组 */
int r,n; /* 根的位置和结点数 */
} CTree;
这里涉及到的struct用法:
当你使用
typedef
关键字与struct
结合时,可以简化结构体的声明和使用。typedef
允许你为现有的类型定义一个新的名称,这样可以让你避免在每次声明结构体变量时都要写出完整的struct
关键字和结构体定义。
struct CTNode *next;
这一行代码定义了一个结构体成员,这个成员是一个指向
CTNode
类型结构体的指针,通常用于链表中的节点连接。这里的next
指向下一个CTNode
类型的节点。
孩子兄弟表达法
有个人由根结点和子结点的关系得到启发,提出来“最左长子与最亲兄弟”的表示方法,如下图所示:
/* 树的孩子兄弟表示法结构定义 */
typedef struct CSNode
{
TElemType data;
struct CSNode *firstchild,*rightsib;
} CSNode,*CSTree;
二叉树表达法
当然,在树中识别“儿子”和“兄弟”还是有点烦的,我们考虑把它转个角度,变为“左和右”:
这就是二叉树的由来。
树、森林与二叉树的转换
树转换成二叉树
森林转换为二叉树
森林转换为二叉树
树、森林的遍历
树的遍历
森林的遍历
遍历关系
二叉树
定义
特殊二叉树
完全二叉树的判定:
判定原则:按层次从左到右编号,若出现空档,则不为完全二叉树。
性质
- 叶 = 支 + 1;
- k 层 <= 2^(k - 1);
- 树最多 2^h - 1;
- 太多不记;
- log2(n + 1)or log2(n)+1 。
抽象数据类型定义
顺序存储结构
链式存储结构
//结果代码实现
typedef struct BiTNode /* 结点结构 */
{
TElemType data; /* 结点数据 */
struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;
重要结论:在含有 n 个结点的二叉链表中,含有 n + 1 个空链域,验证如下:
遍历
二叉树的遍历
- 指按照某种次序依次访问二叉树中的所有结点;
- 使得每个结点被访问一次且仅被访问一次。
递归算法
遍历操作往往要设计到“递归”,这里贴一个链接帮助理解:http://t.csdnimg.cn/wraXX
递归“三要素”:
- 定义函数功能;
- 设定结束条件( if 语句);
- 寻找递进关系( return )。
先序遍历(根左右)
遍历过程为: ① 访问根结点; ② 先序遍历其左子树; ③ 先序遍历其右子树。
void PreOrderTraversal( BinTree BT ) //函数定义
{
if( BT ) { //结束条件
printf(“%d”, BT->Data);
PreOrderTraversal( BT->Left ); //递进
PreOrderTraversal( BT->Right );
}
}
中序遍历(左根右)
遍历过程为: ① 中序遍历其左子树; ② 访问根结点; ③ 中序遍历其右子树。
void InOrderTraversal( BinTree BT )
{
if( BT ) {
InOrderTraversal( BT->Left );
printf(“%d”, BT->Data); //访问根结点
InOrderTraversal( BT->Right );
}
}
后序遍历(左右根)
遍历过程为: ① 后序遍历其左子树; ② 后序遍历其右子树; ③ 访问根结点。
void PostOrderTraversal( BinTree BT )
{
if( BT ) {
PostOrderTraversal( BT->Left );
PostOrderTraversal( BT->Right);
printf(“%d”, BT->Data);
}
}
非递归算法
先序、中序和后序遍历过程:遍历过程中经过结点的路线一 样,只是访问各结点的时机不同。
图中,在从入口到出口的曲线上用三角形、圆形和方形三种符号,分别标记出了先序、中序和后序访问各结点的时刻。
使用非递归算法,最关键的是什么时候访问根结点,有时候需要“摁住”不访问或者先进行访问,自然而然我们可以想象到栈的知识。(回顾:http://t.csdnimg.cn/wjT1k)
中序遍历:
算法思路:
- 遇到一个结点,就把它压栈,并去遍历它的左子树;
- 当左子树遍历结束后,从栈顶弹出这个结点并访问它;
- 然后按其右指针再去中序遍历该结点的右子树。
void InOrderTraversal( BinTree BT )
{ BinTree T=BT;
Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/
while( T || !IsEmpty(S) ){
while(T){ /*一直向左并将沿途结点压入堆栈*/
Push(S,T);
T = T->Left;
}
if(!IsEmpty(S)){
T = Pop(S); /*结点弹出堆栈*/
printf(“%5d”, T->Data); /*(访问)打印结点*/
T = T->Right; /*转向右子树*/
}
}
}
先序遍历:
void LeftOrderTraversal( BinTree BT )
{ BinTree T BT;
Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/
while( T || !IsEmpty(S) ){
while(T){ /*一直向左并将沿途结点压入堆栈*/
printf(“%5d”, T->Data); /*(访问)打印根结点*/
Push(S,T);
T = T->Left;
}
if(!IsEmpty(S)){
T = Pop(S); /*结点弹出堆栈*/
T = T->Right; /*转向右子树*/
}
}
}
层次遍历
队列回顾:http://t.csdnimg.cn/wjT1k
算法思路:
- 先根节点入队;
- 从队列中取出一个元素;
- 访问该元素所指结点;
- 若该结点的左右非空, 则将其左右指针顺序入队。
void LevelOrderTraversal ( BinTree BT )
{ Queue Q; BinTree T;
if ( !BT ) return; /* 若是空树则直接返回 */
Q = CreatQueue( MaxSize ); /*创建并初始化队列Q*/
AddQ( Q, BT );
while ( !IsEmptyQ( Q ) ) {
T = DeleteQ( Q );
printf(“%d\n”, T->Data); /*访问取出队列的结点*/
if ( T->Left ) AddQ( Q, T->Left );
if ( T->Right ) AddQ( Q, T->Right );
}
}
应用-二叉树构造
问题:已知四种遍历序列中的最少几种,才能确定唯一的一棵树?
答案:最少两种,且必须要有中序遍历。
先序和中序:
(ppt这张图很好,帮助理解)
后序和中序:
层序与后序:
线索二叉树
定义
前驱与后继:类似双向链表里的 pre 和 next;
左右孩子:左子树根和右子树根。
typedef char TElemType;
typedef enum {Link,Thread} PointerTag; /* Link=0表示指向左右孩子指针, */
/* Thread=1表示指向前驱或后继的线索 */
typedef struct BiThrNode /* 二叉线索存储结点结构 */
{
TElemType data; /* 结点数据 */
struct BiThrNode *lchild, *rchild; /* 左右孩子指针 */
PointerTag LTag;
PointerTag RTag; /* 左右标志 */
} BiThrNode, *BiThrTree;
} BiThrNode, *BiThrTree;
: 结束BiThrNode
结构体的定义,并定义BiThrTree
为指向BiThrNode
类型的指针,通常用作树根节点的指针。
enum
是 C 语言中的一个关键字,用于定义枚举类型。枚举类型是一种用户定义的类型,它由一组命名的整数常量组成,这些常量通常用来表示一组相关的值。枚举类型提供了一种更加清晰的方式来处理一组固定的选项,而不是直接使用整数值 。用法示例如下:
enum enumeration_name {
enumerator1,
enumerator2,
...
};
每个
enumerator
都是一个标识符,它代表一个整数值。默认情况下,第一个枚举器的值是 0,后续的枚举器的值依次递增 1。
构造
中序线索二叉树
/* 中序遍历进行二叉树线索化 */
void InThread(ThrTree &p, ThrTree &pre)
{
if(p)
{
InThread(p->lchild,pre); /* 递归,左子树线索化 */
if(!p->lchild) /* 当前结点左子树为空 */
{
p->LTag=1; /* 前驱线索 */
p->lchild=pre; /* 左孩子指针指向前驱 */
}
if(pre->rchild && !pre->Rchild) /* 前驱结点非空且其右子树为空 */
{
pre->RTag=1; /* 后继线索 */
pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */
}
pre=p; /* 保持pre指向p的前驱 */
InThread(p->rchild); /* 递归,右子树线索化 */
}
}
//中序遍历建立线索二叉树
void CreatInThread(ThreadTree T){
ThreadTree pre=NULL;
if(T!=NULL){ //非空二叉树,线索化
InThread(T,pre);
pre->rchild = NULL; //处理最后一个结点
pre->Rtag = 1;
}
}
遍历
中序线索二叉树
不带头结点:
对于不带头结点的中序线索二叉树,其特点是:
- 每个叶子节点的左右指针可能被用作线索。
- 每个非叶子节点的左指针指向其左孩子或者指向其中序前驱。
- 每个非叶子节点的右指针指向其右孩子或者指向其中序后继。
算法步骤:
- 初始化:设置一个指针
current
指向根节点,并设置一个指针pre
用于保存上一个访问过的节点。- 寻找最左下节点:如果
current
的左子树存在且不是线索,则递归地向左移动直到找到最左下的节点。- 访问节点:当
current
不再有左子树时,访问current
节点,并将pre
指向current
。- 处理右子树:如果
current
的右子树存在且不是线索,则重复步骤2;否则,继续到下一个节点(即中序后继)。- 重复步骤3和4:直到
current
为空。
懒得打又没得找哈哈:
带头结点:
/* 中序遍历二叉线索树T(头结点)的非递归算法 */
Status InOrderTraverse_Thr(BiThrTree T)
{
BiThrTree p;
p=T->lchild; /* p指向根结点 */
while(p!=T)
{ /* 空树或遍历结束时,p==T */
while(p->LTag==Link)
p=p->lchild;
if(!visit(p->data)) /* 访问其左子树为空的结点 */
return ERROR;
while(p->RTag==Thread&&p->rchild!=T)
{
p=p->rchild;
visit(p->data); /* 访问后继结点 */
}
p=p->rchild;
}
return OK;
}
先序和后序线索二叉树
树与二叉树的应用
哈夫曼树
引入
那么,怎么提高查找效率,降低这个数呢?我们考虑先判定比例相对高的: