从对线性结构的研究过渡到对树形结构的研究，是数据结构课程学习的一次跃变。
6.1 树的定义和基本术语
1,树的定义树是由 n (n? 0)个结点组成的有限集合。
如果 n = 0，称为空树；
如果 n > 0，则,
有一个特定的称之为 根 (root)的结点，它只有后继，但没有前驱；
除根以外的其它结点划分为 m (m? 0)个互不相交的有限集合 T0,T1,…,Tm-1，每个集合本身又是一棵树，并且称之为根的 子树 (subTree)。每棵子树的根结点有且仅有一个 直接 前驱，但可以有
0个或多个后继。
(a)嵌套集合表示法 (b)括号表示法 (c)凹入表示法
1）度（次数、级）
（ 1）结点的度：一个结点所拥有的子数的个数
（ 2）树的度：树内各结点的度的最大值
2）描述上下及左右的关系孩子和双亲结点,某个结点的子树的根称为该结点的孩子，相应的，该结点称为其孩子的双亲。
兄弟结点：同一个双亲的孩子之间互称兄弟祖先：结点的祖先是从根到该结点所经分支上的所有结点。
子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。
2,树的基本术语树的基本操作,p119
树的建立和遍历 ——重点树的抽象数据类型：
3）层次
（ 1）结点的层次,规定根所在的层次为第 1层，根的孩子在第二层，依次类推。
（ 2）树的深度（高度）,树中结点最大的层数。
4）有序树：是指树中结点的各子树从左至右是有次序的，否则称为无序树。
森林：是指 n（ n≥0 ）棵互不相交的树的集合。
6.2 二叉树 (Binary Tree)
二叉树的定义二叉树的五种不同形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
特点,1）每个结点的度 ≤2； 2）是有序树二叉树 基本操作,p121
(1)createbitree(t) (2)destroybitree(t)
(3)root(t) (4)leftchild(t)
(5)rightchild(t) (6)locate(t,x)
(7)parent(t,x) (8)isempty(t)
(9)depth(t) (10)numofnode(t)
(11)addchild(t,x,t1,b) (12)deletechild(t,x,b)
(13)setnull(t) (14)isequal(t1,t2)
(15)preorder(t) (16)inorder(t)
(17)postorder(t) (18)transform(t1,t2)
二叉树的抽象数据类型二叉树是一种重要的树型结构，但二叉树不是树的特例。
二叉树的 5 种形态分别为,空二叉树，只有根结点的二叉树，根结点和左子树，根结点和右子树，根结点和左右子树。
二叉树与树的区别,二叉树中每个结点的孩子至多不超过两个，而树对结点的孩子数无限制；
另外，二叉树中结点的子树有左右之分，而树的子树没有次序。
性质 1 若二叉树的层次从 1开始,则在二叉树的第 i 层最多有 2i-1个结点。 (i? 1)
[证明用数学归纳法 ]
性质 2 深度为 k的二叉树最多有 2k-1个结点。
(k? 1)
[证明用求等比级数前 k项和的公式 ]
性质 3 对任何一棵二叉树,如果其叶结点个数为
n0,度为 2的非叶结点个数为 n2,则有
n0＝ n2＋ 1
二叉树的性质 （ P123）
证明：
若设度为 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
定义 1 满二叉树 (Full Binary Tree)
一棵深度为 k且有 2k -1个结点的二叉树称为满二叉树。
定义 2 完全二叉树 (Complete Binary Tree)
深度为 k，有 n个结点的二叉树，当且仅当其每一个结点都与深度为 k的满二叉树中编号从 1至
n的结点一一对应时，称之为完全二叉树。
或者：若设二叉树的深度为 h，则共有 h层。
除第 h层外，其它各层 (0?h-1)的结点数都达到最大个数，第 h层从右向左连续缺若干结点。
完全二叉树的特点是：
1） 只允许最后一层有空缺结点且空缺在右边,
即叶子结点只能在层次最大的两层上出现；
2）对任一结点，如果其右子树的深度为 j，则其左子树的深度必为 j或 j+1。
性质 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
二叉树的存储结构 (P126)
1,顺序存储结构 （数组表示）
顺序存储二叉树的具体方法是：在一棵具有 n个结点的完全二叉树中，从根结点开始编号为 1，自上到下，每层自左至右地给所有结点编号，这样可以得到一个反映整个二叉树结构的线性序列；然后将完全二叉树上编号为 i的结点依次存储在一维数组 a[l,.,n]中下标为 i的元素中。
完全二叉树的数组表示 一般二叉树的数组表示
#define MAX_TREE_SIZE 100
typedef TElemType
SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;
由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。
单支树
2.链式存储结构链式存储是使用链表来存储二叉树中的数据元素,
链表中的一个结点相应地存储二叉树中的一个结点 。 常见的二叉树的链式存储结构有两种：二叉链表和三叉链表 。。
二叉链表 是指链表中的每个结点包含两个指针域和一个数据域,分别用来存储指向二叉树中结点的左右孩子的指针及结点信息 。
三叉链表 是指链表中的每个结点包含三个指针域和一个数据域,相比二叉链表多出的一个指针域则用来指向该结点的双亲结点 。
不论哪种链表,头指针都指向二叉树的根结点 。
在含有 n个结点的二叉链表中，共有 2n个指针域，但实际有效的指针数等于二叉树中的分支数（即 n-1），所以共存在 n+1个空的指针域。
typedef struct BiTNode{ //二叉链表的定义
TElemType data;
Struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
二叉树链表表示的示例
3,静态二叉链表和静态三叉链表预先开辟空间，用数组表示
leftChild,rightChild—— 数组元素的下标
6.3 遍历二叉树
(Traversing Binary Tree) p144
所谓树的遍历，就是按某种次序访问树中的结点，
要求每个结点访问一次且仅访问一次。
遍历的结果,产生一个关于结点的线性序列。
设 访问根结点 记作 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）还可同时设定一个标记，指示该根结点是第一次还是第二次入栈先序遍历的非递归算法 1
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
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));
}
先序建立二叉树的递归算法
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);
}
复制二叉树
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);
}
}
左右子树互换
void Exchange(BiTree &T)
{
BiTree S;
if (T) {
S=T->lchild;
T->lchild=T->rchild;
T->rchild=S;
Exchange(T->lchild);
Exchange(T->rchild);
}
}
线索二叉树（穿线树、线索树）
(Threaded Binary Tree)
所谓 穿线二叉树,即在一般二叉树的基础上，对每个结点进行考察。若其左子树非空，则其左指针不变，仍指向左子女；若其左子树为空，则让其左指针指向某种遍历顺序下该结点的前驱；若其右子树非空，
则其右指针不变，仍指向右子女；若其右子树为空，
则让其右指针指向某种遍历顺序下该结点的后继。如果规定遍历顺序为前序，则称为 前序穿线二叉树 ；如果规定遍历顺序为中序，则称为 中序穿线二叉树 ；如果规定遍历顺序为后序，则称为 后序穿线二叉树 。
线索二叉树及其线索链表的表示标志域：
ltag = 0,lchild为左孩子指针
ltag = 1,lchild为 前驱线索
rtag = 0,rchild为右孩子指针
rtag = 1,rchild为 后继指针线索二叉树的存储表示
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);
}
}
说明：指针 pre 始终指向刚刚访问过的节点。
前驱线索化 —— 处理后继结点
void InThreading(BiThrTree P)
{ if (P)
{ InThreading (P->lchild);
if (!P->lchild)
{ P->LTag=Thread; P->lchild=pre;}
pre=P;
InThreading(P->rchild);
}
}
通过中序遍历建立中序线索化二叉树
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);
}
}
中序线索化
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)常用的其他几种存储结构
双亲表示法 p123
用结构数组 —— 树的顺序存储方式
类型定义,p123
找双亲方便，找孩子难
孩子链表表示法 p124
顺序和链式结合的表示方法
找孩子方便，找双亲难
孩子兄弟表示法 p127
找孩子容易，若增加 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的第一棵树的根结点 。
。
具有不同路径长度的二叉树
6.6 赫夫曼树 (Huffman Tree)及其应用路径长度 (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
具有不同带权路径长度的扩充二叉树赫夫曼树带权路径长度达到最小的二叉树即为赫夫曼树
（最优二叉树）。
在赫夫曼树中，权值大的结点离根最近。
赫夫曼树的应用
在解决某些判定问题时，利用赫夫曼树可以得到最佳判定算法
用于通讯和数据传送时的赫夫曼编码任一字符的编码都 不是 另一字符编码的前缀，
称为前缀编码。
赫夫曼算法
——如何构造一棵赫夫曼树
(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号单元未用
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);
}
例 1：假设一棵二叉树的先序序列为 EBADCFHGIKJ，
中序序列为 ABCDEFGHIJK，请写出该二叉树的后序遍历序列。
例 2：给定一组权值（ 5,9,11,2,7,16），试设计相应的哈夫曼树。
例 1答案,后序序列,ACDBGJKIHFE
例 2答案,构造而成的哈夫曼树思考题：
1,一棵度为 2的树与一棵二叉树有何区别。
2,已知用一维数组存放的一棵完全二叉树：
ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。
3,假设一棵二叉树的先序序列为 EBADCFHGIKJ，中序序列为 ABCDEFGHIJK，请写出该二叉树的后序遍历序列。
4,给定一组权值（ 5,9,11,2,7,16），试设计相应的哈夫曼树。
5,给定一棵用二叉链表表示的二叉树，其中的指针 t指向根结点，试写出从根开始，按层次遍历二叉树的算法，同层的结点按从左至右的次序访问。
6.1 树的定义和基本术语
1,树的定义树是由 n (n? 0)个结点组成的有限集合。
如果 n = 0，称为空树；
如果 n > 0，则,
有一个特定的称之为 根 (root)的结点，它只有后继，但没有前驱；
除根以外的其它结点划分为 m (m? 0)个互不相交的有限集合 T0,T1,…,Tm-1，每个集合本身又是一棵树，并且称之为根的 子树 (subTree)。每棵子树的根结点有且仅有一个 直接 前驱，但可以有
0个或多个后继。
(a)嵌套集合表示法 (b)括号表示法 (c)凹入表示法
1）度（次数、级）
（ 1）结点的度：一个结点所拥有的子数的个数
（ 2）树的度：树内各结点的度的最大值
2）描述上下及左右的关系孩子和双亲结点,某个结点的子树的根称为该结点的孩子，相应的，该结点称为其孩子的双亲。
兄弟结点：同一个双亲的孩子之间互称兄弟祖先：结点的祖先是从根到该结点所经分支上的所有结点。
子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。
2,树的基本术语树的基本操作,p119
树的建立和遍历 ——重点树的抽象数据类型：
3）层次
（ 1）结点的层次,规定根所在的层次为第 1层，根的孩子在第二层，依次类推。
（ 2）树的深度（高度）,树中结点最大的层数。
4）有序树：是指树中结点的各子树从左至右是有次序的，否则称为无序树。
森林：是指 n（ n≥0 ）棵互不相交的树的集合。
6.2 二叉树 (Binary Tree)
二叉树的定义二叉树的五种不同形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
特点,1）每个结点的度 ≤2； 2）是有序树二叉树 基本操作,p121
(1)createbitree(t) (2)destroybitree(t)
(3)root(t) (4)leftchild(t)
(5)rightchild(t) (6)locate(t,x)
(7)parent(t,x) (8)isempty(t)
(9)depth(t) (10)numofnode(t)
(11)addchild(t,x,t1,b) (12)deletechild(t,x,b)
(13)setnull(t) (14)isequal(t1,t2)
(15)preorder(t) (16)inorder(t)
(17)postorder(t) (18)transform(t1,t2)
二叉树的抽象数据类型二叉树是一种重要的树型结构，但二叉树不是树的特例。
二叉树的 5 种形态分别为,空二叉树，只有根结点的二叉树，根结点和左子树，根结点和右子树，根结点和左右子树。
二叉树与树的区别,二叉树中每个结点的孩子至多不超过两个，而树对结点的孩子数无限制；
另外，二叉树中结点的子树有左右之分，而树的子树没有次序。
性质 1 若二叉树的层次从 1开始,则在二叉树的第 i 层最多有 2i-1个结点。 (i? 1)
[证明用数学归纳法 ]
性质 2 深度为 k的二叉树最多有 2k-1个结点。
(k? 1)
[证明用求等比级数前 k项和的公式 ]
性质 3 对任何一棵二叉树,如果其叶结点个数为
n0,度为 2的非叶结点个数为 n2,则有
n0＝ n2＋ 1
二叉树的性质 （ P123）
证明：
若设度为 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
定义 1 满二叉树 (Full Binary Tree)
一棵深度为 k且有 2k -1个结点的二叉树称为满二叉树。
定义 2 完全二叉树 (Complete Binary Tree)
深度为 k，有 n个结点的二叉树，当且仅当其每一个结点都与深度为 k的满二叉树中编号从 1至
n的结点一一对应时，称之为完全二叉树。
或者：若设二叉树的深度为 h，则共有 h层。
除第 h层外，其它各层 (0?h-1)的结点数都达到最大个数，第 h层从右向左连续缺若干结点。
完全二叉树的特点是：
1） 只允许最后一层有空缺结点且空缺在右边,
即叶子结点只能在层次最大的两层上出现；
2）对任一结点，如果其右子树的深度为 j，则其左子树的深度必为 j或 j+1。
性质 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
二叉树的存储结构 (P126)
1,顺序存储结构 （数组表示）
顺序存储二叉树的具体方法是：在一棵具有 n个结点的完全二叉树中，从根结点开始编号为 1，自上到下，每层自左至右地给所有结点编号，这样可以得到一个反映整个二叉树结构的线性序列；然后将完全二叉树上编号为 i的结点依次存储在一维数组 a[l,.,n]中下标为 i的元素中。
完全二叉树的数组表示 一般二叉树的数组表示
#define MAX_TREE_SIZE 100
typedef TElemType
SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;
由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。
单支树
2.链式存储结构链式存储是使用链表来存储二叉树中的数据元素,
链表中的一个结点相应地存储二叉树中的一个结点 。 常见的二叉树的链式存储结构有两种：二叉链表和三叉链表 。。
二叉链表 是指链表中的每个结点包含两个指针域和一个数据域,分别用来存储指向二叉树中结点的左右孩子的指针及结点信息 。
三叉链表 是指链表中的每个结点包含三个指针域和一个数据域,相比二叉链表多出的一个指针域则用来指向该结点的双亲结点 。
不论哪种链表,头指针都指向二叉树的根结点 。
在含有 n个结点的二叉链表中，共有 2n个指针域，但实际有效的指针数等于二叉树中的分支数（即 n-1），所以共存在 n+1个空的指针域。
typedef struct BiTNode{ //二叉链表的定义
TElemType data;
Struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
二叉树链表表示的示例
3,静态二叉链表和静态三叉链表预先开辟空间，用数组表示
leftChild,rightChild—— 数组元素的下标
6.3 遍历二叉树
(Traversing Binary Tree) p144
所谓树的遍历，就是按某种次序访问树中的结点，
要求每个结点访问一次且仅访问一次。
遍历的结果,产生一个关于结点的线性序列。
设 访问根结点 记作 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）还可同时设定一个标记，指示该根结点是第一次还是第二次入栈先序遍历的非递归算法 1
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
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));
}
先序建立二叉树的递归算法
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);
}
复制二叉树
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);
}
}
左右子树互换
void Exchange(BiTree &T)
{
BiTree S;
if (T) {
S=T->lchild;
T->lchild=T->rchild;
T->rchild=S;
Exchange(T->lchild);
Exchange(T->rchild);
}
}
线索二叉树（穿线树、线索树）
(Threaded Binary Tree)
所谓 穿线二叉树,即在一般二叉树的基础上，对每个结点进行考察。若其左子树非空，则其左指针不变，仍指向左子女；若其左子树为空，则让其左指针指向某种遍历顺序下该结点的前驱；若其右子树非空，
则其右指针不变，仍指向右子女；若其右子树为空，
则让其右指针指向某种遍历顺序下该结点的后继。如果规定遍历顺序为前序，则称为 前序穿线二叉树 ；如果规定遍历顺序为中序，则称为 中序穿线二叉树 ；如果规定遍历顺序为后序，则称为 后序穿线二叉树 。
线索二叉树及其线索链表的表示标志域：
ltag = 0,lchild为左孩子指针
ltag = 1,lchild为 前驱线索
rtag = 0,rchild为右孩子指针
rtag = 1,rchild为 后继指针线索二叉树的存储表示
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);
}
}
说明：指针 pre 始终指向刚刚访问过的节点。
前驱线索化 —— 处理后继结点
void InThreading(BiThrTree P)
{ if (P)
{ InThreading (P->lchild);
if (!P->lchild)
{ P->LTag=Thread; P->lchild=pre;}
pre=P;
InThreading(P->rchild);
}
}
通过中序遍历建立中序线索化二叉树
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);
}
}
中序线索化
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)常用的其他几种存储结构
双亲表示法 p123
用结构数组 —— 树的顺序存储方式
类型定义,p123
找双亲方便，找孩子难
孩子链表表示法 p124
顺序和链式结合的表示方法
找孩子方便，找双亲难
孩子兄弟表示法 p127
找孩子容易，若增加 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的第一棵树的根结点 。
。
具有不同路径长度的二叉树
6.6 赫夫曼树 (Huffman Tree)及其应用路径长度 (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
具有不同带权路径长度的扩充二叉树赫夫曼树带权路径长度达到最小的二叉树即为赫夫曼树
（最优二叉树）。
在赫夫曼树中，权值大的结点离根最近。
赫夫曼树的应用
在解决某些判定问题时，利用赫夫曼树可以得到最佳判定算法
用于通讯和数据传送时的赫夫曼编码任一字符的编码都 不是 另一字符编码的前缀，
称为前缀编码。
赫夫曼算法
——如何构造一棵赫夫曼树
(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号单元未用
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);
}
例 1：假设一棵二叉树的先序序列为 EBADCFHGIKJ，
中序序列为 ABCDEFGHIJK，请写出该二叉树的后序遍历序列。
例 2：给定一组权值（ 5,9,11,2,7,16），试设计相应的哈夫曼树。
例 1答案,后序序列,ACDBGJKIHFE
例 2答案,构造而成的哈夫曼树思考题：
1,一棵度为 2的树与一棵二叉树有何区别。
2,已知用一维数组存放的一棵完全二叉树：
ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。
3,假设一棵二叉树的先序序列为 EBADCFHGIKJ，中序序列为 ABCDEFGHIJK，请写出该二叉树的后序遍历序列。
4,给定一组权值（ 5,9,11,2,7,16），试设计相应的哈夫曼树。
5,给定一棵用二叉链表表示的二叉树，其中的指针 t指向根结点，试写出从根开始，按层次遍历二叉树的算法，同层的结点按从左至右的次序访问。
