第5章 树和二叉树 5．1树 5．2二叉树 5．3二叉树的遍历 5．4线索二叉树 5．5树、森林与二叉树的转换 5．6哈夫曼树

5．1 树 5．1．1树的定义及基本术语 1、树的定义 树是n(n≥0)个结点的有限集T，n=0,为空树；n>0，满足： 5．1 树 5．1．1树的定义及基本术语 1、树的定义 　　树是n(n≥0)个结点的有限集T，n=0,为空树；n>0，满足： 　(1)有且仅有一个结点被称为根结点；　 　(2)当n>1时，除根结点以外的其余n-1个结点可以划分成m(m>0)个互不相交的有限集T1，T2，…，Tm，其中每一个集合本身又是一棵树，称为子树。

E F G H I J A C B D K L M 根结点 子树

2、基本术语 结点：树中的元素。 结点的度：结点拥有子树的数目。 叶子结点：度为0的结点。 分支结点：度不为0的结点。 孩子结点：结点的子树的根。 A D B F C E G I H

兄弟结点：具有同一双亲结点的孩子结点之间。 树的度：最大的结点度数。 双亲结点：孩子结点的上层结点。 兄弟结点：具有同一双亲结点的孩子结点之间。 树的度：最大的结点度数。 结点的层次：根为第一层，它的孩子为第二层…。结点的最大层次数为树的高度。 森林：m(m≥0)棵互不相交的树的集合。 有序树与无序树：树中结点的各子树从左至右有次序为有序树，否则为无序树。 A D B F C E G I H

B,C为A的孩子结点;A为B,C的双亲结点;B,C为兄弟结点 （ ）为分支结点，（ ）为叶子结点 B,C为A的孩子结点;A为B,C的双亲结点;B,C为兄弟结点 A D B F C E G I H

在树T中，由A结点的子树所构成的森林为(T1，T2)，由B结点的子树所构成的森林为(T11，T12，T13)。 D B F C E G I H A在1层，B,C在2层，树的高度为4； 在树T中，由A结点的子树所构成的森林为(T1，T2)，由B结点的子树所构成的森林为(T11，T12，T13)。

5．1．2树的表示 ①树形表示法 A D B F C E G I H

②文氏图表示法。使用集合以及集合的包含关系。

③凹入表示法。使用线段的伸缩关系。

④括号表示法。

5．1．3树的存储结构 1.双亲数组表示 Data：结点的数据值 Parent：双亲在数组中的下标 位置 0 1 2 3 4 5 6 7 8 … Data Parent A B C D E F G H I J … -1 1 2 3

2、孩子链表存储结构

3．孩子兄弟链表存储结构 两个指针对应第一个孩子和下一个兄弟。

5．2 二叉树 5．2．1二叉树的定义 二叉树是由n(n>=0)个结点的有限集合构成。此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。

二叉树的5种基本形态: 空树 只含根结点 左右子树均不为空树 N N 右子树为空树 左子树为空树 N N L R L R

3个结点的二叉树有5种不同形态:

5．2．2二叉树的性质 性质1：二叉树上叶子结点数等于度为2的结点数加1。 3 1 4 2 11 6 8 7 9 10 5

证明： n=n0+n1+n2 设b为分枝数，则n=b+1。 b=n1+2n2 n=n1+2n2+1 可得出： n0=n2+1

假定i=k，命题成立，至多有2k-1个结点。 当i=k+1，即2×2k-1＝2(k+1)-1。 命题成立。 性质2：在二叉树的第i层上至多有2i-1个结点(i>=1)。 证明：用数学归纳法证明。 当i=1时，2i-1=20 =1,命题成立。 假定i=k，命题成立，至多有2k-1个结点。 当i=k+1，即2×2k-1＝2(k+1)-1。 命题成立。

性质3：深度为h的二叉树至多有2h－1个结点（h>=1) 证明：由性质2，二叉树的第i层的最大结点数为：2i-1。

