数据结构(第六章)
树和二叉树
树
树：是n（n≥0）个结点的有限集。当n=0时，称为空树；在任意一棵非空树中满足如下条件：
- 有且仅有一个特定的称为根（root）的结点，它没有直接前驱，但有零个或多个直接后继。
- 其余n-1个结点可以划分成m（m>0）个互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵树，称为根root的子树。 每棵子树的根结点有且仅有一个直接前驱，但有零个或多个直接后继
从逻辑结构看：
- 树中只有树根没有父结点；
- 除根外，其余结点都有且仅一个父结点
- 树中的结点，可以有零个或多个孩子结点；
- 没有孩子的结点称为叶子结点，或终端结点
- 除根外的其他结点，都存在唯一一条从根到该结点的路径
树的基本术语
- 树的结点：包含一个数据元素及若干指向子树的分支；
- 孩子结点：结点的子树的根称为该 结点的孩子
- 父结点：B 是A的孩子，则A是B的父亲；
- 兄弟结点：同一双亲的孩子结点；
- 堂兄弟结点：其父结点在同一层上的结点；
- 祖先结点: 从根到该结点所经分支上的所有结点；
- 子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙
- 结点的度: 结点的孩子数目
- 有序树和无序树：在树中，如果各子树Ti是按照一定的次序从左向右安排的，且相对次序是不能随意改变的，则称为有序树，否则称为无序树
- 森林： m（m≥0）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，给m棵独立的树增加一个根结点，并把这m棵树作为该结点的子树，森林就变成一棵树
树的基本运算
树的运算主要分为三大类：
- 第一类，寻找满足某种特定关系的结点,如寻找当前结点的双亲结点等
- 第二类，插入或删除某个结点,如在树的当前结点上插入一个新结点或删除当前结点的第i个孩子结点等
- 第三类，遍历树中每个结点,这里着重介绍
二叉树
-
二叉树的定义：二叉树 是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树
- 二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况
- 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别
-
二叉树的5种基本形态
其中：(c)和（d）是不同的两棵二叉树
二叉树的性质
-
性质1：在二叉树的第i层上至多有2i-1个结点
证明： 用数学归纳法。
-
当i=1时，整个二叉树只有一根结点，此时$2^{i-1}=2^0=1$，结论成立
-
设i=k时结论成立，即第k层上结点总数最多为$2^{k-1}$个
现证明当i=k+1时， 结论成立：
因为二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即$2×2^{k-1}=2 ^{(k+1)-1}$，故结论成立
度为m的树中第i层上至多有$m^{i-1}$个结点, (i≥1)。
-
-
性质2：深度为k的二叉树至多有2k-1个结点
证明：因为深度为k的二叉树，其结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为k的二叉树的结点总数至多为
深度为k的m叉树至多有 $\frac{m^k-1}{m-1}$个结点
-
性质3：任何一棵二叉树中度为2的结点数目(n2)比度为0的结点数目($n_0$)少1，即$n_2＝ n_0-1$
证明：设二叉树中结点总数为n，n1为二叉树中度为1的结点总数，设二叉树中分支数目为B
-
$n=n_0+n_1+n_2$
除根结点外，每个结点均对应一个进入它的分支
-
n=B+1
二叉树中的分支都是由度为1和度为2的结点发出
-
$B=n_1+2n_2$
-
-
性质4：一个有n个结点的完全二叉树的高度为$[log_2n]+1或 [log_2(n+1)]$
-
性质5完全二叉树中的某结点编号为i，则
- 若该结点有左孩子，则左孩编号为2i
- 若该结点有右孩子，则右孩子结点编号为2i+1
- 若该结点有双亲，则双亲结点编号为$[i/2]$
满二叉树和完全二叉树
-
满二叉树
深度为k且有$2^k-1$个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数
满二叉树的顺序表示，即从二叉树的根开始， 层间从上到下， 层内从左到右，逐层进行编号（1， 2， …， n）
-
完全二叉树：
深度为k，结点数为n的二叉树，如果其结点1~n的位置序号分别与满二叉树的结点1~n的位置序号一一对应，则为完全二叉树，
满二叉树必为完全二叉树， 而完全二叉树不一定是满二叉树
二叉树的顺序存储
-
二叉树的顺序存储指的是用元素在数组中的下标表示一个结点与其孩子和父结点的关系.
-
完全二叉树的顺序存储
#define MAX_TREE_SIZE 100 typedef TelemType SqBiTree[MAX_TREE_SIZE]; SqBiTree bt; -
非完全二叉树的顺序存储
-
非完全二叉树不适合进行顺序存储
二叉树的链式存储
-
一般用二叉链表存储二叉树(每个结点有两个指针域)
typedef struct BiTNode{ TElemType data; struct BiTNode *Lchild,*Rchild; }BiTNode, *BiTree; -
三叉链表存储二叉树(每个节点有三个指针域)
遍历二叉树和线索二叉树
-
任何一个非空的二叉树都由三部分构成
树的遍历是访问树中每个结点仅一次的过程。遍历可以被认为是把所有的结点放在一条线上，或者将一棵树进行线性化的处理
二叉树的遍历
- 先左后右：DLR，LDR，LRD
- 先右后左：DRL，RDL，RLD
先序遍历
-
DLR：访问根结点、先序遍历左子树、先序遍历右子树
若二叉树为空，结束 ——基本项（也叫终止项）
若二叉树非空
- 访问根结点；
- 先序遍历左子树
- 先序遍历右子树
void preorder (BiTNode *root) {//先序遍历root指向根的二叉树 if (root!=NULL) { cout<< root->data；//访问根结点 preorder(root->Lchild); //先序遍历根的左子树 preorder(root->Rchild); //先序遍历根的右子树 }//if }//preorder
中序遍历
-
LDR：中序遍历左子树、访问根结点、中序遍历右子树
若二叉树为空，结束 ——基本项（也叫终止项 )
若二叉树非空 ——递归项
- 中序遍历左子树
- 访问根结点
- 中序遍历右子树
void inorder (BiTNode *root) {//先序遍历root指向根的二叉树 if (root!=NULL) { inorder(root->Lchild); //先序遍历根的左子树 cout<< root->data；//访问根结点 inorder(root->Rchild); //先序遍历根的右子树 }//if }//inordervoid InOrder (BiTNode *root) { InitStack(S); Push(S,root); //根指针进栈 while (!StackEmpty(S)) { while(GetTop(S,p)&&p) Push(S,p->Lchild); //向左走到头 Pop(S,p); //空指针退栈 if (!StackEmpty(S)) { Pop(S,p); cout << p->data; //访问结点 Push(S,p->Rchild); //向右 } //if }//while }//InOrder
后序遍历
-
LRD：后序遍历左子树、后序遍历右子树、访问根结点
后序遍历序列:BDFGECA
void postorder (BiTNode *root) { if (root!=NULL) { postorder(root->Lchild); //后序遍历根的左子树 postorder(root->Rchild); //后序遍历根的右子树 cout<< root->data；//访问根结点 }//if }//postorder
层序遍历
-
先根，后子树；先左子树，后右子树
线索二叉树
typedef enum PointerTag {Link=0,Thread=1};
typedef struct BiThrNode{
ElemType data;
struct BiThrNode *Lchild,*Rchild;
PointerTag Ltag, Rtag;
}*BiThrTree;
中序线索二叉树
-
在中序线索化二叉树上查找给定结点的前驱和后继结点
-
在中序线索二叉树上，查找p所指结点的后继分为两种情况：
-
若p->Rtag=1，则p->Rchild指向其后继结点
-
若p->Rtag=0，则p所指结点的中序后继必为其右子树中序遍历得到的第一个结点，即从p所指结点的右子树根出发，沿左指针链向下找，直到找到一个没有左孩子的结点为止，这个结点称为p的右子树中“最左下”的结点。
-
中序线索二叉树上找指定结点的后继
typedef struct BiThrNode{ ElemType data; struct BiThrNode *Lchild,*Rchild; PointerTag Ltag,Rtag; }*BiThrTree; BiThrTree inordernext(BiThrTree p) { if （p->rtag==1） return(p->Rchild); else { q=p->Rchild; while (q->ltag==0) q=q->Lchild; return(q); } } void InThreading(BiThrTree p) { if (p) { InThreading(p->Lchild); //左子树线索化 if (!p->Lchild) {//前驱线索 p->Ltag = Thread; p->Lchild = pre; } if (!pre->Rchild) {//后继线索 pre->Rtag = Thread; pre->Rchild = p; } pre = p; InThreading(p->Rchild); //右子树线索化 } }//InThreading void InOrderThreading(BiThrTree &Thrt, BiThrTree root) { //Thrt指向中序线索化链表的头结点 if (!Thrt = (BiThrTree)malloc(sizeof(BiThrNode))) exit(OVERFLOW); Thrt->Ltag = Link; Thrt->Rtag = Thread; Thrt->Rchild = Thrt; if (root == NULL) Thrt->Lchild = Thrt; else { Thrt->Lchild = root; pre = Thrt; InThreading(root); //中序遍历进行中序线索化 pre->Rchild = Thrt; pre->Rtag = Thread; Thrt->Rchild = pre; } }//InOrderThreading
-
后序线索二叉树
-
在后序线索化二叉树上查找给定结点的前驱和后继结点
-
在后序线索二叉树上，查找p所指结点的后继分为两种情况：
-
若p所指结点是整棵二叉树的根结点，则无后继结点
-
若p->Rtag=1，则p->Rchild指向其后继结点；
-
若p->Rtag=0：//P所指结点有右子树
- 若p所指结点是其父结点f的右孩子，则其父结点f是其后继；
- 若p所指结点是其父结点f的左孩子：
- 若p所指结点没有右兄弟，则其父结点f是其后继；
- 若P有右兄弟，则其后继结点是其父的右子树上后序遍历得到的第一个结点。
-
先序线索二叉树
- 在先序线索化二叉树上查找给定结点的前驱和后继结点
树和森林
树的存储结构
-
双亲表示法
采用一组地址连续的存储单元存储树的结点,通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系
//双亲表示类型定义 #define MAX 100 struct node{ char data; int parent; //双亲位置域 }; typedef struct node NODE; NODE tree[MAX]; -
孩子表示法
通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。
-
孩子兄弟表示法
用二叉链表作为树的存贮结构。链表的两个指针域分别指向该结点的第一个孩子结点和其右边的下一个兄弟结点
struct node { char data; struct node *son, * brother; };
树与二叉树的转换
-
借助于“孩子兄弟表示法”实现树与二叉树之间的转化
-
将下面的二叉树转换为树
树的遍历
-
树的结构特点：树根、树的子树森林
-
树的先根遍历：先访问根结点、然后依次先根遍历树的子树森林。
-
树的后根遍历：先依次后根遍历每棵子树，然后访问根结点
- 树的先根遍历等同于对转换所得的二叉树进行先序遍历
- 树的后根遍历等同于对转换所得的二叉树进行中序遍历
-
森林的遍历
- 森林的先序遍历等于对转换所得的二叉树进行先序遍历
- 森林的中根遍历等于对转换所得的二叉树进行中序遍历
森林的先序遍历
-
森林的结构特点：第一棵树、其余的树
森林的先序遍历：
- 访问森林中第一棵树的根结点；
- 先序遍历第一棵树中根结点的子树森林；
- 先序遍历除第一棵树后剩余的树构成的森林
森林的中序遍历
森林的中序遍历：
- 中序遍历第一棵树中根结点的子树森林
- 访问森林中第一棵树的根结点；
- 中序遍历除第一棵树后剩余的树构成的森林
最优二叉树
例：编写程序将百分制表示的成绩score转换为等级分grade，规则为：
赫夫曼树(最优二叉树)
-
最优二叉树是一类带权路径长度最短的树
-
路径和路径长度
- 从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称作路径长度。
-
结点的权
- 根据应用的需要可以给树的结点赋权值
-
结点的带权路径长度
- 从根到该结点的路径长度与该结点权的乘积称为结点的带权路径长度
-
树的带权路径长度
-
树中所有叶子的带权路径长度之和称为树的带权路径长度，记作
-
-
设有四个叶子a、b、c和d的二叉树中，对应的权值分别为7、5、2和4，计算WPL。
最优二叉树是一类带权路径长度最短的树
赫夫曼算法
- 根据给定的n个权值{$w_1,w_2,…,w_n$}构造n棵二叉树的集合F={$T_1,T_2,…,T_n$}，其中每棵二叉树Ti中只有一个带权为$w_i$的根结点，其左右子树均空
- 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和
- 在F中删除这两棵树，同时将新得到的二叉树加入F中。
- 重复2和3，直到F中只含一棵树为止。这棵树便是最优二叉树。
编码－译码
-
在进行数据通讯时，涉及数据编码问题。所谓数据编码就是将信息原文转换为二进制字符串，译码则是将信息的编码形式转换为原文。
-
例如发电报：
等长编码方案
例如：要传送的信息原文为“ABACCDA”
不等长编码方案
例如：要传送的信息原文为“ABACCDA”
前缀编码
为一个字符集合中的字符进行编码时，若每个字符的编码不是其他字符编码的前缀，则称这种编码为前缀编码。
赫夫曼编码
-
已知某系统在通信联络中只可能出现8种字符，其概率如下表所示:
-
**为字符建立赫夫曼编码 **
赫夫曼编码举例
typedef struct {
char ch;
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*Huffmantree;
Huffmantree HT;
HT = new HTNode[2*n]; //赫夫曼树的存储结构
赫夫曼编码的求解算法
typedef struct {
char ch;
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*Huffmantree;
Huffmantree HT;
HT = new HTNode[2*n];//赫夫曼树的存储结构
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC,int *w,int n)
{//w存放n个字符的权值，构造赫夫
曼树HT，并求出n个字符的编码
if (n<=1) return;
m = 2*n-1;
HT = new HTNode[m+1];
for(i=1; i<=n; i++)
HT[i].weight = w[i-1];
for(i=1; i<=m; ++i) {
HT[i].parent = 0;
HT[i].lchild =0;
HT[i].rchild = 0;
}
for(i=n+1; i<=m; i++) {//构造赫夫曼树
//从HT[1..i-1]中选择parent为0且weight最小的两个结点，
//其序号为s1和s2
select(HT,i-1,s1,s2);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
//从叶子到根逆向求每个字符的赫夫曼编码
HC = new char*[n+1];
cd = new char [n]; cd[n-1] = ‘\0’;
for(i=1; i<=n; i++) {
start = n-1;
for(j=i,f=HT[i].parent; f!=0; j=f,f=HT[f].parent)
if (HT[f].lchild == j) cd[--start]=‘0’;
else cd[--start]=‘1’;
HC[i] = new char [n-start];
strcpy(HC[i],&cd[start]);
}
delete cd[];
}//HuffmanCoding
译码
译码算法
//将二进制编码翻译回信息原文，m是树根的编号
void Decoding(HuffmanTree HT,int m,char *buff){
int p=m;
while (*buff!=‘\0’ && p!=0) {
if ((*buff)==‘0’)
p=HT[p].lchild; //进入左分支
else
p = HT[p].rchild; //进入右分支
buff++;
if (!HT[p].lchild && !HT[p].rchild) { //进入叶子结点
cout << HT[p].ch;
p = m; //重新从树根出发进行译码
}//if
}//while
}//Decoding