树的定义和基本术语二叉树 (Binary Tree)
二叉树的存储结构遍历二叉树 (Binary Tree Traversal)
线索化二叉树 (Threaded Binary Tree)
树与森林 (Tree & Forest)
赫夫曼树 (Huffman Tree)
二叉树的计数
6.1 树的定义和基本术语
1,树的定义树是由 n (n? 0)个结点组成的有限集合。
如果 n = 0，称为空树；
如果 n > 0，则,
有一个特定的称之为 根 (root)的结点，它只有后继，但没有前驱；
除根以外的其它结点划分为 m (m? 0)个互不相交的有限集合 T0,T1,…,Tm-1，每个集合本身又是一棵树，并且称之为根的 子树 (subTree)。每棵子树的根结点有且仅有一个 直接 前驱，但可以有
0个或多个后继。
结点 (node)
结点的度 (degree)
分支 (branch)结点
叶 (leaf)结点
孩子 (child)结点
双亲 (parent)结点
兄弟 (sibling)结点
祖先 (ancestor)结点
子孙 (descendant)结点
结点所处层次 (level)
树的深度 (depth)
树的度 (degree)
有序树
无序树
森林
1）度（次数、级）
（ 1）结点的度：一个结点所拥有的子数的个数
（ 2）树的度：树内各结点的度的最大值
2）描述上下及左右的关系孩子结点：一个结点的子树的根双亲结点,P120
兄弟结点：同一个双亲的孩子之间互称兄弟祖先：结点的祖先是从根到该结点所经分支上的所有结点子孙,P120结点的后代
3）层次
（ 1）结点的层次
（ 2）树的深度（高度）
2,树的基本术语树的基本操作,p119
树的建立和遍历 —— 重点树的抽象数据类型
6.2 二叉树 (Binary Tree)
二叉树的定义二叉树的五种不同形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
特点,1）每个结点的度 ≤2； 2）是有序树基本操作,p121~p123
二叉树的建立和遍历二叉树的抽象数据类型性质 1 若二叉树的层次从 1开始,则在二叉树的第 i 层最多有 2i-1个结点。 (i? 1)
[证明用数学归纳法 ]
性质 2 深度为 k的二叉树最多有 2k-1个结点。
(k? 1)
[证明用求等比级数前 k项和的公式 ]
性质 3 对任何一棵二叉树,如果其叶结点个数为
n0,度为 2的非叶结点个数为 n2,则有
n0＝ n2＋ 1
二叉树的性质证明,若设度为 1的结点有 n1个，总结点个数为 n，总边数为 e，则根据二叉树的定义，
n = n0 + n1 + n2 e = 2n2 + n1 = n - 1
因此，有 2n2 + n1 = n0 + n1 + n2 - 1
n2 = n0 - 1 n0 = n2 + 1
同理：
三次树,n0=1+n2+2n3
四次树,n0=1+n2+2n3+3n4
…
K次树,n0=1+n2+2n3+…+(k -1)nk
定义 1 满二叉树 (Full Binary Tree)
定义 2 完全二叉树 (Complete Binary Tree)
若设二叉树的深度为 h，则共有 h层。除第 h层外，其它各层 (0?h-1)的结点数都达到最大个数，
第 h层从右向左连续缺若干结点，这就是完全二叉树。
性质 4 具有 n个结点的完全二叉树的深度为
log2n? +1
证明,设完全二叉树的深度为 k，则有
2k-1 - 1 < n? 2k - 1 2k-1? n < 2k
取对数 k-1? log2n < k
因为 k为整数，所以 k =?log2n? +1
说明：常出现在选择题中性质 5 如果将一棵有 n个结点的完全二叉树的结点按层序 (自顶向下，同一层自左向右）连续编号 1,2,…,n，然后按此结点编号将树中各结点顺序地存放于一个一维数组中,并简称编号为 i的结点为结点 i (1? i? n)。则有以下关系：
若 i == 1,则 i 是二叉树的根，无双亲若 i > 1,则 i 的双亲为?i /2?
若 2*i≤ n,则 i 的左孩子为 2*i，否则无左孩子若 2*i+1 ≤ n,则 i 的右孩子为 2*i+1，否则无右孩子
若 i 为偶数,且 i != n,则其右兄弟为 i+1
若 i 为奇数,且 i != 1,则其左兄弟为 i-1
i 所在层次为?log2 i? +1
完全二叉树的数组表示 一般二叉树的数组表示二叉树的存储结构
1,顺序存储结构（数组表示）
#define MAX_TREE_SIZE 100
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;
由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。
单支树
2.链式存储结构
typedef struct BiTNode{ //二叉链表的定义
TElemType data;
Struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
二叉树链表表示的示例
3,静态二叉链表和静态三叉链表预先开辟空间，用数组表示
leftChild,rightChild—— 数组元素的下标
6.3 遍历二叉树
(Traversing Binary Tree) p128
所谓树的遍历，就是按某种次序访问树中的结点，
要求每个结点访问一次且仅访问一次。
遍历的结果,产生一个关于结点的线性序列。
设 访问根结点 记作 D
遍历根的左子树 记作 L
遍历根的右子树 记作 R
则可能的遍历次序有先序 DLR DRL 逆先序中序 LDR RDL 逆中序后序 LRD RLD 逆后序先序遍历 (Preorder Traversal)
先序遍历二叉树算法的框架是
若二叉树为空，则空操作；
否则
访问根结点 (D)；
先序遍历左子树 (L)；
先序遍历右子树 (R)。
遍历结果（前缀表达式）
- + a * b - c d / e f
在波兰式中，自左到右依次扫描：连续出现 2
个操作数时，将其前面的运算符退出，对该两操作数进行这两个操作数前面的运算符的运算，
运算的中间结果进栈，
然后再进行上述的操作。
先序遍历二叉树的递归算法
void PreOrderTraverse(BiTree T){
if (T){
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
中序遍历二叉树算法的框架是：
若二叉树为空，则空操作；
否则
中序遍历左子树 (L)；
访问根结点 (D)；
中序遍历右子树 (R)。
遍历结果（中缀表达式）
a + b * c - d - e / f
中序遍历 (Inorder Traversal)
表达式语法树中序遍历二叉树的递归算法
void InOrderTraverse(BiTree T){
if (T) {
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
}
后序遍历 (Postorder Traversal)
后序遍历二叉树算法的框架是
若二叉树为空，则空操作；
否则
后序遍历左子树 (L)；
后序遍历右子树 (R)；
访问根结点 (D)。
在逆波兰式中，自左到右依次扫描：是操作数，
则依次进栈；遇到运算符。则退出两个操作数，
对该两操作数进行该运算符的运算，运算的中间结果进栈；然后再继续重复上述的操作。
遍历结果（后缀表达式）
a b c d - * + e f / -
后序遍历二叉树的递归算法
void PostOrderTraverse(BiTree T){
if (T) {
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data);
}
}
由二叉树的先序序列和中序序列可唯一地确定一棵二叉树。 例,先序序列 { ABHFDECKG } 和 中序序列 { HBDFAEKCG },构造二叉树过程如下：
遍历二叉树的非递归算法
先序遍历：算法 1，将右子树根结点 入栈,(栈所需最大容量为 n/2+1)；算法 2将根结点入栈
中序遍历：在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈中弹出，访问，再遍历右子树
后序遍历：
1）设定一个指针，指向 最近访问过的结点。在退栈取出根结点时，需判断：若根结点的右子树为空，或它的右子树非空，但已遍历完毕，即它的右子树根结点恰好是最近一次访问过的结点时，应该遍历该根结点。反之，该根结点应重新入栈，先遍历它的右子树。
2）还可同时设定一个标记，指示该根结点是第一次还是第二次入栈
需用到栈，顺序栈的定义如下：
typedef BiTNode* SElemType;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
先序遍历的非递归算法
void preorder(BiTree T)
{ SqStack S; BiTree P=T;
InitStack(S); Push(S,NULL);
while (P)
{ printf("%c",P->data);
if (P->rchild)
Push(S,P->rchild);
if (P->lchild)
P=P->lchild;
else Pop(S,P);
}
}
先序遍历的非递归算法 2
void preorder(BiTree T){
int top=0;
BiTree stack[20],P=T;
do { while (P){
printf("%c",P->data);
stack[top]=P; top++;
P=P->lchild; }
if (top){
top--; P=stack[top];
P=P->rchild;}
}while (top || P);
}
中序遍历的非递归算法 1
void inorder(BiTree T){
SqStack S; BiTree P=T;
InitStack(S);
do{ while(P){
* (S.top) = P; S.top++;
P=P->lchild; }
if (S.top){
S.top--; P=*(S.top);
printf("%c",P->data);
P=P->rchild;}
}while((S.top!=S.base) || P);
}
中序遍历的非递归算法 2（ p131算法 6.3)
void inorder(BiTree T)
{ SqStack S; BiTree P=T;
InitStack(S);
while( P || !Empty(S))
{ if (P) { Push(S,P);
P=P->lchild; }
else { Pop(S,P);
printf("%c",P->data);
P=P->rchild;}
}
}
后序遍历时，每遇到一个结点，先把它推入栈中，让 PopTim=0。在遍历其左子树前，改结点的
PopTim=1，将其左孩子推入栈中。在遍历完左子树后，还不能访问该结点，必须继续遍历右子树，
此时改结点的 PopTim=2，并把其右孩子推入栈中。
在遍历完右子树后，结点才退栈访问。
后序遍历的非递归算法 1
void Postorder(BiTree T)
{ BiTree p=T,q=NULL;
SqStack S; InitStack(S); Push(S,p);
while (!StackEmpty(S))
{ if (p && p!=q) { Push(S,p); p=p->lchild; }
else { Pop(S,p);
if (!StackEmpty(S))
if (p->rchild && p->rchild!=q)
{ Push(S,p); p=p->rchild; }
else {printf("%c",p->data); q=p;}
}
}
}
后序遍历的非递归算法 2
void postorder(BiTree T)
{BiTree P=T,q; int flag; SqStack S; InitStack(S);
do {
while (P){ *(S.top)=P;S.top++;P=P->lchild;}
q=NULL; flag=1;
while ((S.top!=S.base) && flag)
{ P=*(S.top-1);
if (P->rchild == q)
{ printf("%c",P->data); S.top--; q=p;}
else { P=P->rchild; flag=0;}
}
}while ((S.top!=S.base));
}
先序建立二叉树的递归算法 (p131,算法 6.4)
Status CreateBiTree(BiTree &T)
{ char ch; scanf("%c",&ch);
if (ch==' ') T=NULL;
else { if (!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
二叉树的显示输出
void PrintBiTree(BiTree T,int n)
{
int i; char ch=' ';
if (T) {
PrintBiTree(T->rchild,n+1);
for (i=1;i<=n;++i) {printf("%5c",ch);}
printf("%c\n",T->data);
PrintBiTree(T->lchild,n+1);
}
}
说明：
1）遍历的第一个和最后一个结点第一个结点：
先序,根结点；
中序,沿着左链走，找到一个没有左孩子的结点；
后序,从根结点出发，沿着左链走，找到一个既没有左孩子又没有右孩子的结点。
最后一个结点：
中序,从根结点出发，沿着右链走，找到一个没有右孩子的结点；
后序,根结点。
先序：从根结点出发，沿着右链走，找到一个没有右孩子的结点；如果该结点有左孩子，再沿着其左孩子的右链走，以此类推，直到找到一个没有孩子的结点
求中序的第一个结点的算法：
P=T;
while (P->lchild) P=P->lchild;
printf(P->data);
求中序的最后一个结点的算法：
P=T；
while(P->rchild) P=P->rchild;
Printf(P->data);
2）先序 +中序 或 后序 +中序均可唯一地确定一棵二叉树
3）二叉树的二叉链表存储结构中，有 n+1个指针域未利用，已经使用的有 n-1个指针域，共有 2n个指针域利用二叉树 后序遍历 计算二叉树的深度
int Depth(BiTree T){
int depl,depr;
if (T){
depl=Depth(T->lchild);
depr=Depth(T->rchild);
if (depl>=depr) return (depl+1);
else return (depr+1);
}
return 0;
}
遍历二叉树的应用求二叉树结点个数
int Size(BiTree T)
{
if (T==NULL) return 0;
else return 1 + Size (T->lchild ) + Size ( T->rchild);
}
按层次遍历二叉树从根开始逐层访问，
用 FIFO队列实现。
typedef BiTNode* ElemType;
typedef struct{
QElemType *base;
int front,rear;
}SqQueue;
遍历顺序
void LevelOrderTraverse(BiTree T)
{ BiTree p; SqQueue Q; InitQueue(Q);
if (T){ Q.base[Q.rear]=T;
Q.rear=(Q.rear+1)%MAXQSIZE;
while (Q.front !=Q.rear)
{ p=Q.base[Q.front];
printf("%c",p->data);
Q.front=(Q.front+1)%MAXQSIZE;
if (p->lchild)
{ Q.base[Q.rear]=p->lchild;
Q.rear=(Q.rear+1)%MAXQSIZE;}
if (p->rchild)
{ Q.base[Q.rear]=p->rchild;
Q.rear=(Q.rear+1)%MAXQSIZE;} } }
}
左右子树互换
void Exchange(BiTree &T)
{
BiTree S;
if (T) {
S=T->lchild;
T->lchild=T->rchild;
T->rchild=S;
Exchange(T->lchild);
Exchange(T->rchild);
}
}
复制二叉树
void CopyTree(BiTree T,BiTree &T1)
{ if (T)
{ T1=(BiTree)malloc(sizeof(BiTNode));
if (!T1) { printf("Overflow\n"); exit(1); }
T1->data=T->data;
T1->lchild=T1->rchild=NULL;
CopyTree(T->lchild,T1->lchild);
CopyTree(T->rchild,T1->rchild);
}
}
线索二叉树（穿线树、线索树）
(Threaded Binary Tree)
线索 (Thread),指向结点前驱和后继的指针若结点有左孩子，则 lchild指示其左孩子，否则 lchild
中存储该结点的前驱结点的指针；
若结点有右孩子，则 rchild指示其右孩子，否则 rchild
中存储指向该结点的后继结点的指针实质,对一个非线性结构进行线性化操作，使每个结点（除第一和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。
说明,在线索树中的前驱和后继是指按某种次序遍历所得到的序列中的前驱和后继。
概 念,(p132) 线索链表、线索、线索化、线索二叉树线索二叉树及其线索链表的表示标志域：
ltag = 0,lchild为左孩子指针
ltag = 1,lchild为 前驱线索
rtag = 0,rchild为右孩子指针
rtag = 1,rchild为 后继指针线索二叉树的存储表示 p133
typedef enum{Link,Thread}PointerTag;
//Link==0：指针，指向孩子结点
//Thread==1：线索，指向前驱或后继结点
typedef struct BiThrNode{
TElemType data;
struct BiThrNode *lchild,*rchild;
PointerTag LTag,RTag;
}BiThrNode,*BiThrTree;
BiThrTree T；
带表头结点的中序穿线链表从遍历的第一个结点来看：
先序序列中第一个结点必为根结点中、后序序列中第一个结点的左孩子定为空从遍历的最后一个结点来看：
先、中序序列中最后一个结点的右孩子必为空后序序列中最后一个结点一定为根结点作用：
对于遍历操作，线索树优于非线索树；
遍历线索树不用设栈步骤：
1)找遍历的第一个结点
2)不断地找遍历到的结点的后继结点，直到树中各结点都遍历到为止，结束。
遍历线索二叉树
if (current?RTag ==Thread)
后继为 current?rchild
else //current?RTag ==Link
后继为当前结点右子树的中序下的第一个结点寻找当前结点在中序下的后继
A
B
D E
C
F
H I
K
G
J
L
中序后继线索二叉树
DBGJEACHLKFI
if (current?LTag ==Thread)
前驱为 current?lchild
else //current?LTag ==Link
前驱为当前结点左子树的中序下的最后一个结点寻找当前结点在中序下的前驱
A
B
D E
C
F
H I
K
G
J
L
中序前驱线索二叉树中序序列,DBGJEACHLKFI
遍历中序线索二叉树 (不带头结点）
void inorder1_Thr(BiThrTree T)
{ BiThrTree p=T;
while (p->LTag==Link) p=p->lchild;
printf("%c",p->data);
while (p->rchild)
{ if (p->RTag==Link)
{ p=p->rchild;
while(p->LTag==Link) p=p->lchild;}
else p=p->rchild;
printf("%c",p->data);
}
}
void inorder2_Thr(BiThrTree T){
BiThrTree p=T;
while (p){
while (p->LTag==Link) p=p->lchild;
printf("%c",p->data);
while (p->RTag==Thread && p->rchild){
p=p->rchild;
printf("%c",p->data);}
p=p->rchild;
}
}
A
B
D E
C
F
H I
K
G
J
L
A
B
D E
C
F
H I
K
G
J
L
先序线索二叉树
ABDEGJCFHKLI
后序线索二叉树
DJGEBLKHIFCA
先序线索二叉树在先序线索二叉树中寻找当前结点的后继与前驱遍历先序线索二叉树 (不带头结点）
void preorder_Thr(BiThrTree T)
{ BiThrTree p=T;
printf("%c",p->data);
while (p->rchild)
{ if (p->LTag==Link) p=p->lchild;
else p=p->rchild;
printf("%c",p->data);
}
}
后序线索二叉树在后序线索化二叉树中寻找当前结点的后继遍历后序线索二叉树 (不带头结点）
void postorder_Thr(TriThrTree T)
{ TriThrTree f,p=T;
do { while (p->LTag==Link) p=p->lchild;
if (p->RTag==Link) p=p->rchild;
} while (p->LTag!=Thread || p-Tag!=Thread);
printf("%c",p->data);
while (p!=T)
{ if (p->RTag==Link)
{ f=p->parent;
if (f->RTag==Thread || p==f->rchild) p=f;
else { p=f->rchild;
do { while(p->LTag==Link) p=p->lchild;
if (p->RTag==Link) p=p->rchild;
}while (p->LTag!=Thread || p->RTag!=Thread);
}
}
else p=p->rchild;
printf("%c",p->data);
}
}
将未线索过的二叉树给予线索 —— 在遍历的前提下，按照先、中、后序中的一种
中 序线索化
后继线索化 —— 处理前驱结点
a,如果无前驱结点，则不必加线索
b,如果前驱结点的右指针域为非空，也不必加线索
c,如果前驱结点的右指针域为空，则把当前结点的指针值赋给前驱结点的右指针域。
二叉树的线索化
后继线索化 —— 处理前驱结点
void InThreading(BiThrTree P)
{ if (P)
{ InThreading(P->lchild);
if (!P->rchild) P->RTag=Thread;
if (pre & pre->RTag=Thread) pre->rchild=P;
pre=P;
InThreading(P->rchild);
}
}
前驱线索化 —— 处理后继结点
void InThreading(BiThrTree P)
{ if (P)
{ InThreading (P->lchild);
if (!P->lchild)
{ P->LTag=Thread; P->lchild=pre;}
pre=P;
InThreading(P->rchild);
}
}
通过中序遍历建立中序线索化二叉树
P135算法 6.7
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);
}
}
P134 算法 6.6 （设定一个表头结点）
注：指针 pre始终指向当前访问结点的前驱结点
int InOrderThreading(BiThrTree &Thrt,BiThrTree T){
if (!(Thrt =
(BiThrTree)malloc(sizeof(BiThrNode))))
exit(OVERFLOW);
Thrt->LTag = Link; Thrt->RTag=Thread;
Thrt->rchild=Thrt;
if (!T) Thrt->lchild = Thrt;
else {
Thrt->lchild=T; pre=Thrt;
InThreading(T);
pre->rchild = Thrt; pre->RTag=Thread;
Thrt->rchild = pre;
}return OK;
}
中序线索化
void InThreading2 (BiThrTree P){
if (P){
InThreading2 (P->lchild);
if (!P->lchild){
P->LTag=Thread; P->lchild=pre;}
if (!P->rchild) P->RTag=Thread;
if (pre&&pre->RTag==Thread){ pre-
>rchild=P;}
pre=P;
InThreading2 (P->rchild);
}
}
先序线索化
void PreThreading(BiThrTree P)
{ if (P)
{ if (!P->lchild)
{ P->LTag=Thread;P->lchild=pre;}
if (!P->rchild) P->RTag=Thread;
if (pre && pre->RTag==Thread) pre->rchild=P;
pre=P;
if (P->LTag==Link) PreThreading(P->lchild);
if (P->RTag==Link) PreThreading(P->rchild);
}
}
后序线索化
void PostThreading(TriThrTree P)
{ if (P)
{ PostThreading(P->lchild);
PostThreading(P->rchild);
if (!P->lchild)
{ P->LTag=Thread; P->lchild=pre;}
if (!P->rchild) P->RTag=Thread;
if (preT && preT->RTag==Thread) pre->rchild=P;
pre=P;
}
}
1,树的存储结构
6.4 树和森林
1)多重链表（标准存储结构）
定长结构 （ n为树的度）指针利用率不高
不定长结构 d为结点的度，节省空间，但算法复杂
一般采用定长结构
如有 n个结点，树的度为 k，则共有 n*k个指针域，只有 n-1
个指针域被利用，而未利用的指针域为,n*k-(n-1) =n(k-
1)+1，未利用率为,( n(k-1)+1)/nk > n(k-1)/nk=(k-1)/k
二次树,1/2 ；三次树,2/3 ；四次树,3/4
树的度越高，未利用率越高，由于二叉树的利用率较其他树高，因此用二叉树。
data
data child1 child2 child3 childn
d child2 child3 childd
2)常用的其他几种存储结构
双亲表示法 p135
用结构数组 —— 树的顺序存储方式
类型定义,p135
找双亲方便，找孩子难
孩子链表表示法 p136
顺序和链式结合的表示方法
找孩子方便，找双亲难
若用 p137图 6.14中带双亲的孩子链表表示，则找孩子找双亲都较方便
孩子兄弟表示法 p136
找孩子容易，若增加 parent域，则找双亲也较方便。
双亲表示
#define MAX_TREE_SIZE 100
typedef struct PTNode{
TElemType data;
int parent;
} PTNode;
typedef struct{
PTNode nodes[MAX_TREE_SIZE]；
int r,n; //根位置和结点数
}PTree;
孩子兄弟表示法（二叉链表表示法）
树的左孩子 -右兄弟表示
data firstChild nextSibling
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
2,森林与二叉树的转换森林与二叉树的对应关系
(1) 树转化成二叉树的简单方法
① 在同胞兄弟之间加连线；
② 保留结点与第一个孩子之间的连线，去掉其余连线；
③ 顺时针旋转 45度。
以根结点为轴；左孩子不再旋转。
森林转化成二叉树
① 将森林中的每棵树转换成对应的二叉树；
② 将森林中已经转换成的二叉树的各个根视为兄弟，
各兄弟之间自第一棵树根到最后一棵树根之间加连线；
③ 以第一棵树的根为轴，顺时针旋转 45度。
(2) 森林转化成二叉树的规则
若 F为空,即 n = 0，则对应的二叉树 B为空二叉树。
若 F不空,则对应二叉树 B的 根 root (B)是 F中第一棵树 T1
的根 root (T1)；
其 左子树为 B (T11,T12,…,T1m)，其中,T11,
T12,…,T1m是 root (T1)的子树；
其 右子树为 B (T2,T3,…,Tn)，其中,T2,
T3,…,Tn是除 T1外其它树构成的森林。
(3) 二叉树转换为森林的规则
如果 B为空,则对应的森林 F也为空。
如果 B非空,则
F中第一棵树 T1的根为 root；
T1的根的子树森林 { T11,T12,…,T1m }是由
root 的左子树 LB 转换而来,F中除了 T1 之外其余的树组成的森林 { T2,T3,…,Tn } 是由 root
的右子树 RB 转换而成的森林。
3,树和森林的遍历树的遍历（先根遍历、后根遍历、层次遍历）
（ 1）先根遍历：先根访问树的根结点，然后依次先根遍历根的每棵子树
（ 2）后根遍历：先依次后根遍历每棵子树，然后访问根结点树的先根遍历 转换后的二叉树的先序遍历树的后根遍历 转换后的二叉树的中序遍历森林的遍历先序：对应二叉树的先序遍历后序：对应二叉树的后序遍历森林的遍历森林的二叉树表示
(1) 先根次序遍历的规则：
若森林 F为空,返回；
否则
访问 F的第一棵树的根结点；
先根次序遍历第一棵树的子树森林；
先根次序遍历其它树组成的森林。
森林的遍历森林的二叉树表示
(2) 中根次序遍历的规则：
若森林 F为空，返回；
否则
中根次序遍历第一棵树的子树森林；
访问 F的第一棵树的根结点；
中根次序序遍历其它树组成的森林。
森林的遍历森林的二叉树表示
(3) 后根次序遍历的规则：
若森林 F为空，返回；
否则
后根次序遍历第一棵树的子树森林；
后根次序遍历其它树组成的森林；
访问 F的第一棵树的根结点 。
。
森林的遍历森林的二叉树表示
(4) 广度优先遍历 (层次序遍历 ),
若森林 F为空，返回；
否则
依次遍历各棵树的根结点；
依次遍历各棵树根结点的所有孩子；
依次遍历这些孩子结点的孩子结点 。?
具有不同路径长度的二叉树
6.6 赫夫曼树 (Huffman Tree)及其应用 p144
路径长度 (Path Length)
两个结点之间的路径长度 是连接两结点的路径上的分支数。 树的路径长度 是各结点到根结点的路径长度之和。
n个结点的二叉树的路径长度不小于下述数列前
n项的和，即其路径长度最小者为
n
i
iPL
1
2l o g
带权路径长度 ( Weighted Path Length,WPL )
树的带权路径长度是树的各 叶结点 所带的权值与该结点到根的路径长度的乘积的和。
n
i
ii lwW P L
1
n
i
iPL
1
2l o g
332222110
具有不同带权路径长度的扩充二叉树赫夫曼树带权路径长度达到最小的二叉树即为赫夫曼树
（最优二叉树）。
在赫夫曼树中，权值大的结点离根最近。
赫夫曼树的应用
在解决某些判定问题时，利用赫夫曼树可以得到最佳判定算法 p145图 6.23
用于通讯和数据传送时的赫夫曼编码
任一字符的编码都 不是 另一字符编码的前缀，
称为前缀编码。 p146
赫夫曼算法
—— 如何构造一棵赫夫曼树
(1) 由给定的 n个权值 {w0,w1,w2,…,wn-1}，构造具有 n棵二叉树的森林 F = {T0,T1,T2,…,Tn-1}，其中每一棵二叉树 Ti只有一个带有权值 wi的根结点，
其左、右子树均为空。
(2) 重复以下步骤,直到 F中仅剩下一棵树为止：
① 在 F中选取两棵根结点的权值最小的二叉树,
做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
② 在 F中删去这两棵二叉树。
③ 把新的二叉树加入 F。
赫夫曼树的构造过程赫夫曼编码主要用途是实现数据压缩。
设给出一段报文：
CAST CAST SAT AT A TASA
字符集合是 { C,A,S,T }，各个字符出现的频度 (次数 )是 W＝ { 2,7,4,5 }。
若给每个字符以等长编码
A,00 T,10 C,01 S,11
则总编码长度为 ( 2+7+4+5 ) * 2 = 36.
若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。
因各字符出现的概率为 { 2/18,7/18,4/18,5/18}。
化整为 { 2,7,4,5 }，以它们为各叶结点上的权值，
建立赫夫曼树。左分支赋 0，右分支赋 1，得赫夫曼编码 (变长编码 )。
A,0 T,10 C,110 S,111
它的总 编码长度,7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。
总编码长度正好等于赫夫曼树的带权路径长度 WPL。
赫夫曼编码是一种 无前缀的编码 。解码时不会混淆。
赫夫曼编码树
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{ HuffmanTree p; char *cd; int i,s1,s2,start;
unsigned int c,f;
if (n<=1) return; // n为字符树木,m为结点树木
int m=2*n-1;
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
// 0号单元未用建立赫夫曼树及求赫夫曼编码的算法
(p147算法 6.12)
for (p=HT,i=1; i<=n; ++i,++p,++w)
{ p->weight = *w; p->parent=0; p->lchild=0;p->rchild=0; }
// *p = { *w,0,0,0 };
for (; i<=m;++i,++p)
{ p->weight = 0; p->parent=0; p->lchild=0; p->rchild=0; }
//*p={ 0,0,0,0 };
for (i=n+1; i<=m;++i) // 建赫夫曼树
{ 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= (HuffmanCode)malloc((n+1)*sizeof(char *));
cd = (char*)malloc(n*sizeof(char));
cd[n-1]='\0';
for (i=1;i<=n;++i)
{ start = n-1;
for (c=i,f=HT[c].parent; f!=0; c=f,f=HT[f].parent)
if (HT[f].lchild ==c) cd[--start]='0';
else cd[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
printf("%s\n",HC[i]);
}
free(cd);
}
二叉树的存储结构遍历二叉树 (Binary Tree Traversal)
线索化二叉树 (Threaded Binary Tree)
树与森林 (Tree & Forest)
赫夫曼树 (Huffman Tree)
二叉树的计数
6.1 树的定义和基本术语
1,树的定义树是由 n (n? 0)个结点组成的有限集合。
如果 n = 0，称为空树；
如果 n > 0，则,
有一个特定的称之为 根 (root)的结点，它只有后继，但没有前驱；
除根以外的其它结点划分为 m (m? 0)个互不相交的有限集合 T0,T1,…,Tm-1，每个集合本身又是一棵树，并且称之为根的 子树 (subTree)。每棵子树的根结点有且仅有一个 直接 前驱，但可以有
0个或多个后继。
结点 (node)
结点的度 (degree)
分支 (branch)结点
叶 (leaf)结点
孩子 (child)结点
双亲 (parent)结点
兄弟 (sibling)结点
祖先 (ancestor)结点
子孙 (descendant)结点
结点所处层次 (level)
树的深度 (depth)
树的度 (degree)
有序树
无序树
森林
1）度（次数、级）
（ 1）结点的度：一个结点所拥有的子数的个数
（ 2）树的度：树内各结点的度的最大值
2）描述上下及左右的关系孩子结点：一个结点的子树的根双亲结点,P120
兄弟结点：同一个双亲的孩子之间互称兄弟祖先：结点的祖先是从根到该结点所经分支上的所有结点子孙,P120结点的后代
3）层次
（ 1）结点的层次
（ 2）树的深度（高度）
2,树的基本术语树的基本操作,p119
树的建立和遍历 —— 重点树的抽象数据类型
6.2 二叉树 (Binary Tree)
二叉树的定义二叉树的五种不同形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
特点,1）每个结点的度 ≤2； 2）是有序树基本操作,p121~p123
二叉树的建立和遍历二叉树的抽象数据类型性质 1 若二叉树的层次从 1开始,则在二叉树的第 i 层最多有 2i-1个结点。 (i? 1)
[证明用数学归纳法 ]
性质 2 深度为 k的二叉树最多有 2k-1个结点。
(k? 1)
[证明用求等比级数前 k项和的公式 ]
性质 3 对任何一棵二叉树,如果其叶结点个数为
n0,度为 2的非叶结点个数为 n2,则有
n0＝ n2＋ 1
二叉树的性质证明,若设度为 1的结点有 n1个，总结点个数为 n，总边数为 e，则根据二叉树的定义，
n = n0 + n1 + n2 e = 2n2 + n1 = n - 1
因此，有 2n2 + n1 = n0 + n1 + n2 - 1
n2 = n0 - 1 n0 = n2 + 1
同理：
三次树,n0=1+n2+2n3
四次树,n0=1+n2+2n3+3n4
…
K次树,n0=1+n2+2n3+…+(k -1)nk
定义 1 满二叉树 (Full Binary Tree)
定义 2 完全二叉树 (Complete Binary Tree)
若设二叉树的深度为 h，则共有 h层。除第 h层外，其它各层 (0?h-1)的结点数都达到最大个数，
第 h层从右向左连续缺若干结点，这就是完全二叉树。
性质 4 具有 n个结点的完全二叉树的深度为
log2n? +1
证明,设完全二叉树的深度为 k，则有
2k-1 - 1 < n? 2k - 1 2k-1? n < 2k
取对数 k-1? log2n < k
因为 k为整数，所以 k =?log2n? +1
说明：常出现在选择题中性质 5 如果将一棵有 n个结点的完全二叉树的结点按层序 (自顶向下，同一层自左向右）连续编号 1,2,…,n，然后按此结点编号将树中各结点顺序地存放于一个一维数组中,并简称编号为 i的结点为结点 i (1? i? n)。则有以下关系：
若 i == 1,则 i 是二叉树的根，无双亲若 i > 1,则 i 的双亲为?i /2?
若 2*i≤ n,则 i 的左孩子为 2*i，否则无左孩子若 2*i+1 ≤ n,则 i 的右孩子为 2*i+1，否则无右孩子
若 i 为偶数,且 i != n,则其右兄弟为 i+1
若 i 为奇数,且 i != 1,则其左兄弟为 i-1
i 所在层次为?log2 i? +1
完全二叉树的数组表示 一般二叉树的数组表示二叉树的存储结构
1,顺序存储结构（数组表示）
#define MAX_TREE_SIZE 100
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;
由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。
单支树
2.链式存储结构
typedef struct BiTNode{ //二叉链表的定义
TElemType data;
Struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
二叉树链表表示的示例
3,静态二叉链表和静态三叉链表预先开辟空间，用数组表示
leftChild,rightChild—— 数组元素的下标
6.3 遍历二叉树
(Traversing Binary Tree) p128
所谓树的遍历，就是按某种次序访问树中的结点，
要求每个结点访问一次且仅访问一次。
遍历的结果,产生一个关于结点的线性序列。
设 访问根结点 记作 D
遍历根的左子树 记作 L
遍历根的右子树 记作 R
则可能的遍历次序有先序 DLR DRL 逆先序中序 LDR RDL 逆中序后序 LRD RLD 逆后序先序遍历 (Preorder Traversal)
先序遍历二叉树算法的框架是
若二叉树为空，则空操作；
否则
访问根结点 (D)；
先序遍历左子树 (L)；
先序遍历右子树 (R)。
遍历结果（前缀表达式）
- + a * b - c d / e f
在波兰式中，自左到右依次扫描：连续出现 2
个操作数时，将其前面的运算符退出，对该两操作数进行这两个操作数前面的运算符的运算，
运算的中间结果进栈，
然后再进行上述的操作。
先序遍历二叉树的递归算法
void PreOrderTraverse(BiTree T){
if (T){
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
中序遍历二叉树算法的框架是：
若二叉树为空，则空操作；
否则
中序遍历左子树 (L)；
访问根结点 (D)；
中序遍历右子树 (R)。
遍历结果（中缀表达式）
a + b * c - d - e / f
中序遍历 (Inorder Traversal)
表达式语法树中序遍历二叉树的递归算法
void InOrderTraverse(BiTree T){
if (T) {
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
}
后序遍历 (Postorder Traversal)
后序遍历二叉树算法的框架是
若二叉树为空，则空操作；
否则
后序遍历左子树 (L)；
后序遍历右子树 (R)；
访问根结点 (D)。
在逆波兰式中，自左到右依次扫描：是操作数，
则依次进栈；遇到运算符。则退出两个操作数，
对该两操作数进行该运算符的运算，运算的中间结果进栈；然后再继续重复上述的操作。
遍历结果（后缀表达式）
a b c d - * + e f / -
后序遍历二叉树的递归算法
void PostOrderTraverse(BiTree T){
if (T) {
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data);
}
}
由二叉树的先序序列和中序序列可唯一地确定一棵二叉树。 例,先序序列 { ABHFDECKG } 和 中序序列 { HBDFAEKCG },构造二叉树过程如下：
遍历二叉树的非递归算法
先序遍历：算法 1，将右子树根结点 入栈,(栈所需最大容量为 n/2+1)；算法 2将根结点入栈
中序遍历：在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈中弹出，访问，再遍历右子树
后序遍历：
1）设定一个指针，指向 最近访问过的结点。在退栈取出根结点时，需判断：若根结点的右子树为空，或它的右子树非空，但已遍历完毕，即它的右子树根结点恰好是最近一次访问过的结点时，应该遍历该根结点。反之，该根结点应重新入栈，先遍历它的右子树。
2）还可同时设定一个标记，指示该根结点是第一次还是第二次入栈
需用到栈，顺序栈的定义如下：
typedef BiTNode* SElemType;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
先序遍历的非递归算法
void preorder(BiTree T)
{ SqStack S; BiTree P=T;
InitStack(S); Push(S,NULL);
while (P)
{ printf("%c",P->data);
if (P->rchild)
Push(S,P->rchild);
if (P->lchild)
P=P->lchild;
else Pop(S,P);
}
}
先序遍历的非递归算法 2
void preorder(BiTree T){
int top=0;
BiTree stack[20],P=T;
do { while (P){
printf("%c",P->data);
stack[top]=P; top++;
P=P->lchild; }
if (top){
top--; P=stack[top];
P=P->rchild;}
}while (top || P);
}
中序遍历的非递归算法 1
void inorder(BiTree T){
SqStack S; BiTree P=T;
InitStack(S);
do{ while(P){
* (S.top) = P; S.top++;
P=P->lchild; }
if (S.top){
S.top--; P=*(S.top);
printf("%c",P->data);
P=P->rchild;}
}while((S.top!=S.base) || P);
}
中序遍历的非递归算法 2（ p131算法 6.3)
void inorder(BiTree T)
{ SqStack S; BiTree P=T;
InitStack(S);
while( P || !Empty(S))
{ if (P) { Push(S,P);
P=P->lchild; }
else { Pop(S,P);
printf("%c",P->data);
P=P->rchild;}
}
}
后序遍历时，每遇到一个结点，先把它推入栈中，让 PopTim=0。在遍历其左子树前，改结点的
PopTim=1，将其左孩子推入栈中。在遍历完左子树后，还不能访问该结点，必须继续遍历右子树，
此时改结点的 PopTim=2，并把其右孩子推入栈中。
在遍历完右子树后，结点才退栈访问。
后序遍历的非递归算法 1
void Postorder(BiTree T)
{ BiTree p=T,q=NULL;
SqStack S; InitStack(S); Push(S,p);
while (!StackEmpty(S))
{ if (p && p!=q) { Push(S,p); p=p->lchild; }
else { Pop(S,p);
if (!StackEmpty(S))
if (p->rchild && p->rchild!=q)
{ Push(S,p); p=p->rchild; }
else {printf("%c",p->data); q=p;}
}
}
}
后序遍历的非递归算法 2
void postorder(BiTree T)
{BiTree P=T,q; int flag; SqStack S; InitStack(S);
do {
while (P){ *(S.top)=P;S.top++;P=P->lchild;}
q=NULL; flag=1;
while ((S.top!=S.base) && flag)
{ P=*(S.top-1);
if (P->rchild == q)
{ printf("%c",P->data); S.top--; q=p;}
else { P=P->rchild; flag=0;}
}
}while ((S.top!=S.base));
}
先序建立二叉树的递归算法 (p131,算法 6.4)
Status CreateBiTree(BiTree &T)
{ char ch; scanf("%c",&ch);
if (ch==' ') T=NULL;
else { if (!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
二叉树的显示输出
void PrintBiTree(BiTree T,int n)
{
int i; char ch=' ';
if (T) {
PrintBiTree(T->rchild,n+1);
for (i=1;i<=n;++i) {printf("%5c",ch);}
printf("%c\n",T->data);
PrintBiTree(T->lchild,n+1);
}
}
说明：
1）遍历的第一个和最后一个结点第一个结点：
先序,根结点；
中序,沿着左链走，找到一个没有左孩子的结点；
后序,从根结点出发，沿着左链走，找到一个既没有左孩子又没有右孩子的结点。
最后一个结点：
中序,从根结点出发，沿着右链走，找到一个没有右孩子的结点；
后序,根结点。
先序：从根结点出发，沿着右链走，找到一个没有右孩子的结点；如果该结点有左孩子，再沿着其左孩子的右链走，以此类推，直到找到一个没有孩子的结点
求中序的第一个结点的算法：
P=T;
while (P->lchild) P=P->lchild;
printf(P->data);
求中序的最后一个结点的算法：
P=T；
while(P->rchild) P=P->rchild;
Printf(P->data);
2）先序 +中序 或 后序 +中序均可唯一地确定一棵二叉树
3）二叉树的二叉链表存储结构中，有 n+1个指针域未利用，已经使用的有 n-1个指针域，共有 2n个指针域利用二叉树 后序遍历 计算二叉树的深度
int Depth(BiTree T){
int depl,depr;
if (T){
depl=Depth(T->lchild);
depr=Depth(T->rchild);
if (depl>=depr) return (depl+1);
else return (depr+1);
}
return 0;
}
遍历二叉树的应用求二叉树结点个数
int Size(BiTree T)
{
if (T==NULL) return 0;
else return 1 + Size (T->lchild ) + Size ( T->rchild);
}
按层次遍历二叉树从根开始逐层访问，
用 FIFO队列实现。
typedef BiTNode* ElemType;
typedef struct{
QElemType *base;
int front,rear;
}SqQueue;
遍历顺序
void LevelOrderTraverse(BiTree T)
{ BiTree p; SqQueue Q; InitQueue(Q);
if (T){ Q.base[Q.rear]=T;
Q.rear=(Q.rear+1)%MAXQSIZE;
while (Q.front !=Q.rear)
{ p=Q.base[Q.front];
printf("%c",p->data);
Q.front=(Q.front+1)%MAXQSIZE;
if (p->lchild)
{ Q.base[Q.rear]=p->lchild;
Q.rear=(Q.rear+1)%MAXQSIZE;}
if (p->rchild)
{ Q.base[Q.rear]=p->rchild;
Q.rear=(Q.rear+1)%MAXQSIZE;} } }
}
左右子树互换
void Exchange(BiTree &T)
{
BiTree S;
if (T) {
S=T->lchild;
T->lchild=T->rchild;
T->rchild=S;
Exchange(T->lchild);
Exchange(T->rchild);
}
}
复制二叉树
void CopyTree(BiTree T,BiTree &T1)
{ if (T)
{ T1=(BiTree)malloc(sizeof(BiTNode));
if (!T1) { printf("Overflow\n"); exit(1); }
T1->data=T->data;
T1->lchild=T1->rchild=NULL;
CopyTree(T->lchild,T1->lchild);
CopyTree(T->rchild,T1->rchild);
}
}
线索二叉树（穿线树、线索树）
(Threaded Binary Tree)
线索 (Thread),指向结点前驱和后继的指针若结点有左孩子，则 lchild指示其左孩子，否则 lchild
中存储该结点的前驱结点的指针；
若结点有右孩子，则 rchild指示其右孩子，否则 rchild
中存储指向该结点的后继结点的指针实质,对一个非线性结构进行线性化操作，使每个结点（除第一和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。
说明,在线索树中的前驱和后继是指按某种次序遍历所得到的序列中的前驱和后继。
概 念,(p132) 线索链表、线索、线索化、线索二叉树线索二叉树及其线索链表的表示标志域：
ltag = 0,lchild为左孩子指针
ltag = 1,lchild为 前驱线索
rtag = 0,rchild为右孩子指针
rtag = 1,rchild为 后继指针线索二叉树的存储表示 p133
typedef enum{Link,Thread}PointerTag;
//Link==0：指针，指向孩子结点
//Thread==1：线索，指向前驱或后继结点
typedef struct BiThrNode{
TElemType data;
struct BiThrNode *lchild,*rchild;
PointerTag LTag,RTag;
}BiThrNode,*BiThrTree;
BiThrTree T；
带表头结点的中序穿线链表从遍历的第一个结点来看：
先序序列中第一个结点必为根结点中、后序序列中第一个结点的左孩子定为空从遍历的最后一个结点来看：
先、中序序列中最后一个结点的右孩子必为空后序序列中最后一个结点一定为根结点作用：
对于遍历操作，线索树优于非线索树；
遍历线索树不用设栈步骤：
1)找遍历的第一个结点
2)不断地找遍历到的结点的后继结点，直到树中各结点都遍历到为止，结束。
遍历线索二叉树
if (current?RTag ==Thread)
后继为 current?rchild
else //current?RTag ==Link
后继为当前结点右子树的中序下的第一个结点寻找当前结点在中序下的后继
A
B
D E
C
F
H I
K
G
J
L
中序后继线索二叉树
DBGJEACHLKFI
if (current?LTag ==Thread)
前驱为 current?lchild
else //current?LTag ==Link
前驱为当前结点左子树的中序下的最后一个结点寻找当前结点在中序下的前驱
A
B
D E
C
F
H I
K
G
J
L
中序前驱线索二叉树中序序列,DBGJEACHLKFI
遍历中序线索二叉树 (不带头结点）
void inorder1_Thr(BiThrTree T)
{ BiThrTree p=T;
while (p->LTag==Link) p=p->lchild;
printf("%c",p->data);
while (p->rchild)
{ if (p->RTag==Link)
{ p=p->rchild;
while(p->LTag==Link) p=p->lchild;}
else p=p->rchild;
printf("%c",p->data);
}
}
void inorder2_Thr(BiThrTree T){
BiThrTree p=T;
while (p){
while (p->LTag==Link) p=p->lchild;
printf("%c",p->data);
while (p->RTag==Thread && p->rchild){
p=p->rchild;
printf("%c",p->data);}
p=p->rchild;
}
}
A
B
D E
C
F
H I
K
G
J
L
A
B
D E
C
F
H I
K
G
J
L
先序线索二叉树
ABDEGJCFHKLI
后序线索二叉树
DJGEBLKHIFCA
先序线索二叉树在先序线索二叉树中寻找当前结点的后继与前驱遍历先序线索二叉树 (不带头结点）
void preorder_Thr(BiThrTree T)
{ BiThrTree p=T;
printf("%c",p->data);
while (p->rchild)
{ if (p->LTag==Link) p=p->lchild;
else p=p->rchild;
printf("%c",p->data);
}
}
后序线索二叉树在后序线索化二叉树中寻找当前结点的后继遍历后序线索二叉树 (不带头结点）
void postorder_Thr(TriThrTree T)
{ TriThrTree f,p=T;
do { while (p->LTag==Link) p=p->lchild;
if (p->RTag==Link) p=p->rchild;
} while (p->LTag!=Thread || p-Tag!=Thread);
printf("%c",p->data);
while (p!=T)
{ if (p->RTag==Link)
{ f=p->parent;
if (f->RTag==Thread || p==f->rchild) p=f;
else { p=f->rchild;
do { while(p->LTag==Link) p=p->lchild;
if (p->RTag==Link) p=p->rchild;
}while (p->LTag!=Thread || p->RTag!=Thread);
}
}
else p=p->rchild;
printf("%c",p->data);
}
}
将未线索过的二叉树给予线索 —— 在遍历的前提下，按照先、中、后序中的一种
中 序线索化
后继线索化 —— 处理前驱结点
a,如果无前驱结点，则不必加线索
b,如果前驱结点的右指针域为非空，也不必加线索
c,如果前驱结点的右指针域为空，则把当前结点的指针值赋给前驱结点的右指针域。
二叉树的线索化
后继线索化 —— 处理前驱结点
void InThreading(BiThrTree P)
{ if (P)
{ InThreading(P->lchild);
if (!P->rchild) P->RTag=Thread;
if (pre & pre->RTag=Thread) pre->rchild=P;
pre=P;
InThreading(P->rchild);
}
}
前驱线索化 —— 处理后继结点
void InThreading(BiThrTree P)
{ if (P)
{ InThreading (P->lchild);
if (!P->lchild)
{ P->LTag=Thread; P->lchild=pre;}
pre=P;
InThreading(P->rchild);
}
}
通过中序遍历建立中序线索化二叉树
P135算法 6.7
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);
}
}
P134 算法 6.6 （设定一个表头结点）
注：指针 pre始终指向当前访问结点的前驱结点
int InOrderThreading(BiThrTree &Thrt,BiThrTree T){
if (!(Thrt =
(BiThrTree)malloc(sizeof(BiThrNode))))
exit(OVERFLOW);
Thrt->LTag = Link; Thrt->RTag=Thread;
Thrt->rchild=Thrt;
if (!T) Thrt->lchild = Thrt;
else {
Thrt->lchild=T; pre=Thrt;
InThreading(T);
pre->rchild = Thrt; pre->RTag=Thread;
Thrt->rchild = pre;
}return OK;
}
中序线索化
void InThreading2 (BiThrTree P){
if (P){
InThreading2 (P->lchild);
if (!P->lchild){
P->LTag=Thread; P->lchild=pre;}
if (!P->rchild) P->RTag=Thread;
if (pre&&pre->RTag==Thread){ pre-
>rchild=P;}
pre=P;
InThreading2 (P->rchild);
}
}
先序线索化
void PreThreading(BiThrTree P)
{ if (P)
{ if (!P->lchild)
{ P->LTag=Thread;P->lchild=pre;}
if (!P->rchild) P->RTag=Thread;
if (pre && pre->RTag==Thread) pre->rchild=P;
pre=P;
if (P->LTag==Link) PreThreading(P->lchild);
if (P->RTag==Link) PreThreading(P->rchild);
}
}
后序线索化
void PostThreading(TriThrTree P)
{ if (P)
{ PostThreading(P->lchild);
PostThreading(P->rchild);
if (!P->lchild)
{ P->LTag=Thread; P->lchild=pre;}
if (!P->rchild) P->RTag=Thread;
if (preT && preT->RTag==Thread) pre->rchild=P;
pre=P;
}
}
1,树的存储结构
6.4 树和森林
1)多重链表（标准存储结构）
定长结构 （ n为树的度）指针利用率不高
不定长结构 d为结点的度，节省空间，但算法复杂
一般采用定长结构
如有 n个结点，树的度为 k，则共有 n*k个指针域，只有 n-1
个指针域被利用，而未利用的指针域为,n*k-(n-1) =n(k-
1)+1，未利用率为,( n(k-1)+1)/nk > n(k-1)/nk=(k-1)/k
二次树,1/2 ；三次树,2/3 ；四次树,3/4
树的度越高，未利用率越高，由于二叉树的利用率较其他树高，因此用二叉树。
data
data child1 child2 child3 childn
d child2 child3 childd
2)常用的其他几种存储结构
双亲表示法 p135
用结构数组 —— 树的顺序存储方式
类型定义,p135
找双亲方便，找孩子难
孩子链表表示法 p136
顺序和链式结合的表示方法
找孩子方便，找双亲难
若用 p137图 6.14中带双亲的孩子链表表示，则找孩子找双亲都较方便
孩子兄弟表示法 p136
找孩子容易，若增加 parent域，则找双亲也较方便。
双亲表示
#define MAX_TREE_SIZE 100
typedef struct PTNode{
TElemType data;
int parent;
} PTNode;
typedef struct{
PTNode nodes[MAX_TREE_SIZE]；
int r,n; //根位置和结点数
}PTree;
孩子兄弟表示法（二叉链表表示法）
树的左孩子 -右兄弟表示
data firstChild nextSibling
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
2,森林与二叉树的转换森林与二叉树的对应关系
(1) 树转化成二叉树的简单方法
① 在同胞兄弟之间加连线；
② 保留结点与第一个孩子之间的连线，去掉其余连线；
③ 顺时针旋转 45度。
以根结点为轴；左孩子不再旋转。
森林转化成二叉树
① 将森林中的每棵树转换成对应的二叉树；
② 将森林中已经转换成的二叉树的各个根视为兄弟，
各兄弟之间自第一棵树根到最后一棵树根之间加连线；
③ 以第一棵树的根为轴，顺时针旋转 45度。
(2) 森林转化成二叉树的规则
若 F为空,即 n = 0，则对应的二叉树 B为空二叉树。
若 F不空,则对应二叉树 B的 根 root (B)是 F中第一棵树 T1
的根 root (T1)；
其 左子树为 B (T11,T12,…,T1m)，其中,T11,
T12,…,T1m是 root (T1)的子树；
其 右子树为 B (T2,T3,…,Tn)，其中,T2,
T3,…,Tn是除 T1外其它树构成的森林。
(3) 二叉树转换为森林的规则
如果 B为空,则对应的森林 F也为空。
如果 B非空,则
F中第一棵树 T1的根为 root；
T1的根的子树森林 { T11,T12,…,T1m }是由
root 的左子树 LB 转换而来,F中除了 T1 之外其余的树组成的森林 { T2,T3,…,Tn } 是由 root
的右子树 RB 转换而成的森林。
3,树和森林的遍历树的遍历（先根遍历、后根遍历、层次遍历）
（ 1）先根遍历：先根访问树的根结点，然后依次先根遍历根的每棵子树
（ 2）后根遍历：先依次后根遍历每棵子树，然后访问根结点树的先根遍历 转换后的二叉树的先序遍历树的后根遍历 转换后的二叉树的中序遍历森林的遍历先序：对应二叉树的先序遍历后序：对应二叉树的后序遍历森林的遍历森林的二叉树表示
(1) 先根次序遍历的规则：
若森林 F为空,返回；
否则
访问 F的第一棵树的根结点；
先根次序遍历第一棵树的子树森林；
先根次序遍历其它树组成的森林。
森林的遍历森林的二叉树表示
(2) 中根次序遍历的规则：
若森林 F为空，返回；
否则
中根次序遍历第一棵树的子树森林；
访问 F的第一棵树的根结点；
中根次序序遍历其它树组成的森林。
森林的遍历森林的二叉树表示
(3) 后根次序遍历的规则：
若森林 F为空，返回；
否则
后根次序遍历第一棵树的子树森林；
后根次序遍历其它树组成的森林；
访问 F的第一棵树的根结点 。
。
森林的遍历森林的二叉树表示
(4) 广度优先遍历 (层次序遍历 ),
若森林 F为空，返回；
否则
依次遍历各棵树的根结点；
依次遍历各棵树根结点的所有孩子；
依次遍历这些孩子结点的孩子结点 。?
具有不同路径长度的二叉树
6.6 赫夫曼树 (Huffman Tree)及其应用 p144
路径长度 (Path Length)
两个结点之间的路径长度 是连接两结点的路径上的分支数。 树的路径长度 是各结点到根结点的路径长度之和。
n个结点的二叉树的路径长度不小于下述数列前
n项的和，即其路径长度最小者为
n
i
iPL
1
2l o g
带权路径长度 ( Weighted Path Length,WPL )
树的带权路径长度是树的各 叶结点 所带的权值与该结点到根的路径长度的乘积的和。
n
i
ii lwW P L
1
n
i
iPL
1
2l o g
332222110
具有不同带权路径长度的扩充二叉树赫夫曼树带权路径长度达到最小的二叉树即为赫夫曼树
（最优二叉树）。
在赫夫曼树中，权值大的结点离根最近。
赫夫曼树的应用
在解决某些判定问题时，利用赫夫曼树可以得到最佳判定算法 p145图 6.23
用于通讯和数据传送时的赫夫曼编码
任一字符的编码都 不是 另一字符编码的前缀，
称为前缀编码。 p146
赫夫曼算法
—— 如何构造一棵赫夫曼树
(1) 由给定的 n个权值 {w0,w1,w2,…,wn-1}，构造具有 n棵二叉树的森林 F = {T0,T1,T2,…,Tn-1}，其中每一棵二叉树 Ti只有一个带有权值 wi的根结点，
其左、右子树均为空。
(2) 重复以下步骤,直到 F中仅剩下一棵树为止：
① 在 F中选取两棵根结点的权值最小的二叉树,
做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
② 在 F中删去这两棵二叉树。
③ 把新的二叉树加入 F。
赫夫曼树的构造过程赫夫曼编码主要用途是实现数据压缩。
设给出一段报文：
CAST CAST SAT AT A TASA
字符集合是 { C,A,S,T }，各个字符出现的频度 (次数 )是 W＝ { 2,7,4,5 }。
若给每个字符以等长编码
A,00 T,10 C,01 S,11
则总编码长度为 ( 2+7+4+5 ) * 2 = 36.
若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。
因各字符出现的概率为 { 2/18,7/18,4/18,5/18}。
化整为 { 2,7,4,5 }，以它们为各叶结点上的权值，
建立赫夫曼树。左分支赋 0，右分支赋 1，得赫夫曼编码 (变长编码 )。
A,0 T,10 C,110 S,111
它的总 编码长度,7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。
总编码长度正好等于赫夫曼树的带权路径长度 WPL。
赫夫曼编码是一种 无前缀的编码 。解码时不会混淆。
赫夫曼编码树
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{ HuffmanTree p; char *cd; int i,s1,s2,start;
unsigned int c,f;
if (n<=1) return; // n为字符树木,m为结点树木
int m=2*n-1;
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
// 0号单元未用建立赫夫曼树及求赫夫曼编码的算法
(p147算法 6.12)
for (p=HT,i=1; i<=n; ++i,++p,++w)
{ p->weight = *w; p->parent=0; p->lchild=0;p->rchild=0; }
// *p = { *w,0,0,0 };
for (; i<=m;++i,++p)
{ p->weight = 0; p->parent=0; p->lchild=0; p->rchild=0; }
//*p={ 0,0,0,0 };
for (i=n+1; i<=m;++i) // 建赫夫曼树
{ 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= (HuffmanCode)malloc((n+1)*sizeof(char *));
cd = (char*)malloc(n*sizeof(char));
cd[n-1]='\0';
for (i=1;i<=n;++i)
{ start = n-1;
for (c=i,f=HT[c].parent; f!=0; c=f,f=HT[f].parent)
if (HT[f].lchild ==c) cd[--start]='0';
else cd[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
printf("%s\n",HC[i]);
}
free(cd);
}