满二叉树： 在二叉树中，当第i层的结点数为2i-1个时，则称此层的结点数是满的，当一棵二叉中的每一层都满时，则称此树为满二叉树。 3 1 4 3 1 4 2 11 6 8 7 9 10 5 12 13 14

完全二叉树： 在二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干个结点，则称此树为完全二叉树。 3 3 1 4 2 11 6 8 7 9 10 5 3 1 4 2 6 8 7 9 10 5

性质4：具有n个结点的完全二叉树的高度为 (int)(log2n) +1。

k层完全二叉树，当总结点数最少时，总结点数n=(2k-1-1)+1。 当总结点数最多时，总结点数n=2k-1。 证明： k层完全二叉树，当总结点数最少时，总结点数n=(2k-1-1)+1。 当总结点数最多时，总结点数n=2k-1。 因此有：(2k-1-1)+1≤n≤2k-1 ∴ 2k-1≤n<2k 得k-1≤log2n<k。 ∴k= (int)(log2n) +1

性质5：对一棵含有n个结点的完全二叉树，如果按照从上至下、从左到右的顺序对树中所有结点从0开始顺序编号，则对于任意编号为i（0≤i≤n-1）的结点，有： (A)如果i>0，则结点i的双亲的编号为(int)((i-1)/2)；否则，结点i是完全二叉树的根结点，无双亲。 (B)如果2i+1<n，则结点i的左孩子的编号为2i+1；否则，结点i无左孩子。 (C)如果2i+2<n，则结点i的右孩子的编号为2i+2；否则，结点i无右孩子。

5．2．3二叉树的存储结构 1．顺序存储结构

/*顺序存储结构类型定义*/ typedef struct { BTreeDT *base; int spacesize; BTreeDT nullvalue; }SeqTree;

2、链式存储结构 1）二叉链表存储结构 typedef struct bkbtnode { BTreeDT data; struct bkbtnode *lchild; struct bkbtnode *rchild; }BTNode,*BKBTree; lchild data rchild

2）三叉链表存储结构 typedef struct tkbtnode { BTreeDT data; struct tkbtnode *lchild; struct tkbtnode *rchild; struct tkbtnode *parent; }TKBTNode,*TKBTree; lchild data parent rchild

5．2．4 二叉树的基本操作 1、二叉树基本运算 ①CreateBTree(bt,str) ②BTHeight(bt) ③NodeCount(bt) ④LeafCount(bt) ⑤DispBTree(bt) ⑥TravleTree(bt)

2、二叉树基本运算实现 求二叉树高度运算 int BTHeight(BTNode *bt) { int lchilddep,rchilddep; if(bt==NULL) return(0); /*空树的高度为0 */ else {lchilddep=BTHeight(bt->lchild);/*左子树的高度*/ rchilddep=BTHeight(bt->rchild);/*右子树的高度*/ return (lchilddep>rchilddep)? (lchilddep+1)：(rchilddep+1)； } }

求二叉树结点个数运算 int NodeCount(BTNode *bt) { int num1,num2; if(bt==NULL) return 0; else { num1=NodeCount( bt->lchild); num2=NodeCount(bt->rchild); return(num1+num2+1); } }

求二叉树叶子结点个数运算 int LeafCount(BTNode *bt) { int num1,num2; if(bt==NULL)return 0; else if(bt->lchild==NULL&&bt->rchild==NULL) return 1; else { num1=LeafCount(bt->lchild); num2=LeafCount(bt->rchild); return(num1+num2); }}

以括号表示法输出二叉树 void DispBTree(BTNode *bt) { if(bt!=NULL) { printf("%d",bt->data); if(bt->lchild!=NULL||bt->rchild!=NULL) { printf("("); DispBTree(bt->lchild);/*递归处理左子树*/ if(bt->rchild!=NULL) printf(","); DispBTree(bt->rchild);/*递归处理右子树*/ printf(")");}}}

5．3 二叉树的遍历 5.3.1 遍历定义 5.3.2 遍历方法 5.3.3 遍历应用

按一定规律对二叉树中的每个结点访问且仅访问一次。 5.3.1 遍历定义 按一定规律对二叉树中的每个结点访问且仅访问一次。 遍历 结点访问序列 非线性结构 线性排列

5.3.2遍历方法 二叉树的遍历顺序有： （1）访问根，遍历左子树，遍历右子树。 （2）访问根，遍历右子树，遍历左子树。 （3）遍历左子树，访问根，遍历右子树。 （4）遍历右子树，访问根，遍历左子树。 （5）遍历左子树，遍历右子树，访问根。 （6）遍历右子树，遍历左子树，访问根。 先序（根） 遍历 中序（根）遍历 后序（根）遍历

1、先序遍历 若二叉树非空，则： ①访问根结点； ②先序遍历左子树； ③先序遍历右子树。 先序遍历递归算法 PreOrder(BTNode root) {if(root!=NULL) { visit(root->data); PreOrder(root->lchild); PreOrder(root->rchild); }} 1、先序遍历 若二叉树非空，则： ①访问根结点； ②先序遍历左子树； ③先序遍历右子树。

先序遍历结果:ABDCEF

void PreOrder(BTNode *bt) {/*先序遍历二叉树非递归算法*/ BTNode *p=bt; while(!(p== NULL &&top== NULL)) { if(p!= NULL) { printf("%d",p->data); /*访问该结点*/ push(p); /*将当前指针p压栈*/ p=p->lchild; /*指针指向p的左孩子*/} else { pop(); p=p->rchild; /*指向p的右孩子结点*/ }}}

2、中序遍历 若二叉树非空，则： ①中序遍历左子树； ②访问根结点； ③中序遍历右子树。 中序遍历递归算法 void InOrder(BTNode root) {if(root!=NULL) {InOrder(root->lchild); visit(root->data); InOrder(root->rchild); }} 2、中序遍历 若二叉树非空，则： ①中序遍历左子树； ②访问根结点； ③中序遍历右子树。

中序遍历结果:BDAECF

void InOrder(BTNode *bt) { /*中序遍历二叉树非递归算法*/ BTNode *p=bt; int top; top=0; while(!(p==NULL&&top==NULL)) {while(p!=NULL) {push(p); /*将根结点压入栈中*/ p=p->lchild; /*指针指向p的左孩子*/} pop(); printf("%d\n",p->data); /*访问该结点*/ p=p->rchild; /*指针指向p的右孩子结点*/} }

3、后序遍历 若二叉树非空，则： ①后序遍历左子树； ②后序遍历右子树； ③访问根结点。 递归算法： void PostOrder(BTNode root) { if(root!=NULL) {PostOrder(root->lchild); PostOrder(root->rchild); visit(root->data); }} 3、后序遍历 若二叉树非空，则： ①后序遍历左子树； ②后序遍历右子树； ③访问根结点。

后序遍历结果:DBEFCA

{sign=pop(); pop(); if(sign==1) /*sign=1表示仅走过p的左子树*/ {push(p); /*第二次压入结点p的指针值*/ push(2); /*置标志为2*/ p=p->rchild; break; } else if(sign==2) /*sign=2表示p的左、右子树都已走过*/ {printf("%d",p->data);/*输出结点p的值*/ p=NULL; } }} while(p!=NULL||top!=NULL); } PostOrder(BTNode *bt) {/*后序遍历二叉树非递归算法*/ BTNode *p=bt; unsigned sign;/*设置标志记录结点从栈中弹出的次数*/ do{ if(p!=NULL) {push(p); /*第一次遇到结点p时压入其指针值*/ push(1); /*置标志为1*/ p=p->lchild; } else while(top!=NULL)

例：写出树的先序、中序、后序遍历。 先序序列： A B C D E F G H K A B C D E F G H K 中序序列： B D C A E H G K F 后序序列： D C B H K G F E A

4、层次遍历 ABCDEFGHI A B G H D C F I E

层次遍历算法 void TraversalLevel(BTNode *bt) { BTNode *q[50]; /*假定队列容量足够大，不需用循环，也不需判队满*/ int front=-1,rear=-1; /*置队空*/ BTNode *p=bt; q[++rear]=p; while(front<rear) {p=q[++front];printf("%c",p->data); if(p->lchild!=NULL) q[++rear]=p->lchild; if(p->rchild!=NULL) q[++rear]=p->rchild;} }

5.3.3遍历算法的应用 输出二叉树中的结点 输出二叉树中的叶子结点 统计叶子结点的数目 求二叉树的高度 建立二叉链表方式存储二叉树 …

例1：输出二叉树中的结点 思路：按先序遍历走遍二叉树中的每一个结点，并输出。 void PreOrder(BTNode root) { if(root!=NULL) { visit(root->data); PreOrder(root->lchild); PreOrder(root->rchild); } printf(“%c”,root->data);

例2：输出二叉树中的叶子结点 思路：遍历过程中判断当前访问结点是否为叶子结点。 条件：既没有左孩子，又没有右孩子。 void PreOrder(BTNode root) { if(root!=NULL) { printf(“%c”,root->data); PreOrder(root->lchild); PreOrder(root->rchild); } if(root->lchild==NULL&&root->child==NULL)

例3：统计叶子结点的数目 思路：设置计数器为全局变量，保留叶子结点数目，调用之前初值为0。 void leaf(BTNode root) { if(root!=NULL) { leaf(root->lchild); leaf(root->rchild); leafcount++; } if(root->lchild==NULL&&root->child==NULL)

例4：求二叉树的高度 int BTHeight(BTNode *bt) { int lchilddep,rchilddep; if(bt==NULL) return(0); /*空树的高度为0 */ else { lchilddep=BTHeight(bt->lchild); /*求左子树的高度为lchilddep*/ rchilddep=BTHeight(bt->rchild); /*求右子树的高度为rchilddep*/ return (lchilddep>rchilddep)? (lchilddep+1)：(rchilddep+1)； }

例5:由前序和中序建立该二叉树。 1. 用前序序列的第一个结点作为根结点; 2.在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列; 根据左、右子树的中序序列中的结点个数，将前序序列去掉根结点后的序列划分为左、右两个序列，它们分别是左、右子树的前序序列; 4. 对左、右子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。

1.A为根结点 2. B为左子树的根结点 前序序列为ABDGHCEFI，中序序列为GDHBAECIF，则得到的二叉树为 A DHG GDH B

3. D为左子树的左子树的根结点 4 . C为右子树的根结点 B DGH GDH B C E FI E C IF A B G H D C E

A B G H D C F I E FI IF 5. F为右子树的右子树的根结点

5．4 线索二叉树 5．4．1 定义 n个结点二叉树(有n+1个空链域)，利用空链域存放某种遍历下该结点的前趋和后继的指针，这些指针称为线索，加上线索二叉树为线索二叉树。

先序：ABDCEF 线序线索二叉树

中序线索二叉树 中序：BDAECF

后序线索二叉树 后序：DBEFCA

线索二叉树结点结构 lchild ltag data rtag rchild 0 lchild域指向结点的左孩子 ltag=

线索二叉树类型定义： typedef struct bthnode { BTreeDT data; struct bthnode *lchild,*rchild; int lflag,rflag; }BthNode ;

带头结点中序线索二叉树（BDAECF）

5．4．2二叉树的线索化 建立线索化二叉树，实质上就是遍历二叉树，在遍历过程中，检查当前结点的左、右指针域是否为空；如果为空，将它们改为指向前趋结点或后继结点的线索。

p的前驱为pre，在当前结点 p不空的情况下： ①遍历左子树(即左子树线索化)。 ②对空指针线索化。 若p->lchild为空，则使p->lflag=l，且p->lchild=pre; 若pre->rchild为空，则使pre->rflag=l， 且pre->rchild=p；pre=p； ③遍历右子树(即右子树线索化)。

void Thread(BthNode *p) {if(p!=NULL) { Thread(p->lchild); /*左子树线索化*/ if(p->lchild==NULL) /*前趋线索*/ {p->lchild=pre; /*给结点*p添加前趋线索*/ p->lflag=1;} else p->lflag=0; if(pre->rchild==NULL) {pre->rchild=p; /*给结点*pre添加后继线索*/ pre->rflag=1;} else pre->rflag=0 ; pre=p; Thread(p->rchild); /*右子树线索化*/ } }

BthNode *CreaThread(BthNode *bt) /*对以bt为根结点的二叉树中序线索化，并增加一个头结点head*/ { BthNode *head; head=(BthNode *)malloc(sizeof(BthNode)); /*创建头结点*/ head->lflag=0 ;head->rflag=1 ; head->rchild=bt; if(bt==NULL) /*bt为空树时*/ head->lchild=head; else { head->lchild=bt; pre=head; /*pre是*p的前趋结点，供加线索用*/ Thread(bt); /*中序遍历线索化二叉树*/ pre->rchild=head; /*最后处理，加入指向根结点的线索*/ pre->rflag=1 ; head->rchild=pre; /*根结点右线索化 */ } return head; }

5.4.3 基本运算算法 ①查找中序序列的第一个结点FirstNode(tb)。 ②查找中序序列的最后一个结点 LastNode(tb)。 ③查找p结点的前趋结点PreNode(p)。 ④查找p结点的后继结点PostNode(p)。 ⑤输出中序遍历序列ThInOrder(tb)。 ⑥输出逆中序遍历序列ThlnOrderl(tb)。

(1)查找中序序列的第一个结点 从根结点出发沿左指针向下到达最左下结点，它是中序序列的第一个结点。 BthNode *FirstNode(BthNode *tb) { BthNode *p=tb->lchild; while(p->lflag==0) p=p->lchild; return(p); }

BthNode *LastNode(BthNode *tb) { return(tb->rchild); } (2)查找中序序列的最后一个结点 由头结点的rchild域指向中序序列的最后一个结点。 BthNode *LastNode(BthNode *tb) { return(tb->rchild); }

(3)查找p结点的前趋结点 若p->lflag=1，则p->lchild指向前趋结点；否则，查找p结点的左孩子的最右下结点,该结点作为p结点的前趋结点。 BthNode *PreNode(BthNode *p) { BthNode *pre ; pre=p->lchild; if(p->lflag!=1) while(pre->rflag==0) pre=pre->rchild; return(pre); }

(4)查找p结点的后继结点 若p->rflag=1，则p->rchild指向后继结点；否则，查找p结点的右孩子的最左下结点，该结点作为p结点的后继结点。 BthNode *PostNode(BthNode *p) { BthNode *post; post=p->rchild; if(p->rflag!=1) while(post->lflag==0) post=post->lchild; return(post);}

(5)输出中序遍历序列。先访问第一个结点，继续访问其后继结点，直到遍历完所有结点为止。 void ThInOrder(BthNode *tb) { BthNode *p; p=FirstNode(tb); while(p!=tb) { printf("%d",p->data); p=PostNode(p); } }

void Thlnorderl(BthNode *tb) { BthNode *p; p=LastNode(tb); (6)输出逆中序遍历序列。先访问最后一个结点，继续访问其前趋结点，直到遍历完所有结点为止。 void Thlnorderl(BthNode *tb) { BthNode *p; p=LastNode(tb); while(p!=tb) {printf(“%d”,p->data); p=PreNode(p); }}

5．5树、森林与二叉树的转换 5．5．1树转换为二叉树 ①所有相邻兄弟之间加一条连线； 过程如下： ①所有相邻兄弟之间加一条连线； ②只保留与第一个孩子之间的连线，删除与其他孩子之间的连线； ③以根结点为轴心，将整棵树顺时针转动45度，使之层次分明。

连线 A B C D E F G

抹线 旋转 B A C D E F G A B C D E F G

【例1】将树转换成二叉树 (a)一棵树

5．5．2森林转换为二叉树 ①森林中的每棵树转换成二叉树。 过程如下： ①森林中的每棵树转换成二叉树。 ②第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子结点，当所有二叉树连在一起后，得到的二叉树就是由森林转换得到的二叉树。

5.5.3 二叉树还原为树和森林 过程如下： ①若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、．．．、都与该结点的双亲结点用连线连起来。 ②删除原二叉树中所有双亲结点与右孩子结点之间的连线。 ③整理由①、②两步所得到的树或森林，使之结构层次分明。

5．6 哈夫曼树 5．6．1哈夫曼树的基本概念 结点路径长度：从根结点到该结点分支的数目。

结点的权：树中结点上赋予的一定意义的实数。 结点的带权路径长度：结点路径长度与该结点上的权值之积。 树的带权路径长度：树中所有叶子结点的带权路径长度之和 WPL(T) = wklk (对所有叶子结点)

7 5 9 2 4 WPL(T)= 72+52+23+43+92=60

2 4 5 7 9 WPL(T)=74+94+53+42+21=89

n（n>1）个带权值的叶子构造二叉树，树中除了叶子外只能为度为2的结点，其中树的带权路径长度最小的树称为哈夫曼树。

5．6．2哈夫曼树的具体构造方法 （1）n个权值{W0，W1，……，Wn-1}构造n棵只有一个根结点的二叉树，这些二叉树组成一个森林F。

例如: 已知权值 W={ 5, 6, 3, 9, 7 } 5 6 3 9 7 6 9 7 8 5 3 9 5 3 8 13 6 7

9 5 3 8 6 7 13 30 6 7 13 17 5 3 8 9

5.6.3 哈夫曼树的应用 等长编码方案 不等长编码方案 假设一个文件包含8个字符 {A，B，C，D，E，F，G，H}，出现的次数为{5，29，6，9，14，23，3，11}。 为了压缩文件长度，有两种方案： 等长编码方案 （用3个二进制位长度的等长编码） 不等长编码方案

前缀编码：不等长编码中，任何字符编码都不允许是另一个字符编码的前缀。 例如:A编码是01，B编码是0101，当对压缩串“010101”解码时会有多种解释：“AAA”、“AB”和“BA”等。

5．6．3哈夫曼树的应用 字符作为叶子，字符出现的次数为叶子的权值来构造哈夫曼树。规定0表示左分支、1表示右分支，从根结点到每个叶子所经过的分支组成的序列为该叶子对应字符的编码。

习题课 一、名词解释 1、树、二叉树 2、满二叉树 3、完全二叉树 4、二叉树遍历 5、线索二叉树 6、哈夫曼树

树： A D B F C E G I H

二叉树:

满二叉树： 3 1 4 2 11 6 8 7 9 10 5 12 13 14

完全二叉树： 3 1 4 2 11 6 8 7 9 10 5 3 1 4 2 6 8 7 9 10 5

二叉树遍历

线索二叉树： 中序：BDAECF

哈夫曼树： 定义 构造方法

已知一棵度为m（m>1）的树中有n1个度为1的结点，n2个度为2的结点，…，nm个度为m的结点，则该树中有多少个叶子结点。

已知一棵共有n（n>1）个结点的树，其中所有分支结点的度均为k（1≤k<n），则该树的叶子数目为多少个。

有n个叶子的哈夫曼树的结点总数为多少个。

写出先序、中序和后序遍历。

已知一棵二叉树的后序遍历序列为GDEBHFCA，中序遍历序列为DGBEAFHC，画出该二叉树。

画出森林所对应的二叉树。

以数据集{2，5，7，9，13}为权值构造一颗哈夫曼树。

结 束！