数据结构讲义树和二叉树

数据结构讲义树和二叉树第一页，共一百零六页，编辑于2023年，星期三6.1树的定义和基本术语1、树的定义

树是由n(n≥0)个结点组成的有限集合。 如果n=0，称为空树； 否则，在一棵非空树中，满足如下两个条件： （1）有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱； （2）除根以外的其它结点划分为m(m≥0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。ABCDGFEHIJKLM第二页，共一百零六页，编辑于2023年，星期三2、树的表示（1）树型表示（直观表示法）6.1树的定义和基本术语ABCDGFEHIJKLM第三页，共一百零六页，编辑于2023年，星期三2、树的表示（1）树型表示（直观表示法）（2）二元组表示T=(D,R)D={A,B,C,D,E,F,G,H,I,J,K,L,M}R={<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,<D,H>,<D,I>,<D,J>,<E,K>,<E,L>,<H,M>}6.1树的定义和基本术语ABCDGFEHIJKLM第四页，共一百零六页，编辑于2023年，星期三2、树的表示（1）树型表示（直观表示法）（2）二元组表示（3）凹入法6.1树的定义和基本术语ABCDGFEHIJKLMABEKLFCGDHMJI第五页，共一百零六页，编辑于2023年，星期三2、树的表示（1）树型表示（直观表示法）（2）二元组表示（3）凹入法（4）嵌套集合表示6.1树的定义和基本术语ABCDGFEHIJKLMAEDHJIKLMDGC第六页，共一百零六页，编辑于2023年，星期三2、树的表示（1）树型表示（直观表示法）（2）二元组表示（3）凹入法（4）嵌套集合表示（5）广义表表示（嵌套括号表示）6.1树的定义和基本术语ABCDGFEHIJKLM（A（B（E（K,L）,F）,C（G）,D（H（M）,I,J）））第七页，共一百零六页，编辑于2023年，星期三3、基本术语 结点（node）：包含一个数据元素及若干指向其它结点的分支信息。 结点的度(degree)：结点的子树个数 叶结点(leaf)：度为0的结点，也称为终端结点。 分支结点(branch)：度不为0的结点，也称为非终端结点。 孩子结点(child)：一个结点的直接后继或某结点子树的根结点

。 双亲结点(parent)：一个结点的直接前驱或某个结点是其子树之根的双亲

。6.1树的定义和基本术语ABCDGFEHIJKLM第八页，共一百零六页，编辑于2023年，星期三3、基本术语 兄弟(sibling)结点:具有同一双亲的所有结点 祖先(ancestor)结点:若树中结点k到ks存在一条路径，则称k是ks的祖先 子孙(descendant)结点:若树中结点k到ks存在一条路径，则称ks是k的子孙

结点所处层次(level):根结点的层数为1，其余结点的层，其余结点的层数为双亲结点的层数加1 树的高度(depth):树中结点的最大层数 树的度(degree):树中结点的最大度数

6.1树的定义和基本术语ABCDGFEHIJKLM第九页，共一百零六页，编辑于2023年，星期三3、基本术语有序树子树的次序不能互换无序树子树的次序可以互换森林（Forest）互不相交的树的集合

6.1树的定义和基本术语ABCDGFEHIJKLM第十页，共一百零六页，编辑于2023年，星期三4、树的基本操作初始化求指定结点所在树的根结点求指定结点的双亲结点求指定结点的某一孩子结点求指定结点的最右边兄弟结点将一棵树插入到另一树的指定结点下作为它的子树删除指定结点的某一子树树的遍历6.1树的定义和基本术语第十一页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.1二叉树的定义1、二叉树（BinaryTree）或为空树，或由根及两棵不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。说明1）二叉树中每个结点最多有两棵子树；二叉树每个结点度小于等于2;2）左、右子树不能颠倒——有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;

A

F

G

E

D

C

B第十二页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.1二叉树的定义2、二叉树的五种不同形态二叉树的五种不同形态第十三页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.1二叉树的定义3、二叉树和树的区别：

二叉树不是树的特殊情形，它们是两个概念。 树和二叉树之间最主要的差别是：二叉树中结点的子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。

第十四页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.2二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)性质2：深度为k的二叉树最多有2k-1个结点。(k≥1)性质3：对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0＝n2＋1。

第十五页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.2二叉树的性质两种特殊的二叉树： 满二叉树：深度为k且有2k-1个结点的二叉树。 在满二叉树中，每层结点都是满的，即每层结点都具 有最大结点数。123456789101112131415满二叉树第十六页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.2二叉树的性质两种特殊的二叉树： 完全二叉树：若设二叉树的高度为h，除第h层外，其它各层的结点数都达到最大个数，第h层的结点集中出现在左端若干连续位置上，这就是完全二叉树。完全二叉树1234567891011121314关系：满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。第十七页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.2二叉树的性质两种特殊的二叉树：

完全二叉树举例：12345612345712367(a)完全二叉树(b)非完全二叉树(c)非完全二叉树第十八页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.2二叉树的性质性质4：具有n个结点的完全二叉树的深度为 └log2n┘+1

证明：设完全二叉树的高度为深度为h，则有2h-1-1<n≤2h-1⇒2h-1<=n<2h⇒取对数h–1<=log2(n)<h。

第十九页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.2二叉树的性质性质5：对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有：（1）如i=1，则序号为i的结点是根结点，无双亲结点；如i>1，则序号为i的结点的双亲结点序号为└i/2┘。（2）如2×i>n，则序号为i的结点无左孩子；如2×i≤n，则序号为i的结点的左孩子结点的序号为2×i。（3）如2×i＋1>n，则序号为i的结点无右孩子；如2×i＋1≤n，则序号为i的结点的右孩子结点的序号为2×i＋1。 第二十页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.3二叉树的存储结构1、顺序存储结构

#defineMAXNODE100 typedefelemtypeSqBiTree[MAXNODE] SqBiTreebt;ABCDEFGHIJKLABCDEFGHIJKL二叉树的顺序存储结构11109876543210第二十一页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.3二叉树的存储结构1、顺序存储结构

ACBEDFGABC∧DE∧∧∧F∧∧GABDCEFG(a)一般的二叉树(b)改造后的完全二叉树第二十二页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.3二叉树的存储结构1、顺序存储结构

ABCDA^

B^^^C^^^^^^^D单支树顺序存储结构仅适用于完全二叉树2n-1第二十三页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.3二叉树的存储结构2、链式存储结构 （1）二叉链表： 二叉链表中每个结点包含三个域：数据域、左指针域、右指针域lchilddatarchildtypedefstructnode{ ElemTypedata; structnode*lchild; structnode*rchild;}BiTNode,*BiTree;第二十四页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.3二叉树的存储结构2、链式存储结构 （1）二叉链表：

∧EA∧D∧C∧∧G∧∧F∧BBDFACEG

二叉树的二叉链表表示第二十五页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.3二叉树的存储结构2、链式存储结构 （2）三叉链表： 三叉链表中每个结点包含四个域：数据域、双亲指针 域、左指针域、右指针域

BDEADFABDFEC第二十六页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.3二叉树的存储结构2、链式存储结构 示例第二十七页，共一百零六页，编辑于2023年，星期三6.2二叉树(BinaryTree)6.2.4二叉树的基本操作创建二叉树 二叉树的遍历第二十八页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.1遍历二叉树（traversingbinarytree） 一、遍历二叉树的定义： 1、先序遍历（DLR） 若二叉树为空，则空操作；否则：

（1）访问根结点； （2）先序遍历左子树；

（3）先序遍历右子树；

A

F

G

E

D

C

B 先序遍历序列：A,B,D,E,G,C,F第二十九页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.1遍历二叉树（traversingbinarytree） 一、遍历二叉树的定义： 2、中序遍历（LDR）若二叉树为空，则空操作；否则：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；

A

F

G

E

D

C

B中序遍历序列：D,B,G,E,A,C,F第三十页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.1遍历二叉树（traversingbinarytree） 一、遍历二叉树的定义： 3、后序遍历（LRD） 若二叉树为空，则空操作；否则：

（1）后序遍历左子树； （2）后序遍历右子树；

（3）访问根结点；

A

F

G

E

D

C

B后序遍历序列：D,G,E,B,F,C,A第三十一页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.1遍历二叉树 例：先序遍历、中序遍历、后序遍历下图所示的表达式语法树

后序遍历序列（后缀表达式）：abcd-*+ef/-

中序遍历序列（中缀表达式）：a+b*c–d–e/f

先序遍历序列（前缀表达式）：-+a*b–cd/ef第三十二页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.1遍历二叉树 二、遍历二叉树的递归算法 数据结构定义：typedefintElemTypetypedefstructnode{ ElemTypedata; structnode*lchild; structnode*rchild;}BiTNode,*BiTree;第三十三页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.1遍历二叉树 二、遍历二叉树的递归算法 1、先序遍历PreOrderTranverse(BiTreeT){if(T){ printf(“%d”,T->data);//访问的方式有多种 PreOrderTranverse(T->LChild); PreOrderTranverse(T->RChild);}}第三十四页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.1遍历二叉树 二、遍历二叉树的递归算法 2、中序遍历InOrderTranverse(BiTreeT){if(T){ InOrderTranverse(T->LChild); printf(“%d”,T->data);//访问的方式有多种 InOrderTranverse(T->RChild);}}第三十五页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.1遍历二叉树 二、遍历二叉树的递归算法 3、后序遍历PostOrderTranverse(BiTreeT){if(T){ PostOrderTranverse(T->LChild); PostOrderTranverse(T->RChild); printf(“%d”,T->data);//访问的方式有多种 }}第三十六页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.1遍历二叉树 三、遍历二叉树的非递归算法 遍历的递归执行过程：

⊕⊕⊕⊕⊕⊕*******△△△AGBCDE△△△F△第三十七页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.1遍历二叉树 三、遍历二叉树的非递归算法 （一）基于栈的递归消除 1、中序遍历的非递归算法 第三十八页，共一百零六页，编辑于2023年，星期三void

InOrder（BiTreeT）{

InitStack(S);push(S,T); while(!StackEmpty(S)){ if(Getop(S,p)&&p!=NULL)

//向左走到尽头

{push(S,p->lchild;} pop(S,p);//空指针退栈

if(!StackEmpty(S)){//访问结点，向右一步

pop(S,p);visit(p->data);

p=p->rchild; } }} 6.3遍历二叉树和线索二叉树第三十九页，共一百零六页，编辑于2023年，星期三void

InOrder（BiTreeT）{

InitStack(S);p=T; while(p!=NULL||!StackEmpty(S)) {if(p!=NULL)

/*根指针进栈，遍历左子树*/

{push(S,p);p=p->lchild;}

else {

/*根指针退栈，访问根结点，遍历右子树*/ pop(S,p);visit(p->data);

p=p->rchild; } }} 6.3遍历二叉树和线索二叉树第四十页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.1遍历二叉树 三、遍历二叉树的非递归算法 （一）基于栈的递归消除 1、中序遍历的非递归算法 2、先序遍历的非递归算法第四十一页，共一百零六页，编辑于2023年，星期三void

PreOrder（BiTreeT）{

InitStack(S);p=T; while(p!=NULL||!StackEmpty(S)) {if(p!=NULL)

/*根指针进栈，遍历左子树*/

{visit(p->data);push(S,p);p=p->lchild;}

else {

/*根指针退栈，访问根结点，遍历右子树*/ pop(S,p);

p=p->RChild; } }} 6.3遍历二叉树和线索二叉树第四十二页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.1遍历二叉树 三、遍历二叉树的非递归算法 （一）基于栈的递归消除 1、中序遍历的非递归算法 2、先序遍历的非递归算法 3、后序遍历的非递归算法第四十三页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树typedefstruct{BiTreelink;intflag;}stacktype;void

PostOrder（BiTreeT）{

stacktypestack[MAXNODE];BiTreep;inttop,sign;if(T==NULL)return;top=-1;/*栈顶位置初始化*/p=T;while(!(p==NULL&&top==-1)){if(p!=NULL)/*结点第一次进栈*/{top++;stack[top].link=p;stack[top].flag=1;p=p->lchild; }else{p=stack[top].link;sign=stack[top].flag;top--;if(sign==1)//结点第二次进栈{top++;stack[top].link=p;stack[top].flag=2;//标记第二次出栈*/p=p->rchild;}else{visit(p->data); p=NULL;}}}}第四十四页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.1遍历二叉树 三、遍历二叉树的非递归算法 （一）基于栈的递归消除 1、中序遍历的非递归算法 2、先序遍历的非递归算法 3、后序遍历的非递归算法 （二）不用栈的二叉树遍历的非递归方法 1、对二叉树采用三叉链表存放 2、采用逆转链的方法 3、在线索二叉树上的遍历

第四十五页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.1遍历二叉树 四、层次遍历二叉树 二叉树的层次遍历，是指从二叉树的第一层（根结点） 开始，从上至下逐层遍历，在同一层中，则按从左到右 的顺序对结点逐个访问。 例： 层次遍历序列为ABCDEFG

A

F

G

E

D

C

B第四十六页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.1遍历二叉树 四、层次遍历二叉树算法voidLevelOrder（BiTreebt）/*层次遍历二叉树bt*/{BiTreeQueue[MAXNODE];intfront,rear;if(bt==NULL)return;front=-1;rear=0;queue[rear]=bt;while(front!=rear){front++;p=queue[front];Visit(p->data);if(p->lchild!=NULL)/*队首结点的左孩子入队*/{rear++;queue[rear]=p->lchild;}if(p->rchild!=NULL)/*队首结点的右孩子入队*/{rear++;queue[rear]=p->rchild;}}}第四十七页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.2遍历算法的应用

1．输出二叉树中的结点

输出二叉树中结点并无次序要求，因此可用任一种算法来完成。

voidPreOrder(BiTreeroot) /*先序遍历输出二叉树结点*/{ if(root!=NULL){printf(root->data);/*输出根结点*/ PreOrder(root->LChild);/*先序遍历左子树*/ PreOrder(root->RChild);/*先序遍历右子树*/ }}问题思考：若要求统计二叉树中结点个数应如何去实现？第四十八页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.2遍历算法的应用

2.统计叶子结点数目方法1：/*LeafCount保存叶子结点数目的全局变量,调用之前初始化值为0*/

IntLeafCount=0;voidleaf(BiTreeroot)

{if(root!=NULL)

{ leaf(root->LChild);

leaf(root->RChild);

if(root->LChild==NULL&&root->RChild==NULL) LeafCount++;

}

}第四十九页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.2遍历算法的应用

2.统计叶子结点数目方法2：intleaf(BiTreeroot){if(root==NULL)return0;elseif((root->LChild==NULL)&&(root->RChild==NULL)) return1;else returnleaf(root->LChild)+leaf(root->RChild); }第五十页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.2遍历算法的应用

3.建立二叉链表方式存储的二叉树voidCreateBiTree(BiTree&bt){ch=getchar();

if(ch=='.')bt=NULL;

else{ bt=(BiTree)malloc(sizeof(BiTNode));

bt->data=ch;

CreateBiTree(bt->LChild));

CreateBiTree(bt->RChild));

}

}第五十一页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.2遍历算法的应用

4.在二叉树中查找具有给定值的结点

BiTree

FindNode（BiTreeT,ElemTypex）{

InitStack(S);push(S,T); while(!StackEmpty(S)){ if(Getop(S,p)&&p!=NULL)

//向左走到尽头

push(S,p->lchild); pop(S,p);//空指针退栈

if(!StackEmpty(S)){//访问结点，向右一步

pop(S,p);if(p->data==x) returnp;

p=p->rchild;} }returnNULL;} 第五十二页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.2遍历算法的应用

5.表达式运算 可以用二叉树表示表达式 前缀表达式、中缀表达式、 后缀表达式分别是表达式树 的前序、中序、后序遍历结果。思考：利用中缀表达式建立表达式树？ 根据表达式树如何求得表达式的结果？

e

d

c

b

f

a

+

*

/

-

-第五十三页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.3线索二叉树

1.基本概念 二叉树的遍历是将二叉树中结点按一定规律线性化的过程。当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在遍历序列中的前驱和后继信息。要得到这些信息，第一种方法是将二叉树遍历一遍，在遍历过程中便可得到结点的前驱和后继，但这种动态访问浪费时间；第二种方法是充分利用二叉链表中的空链域，将遍历过程中结点的前驱、后继信息保存下来。第五十四页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.3线索二叉树

1.基本概念 在有n个结点的二叉链表中共有2n个链域，有n+1个空链域。我们可以利用剩下的n+1个空链域来存放遍历过程中结点的前驱和后继信息。现作如下规定： 若结点有左子树，则其LChild域指向其左孩子，否则LChild域指向其前驱结点；若结点有右子树，则其RChild域指向其右孩子，否则RChild域指向其后继结点。第五十五页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.3线索二叉树

1.基本概念 为了区分孩子结点和前驱、后继结点，为结点结构增设两个标志域，如下图所示：LChildLtagDataRtagRChild其中：Ltag=0LChild域指示结点的左孩子1LChild域指示结点的遍历前驱Rtag=0RChild域指示结点的右孩子1RChild域指示结点的遍历后继第五十六页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.3线索二叉树

1.基本概念 二叉树的二叉线索存储表示：

typedefenumPointerTag{Link,Thread};

typedefstructBitThrNode{ ElemTypedata; structBiThrNode*lchild,*rchild; PointerTagLTag,Rtag; }BiThrNode,*BiThrTree;第五十七页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.3线索二叉树

1.基本概念

线索：在这种存储结构中，指向前驱和后继结点的指针叫做线索。线索链表：以这种结构组成的二叉链表作为二叉树的存储结构，叫做线索链表。线索化：对二叉树以某种次序进行遍历并且加上线索的过程叫做线索化。线索二叉树：线索化了的二叉树称为线索二叉树。第五十八页，共一百零六页，编辑于2023年，星期三6.3遍历二叉树和线索二叉树6.3.3线索二叉树

2.二叉树的线索化

线索化实质上是将二叉链表中的空指针域填上相应结点的遍历前驱或后继结点的地址，而前驱和后继的地址只能在动态的遍历过程中才能得到。因此线索化的过程是在遍历过程中修改空指针域的过程。

对二叉树按照不同的遍历次序进行线索化，可以得到不同的线索二叉树

（先序线索二叉树、中序线索二叉树和后序线索二叉树）。第五十九页，共一百零六页，编辑于2023年，星期三下面是对同一棵二叉树的遍历方法不同得到的不同线索树。NULL(a)二叉树ABCDGEFH(b)先序线索二叉树ABCDGEFHNULLNULL（c）中序线索二叉树ABCDGEFH（d）后序线索二叉树NULLABCDGEFH第六十页，共一百零六页，编辑于2023年，星期三voidInOrderThreading(BiThrTree&Thrt,BiThrTreeT){/*对二叉树T进行中序线索化，其中pre始终指向刚访问过的结点*/ if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))return; 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;}} 中序线索化算法：第六十一页，共一百零六页，编辑于2023年，星期三voidInthreading(BiThrTreep){if(p){ Inthread(root->LChild);/*线索化左子树*/ if(p->LChild==NULL) {p->Ltag=Thrad;p->LChild=pre;}/*置前驱线索*/ if(pre->RChild==NULL) /*置后继线索*/ {pre->RChild=p;pre=p；}

Inthread(root->RChild);/*线索化右子树*/ }} 中序线索化算法：第六十二页，共一百零六页，编辑于2023年，星期三TRAVERSEINTHREAD(BiThrTreeT){ p=T->lchild; while(p!=T){ while(p->ltag==Link) p＝p->lchild; visit(p->data); while(p->Rtag==Thread&&p->rchild!=T) {p=p->rchild;visit(p->data);} }}中序线索化二叉树的遍历算法：第六十三页，共一百零六页，编辑于2023年，星期三6.4树和森林6.4.1树的存储结构 1、双亲表示法双亲表示类型定义#defineMAX100typedefstructnode{chardata;intparent;//双亲位置域}NODE;NODEtree[MAX];IACBHGFED9A0B1C1D2E2F3G5H5I50123456789dataparent找一个结点的双亲十分方便，但要找一个结点的孩子则要遍历整个结构第六十四页，共一百零六页，编辑于2023年，星期三6.4树和森林6.4.1树的存储结构 2、孩子链表表示法IACBHGFED∧A

B

C

D∧E

F∧G∧H∧

I∧012345678979∧823∧5∧6∧4datalink结点的孩子结点链表找一个结点的孩子十分方便，但要找一个结点的双亲则要遍历整个结构第六十五页，共一百零六页，编辑于2023年，星期三6.4树和森林6.4.1树的存储结构 2、孩子链表表示法树的孩子链表类型定义

structnode//孩子结点{intchild;structnode*link;};structt_node{chardata;structt_node*link;//孩子链表头指针}tree[MAX];第六十六页，共一百零六页，编辑于2023年，星期三6.4树和森林6.4.1树的存储结构 3、双亲孩子表示法IACBHGFED9∧A0B1C1D2∧E2F3∧G5∧H5∧

I5∧012345678979∧823∧5∧6∧4dataparentlink结点的孩子结点链表第六十七页，共一百零六页，编辑于2023年，星期三

structnode{chardata;structnode*son,*brother;};IF树的孩子兄弟表示法图示B的第一个孩子结点B的右兄弟结点∧GHECDB∧A∧∧∧∧∧∧∧∧6.4树和森林6.4.1树的存储结构 3、孩子兄弟表示法IACBHGFED第六十八页，共一百零六页，编辑于2023年，星期三IACBDHGFE此二叉链表既是树(a)的孩子兄弟表示又是二叉树(b)的二叉链表(a)(b)由此可将树与二叉树对应起来AIHDGFCEBFIABDHGCE6.4树和森林第六十九页，共一百零六页，编辑于2023年，星期三6.4树和森林6.4.2森林和二叉树的转换 二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。

1.树转换为二叉树⑴树中所有相邻兄弟之间加一条连线。⑵对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。⑶

以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。

第七十页，共一百零六页，编辑于2023年，星期三6.4树和森林6.4.2森林和二叉树的转换 二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。

1.树转换为二叉树⑴树中所有相邻兄弟之间加一条连线。⑵对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。⑶

以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。

第七十一页，共一百零六页，编辑于2023年，星期三IACBDHGFEFIABDHGCE6.4树和森林6.4.2森林和二叉树的转换1.树转换为二叉树第七十二页，共一百零六页，编辑于2023年，星期三6.4树和森林6.4.2森林和二叉树的转换2.森林转换为二叉树森林转换为二叉树的方法为：（1）将森林中的每棵树转换成相应的二叉树。（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。

第七十三页，共一百零六页，编辑于2023年，星期三6.4树和森林6.4.2森林和二叉树的转换2.森林转换为二叉树用递归的方法描述森林转换为二叉树的过程为：

将森林F看作树的有序集F={T1，T2，…,TN}，它对应的二叉树为B（F）：

（1）若N＝0，则B（F）为空。

（2）若N>0，二叉树B（F）的根为森林中第一棵树T1的根；B（F）的左子树为B（{T11，…，T1m}），其中{T11，…，T1m}是T1的子树森林；B（F）的右子树是B（{T2，…，TN}）。

第七十四页，共一百零六页，编辑于2023年，星期三6.4树和森林6.4.2森林和二叉树的转换3.二叉树还原为森林（1）若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、……都与该结点的双亲结点用线连起来。

（2）删掉原二叉树中所有双亲结点与右孩子结点的连线。

（3）整理由（1）、（2）两步所得到的树或森林，使之结构层次分明。

第七十五页，共一百零六页，编辑于2023年，星期三6.4树和森林6.4.2森林和二叉树的转换3.二叉树还原为森林第七十六页，共一百零六页，编辑于2023年，星期三6.4树和森林6.4.3森林和树的遍历1.树的遍历树的遍历方法主要有以下两种：1）先根遍历若树非空，则遍历方法为：（1）访问根结点。（2）从左到右，依次先根遍历根结点的每一棵子树。

ABECDFGH如图中树的先根遍历序列为：ABECFHGD。第七十七页，共一百零六页，编辑于2023年，星期三6.4树和森林6.4.3森林和树的遍历1.树的遍历树的遍历方法主要有以下两种：ABECDFGH2）后根遍历若树非空，则遍历方法为：（1）从左到右，依次后根遍历根结点的每一棵子树。（2）访问根结点。如图中树的后根遍历序列为：EBHFGCDA。注意：前序遍历一棵树等价于前序遍历该树对应的二叉树后序遍历一棵树等价于中序遍历该树对应的二叉树第七十八页，共一百零六页，编辑于2023年，星期三6.4树和森林6.4.3森林和树的遍历2.森林的遍历森林的遍历方法主要有以下三种：1）先序遍历若森林非空，则遍历方法为：（1）访问森林中第一棵树的根结点。（2）先序遍历第一棵树的根结点的子树森林。

（3）先序遍历除去第一棵树之后剩余的树构成的森林。

第七十九页，共一百零六页，编辑于2023年，星期三6.4树和森林6.4.3森林和树的遍历2.森林的遍历森林的遍历方法主要有以下三种：2）中序遍历若森林非空，则遍历方法为：（1）中序遍历森林中第一棵树的根结点的子树森林。

（2）访问第一棵树的根结点。

（3）中序遍历除去第一棵树之后剩余的树构成的森林。

第八十页，共一百零六页，编辑于2023年，星期三6.6.1最优二叉树（赫夫曼(Huffman)树）路径：从一个结点到另一个结点之间的若干个分支路径长度：路径上的分支数目称为路径长度；结点的路径长度：从根到该结点的路径长度树的路径长度：树中所有叶子结点的路径长度之和；一般记为PL。在结点数相同的条件下，完全二叉树是路径最短的二叉树。7132564881325746非完全二叉树完全二叉树6.6赫夫曼树及其应用第八十一页，共一百零六页，编辑于2023年，星期三1哈夫曼树的概念结点的权：根据应用的需要可以给树的结点赋权值；结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作WPL=wiLi哈夫曼树：假设有n个权值(w1,

w2,…,wn)，构造有n个叶子结点的严格二叉树，每个叶子结点有一个wi作为它的权值。则带权路径长度最小的严格二叉树称为哈夫曼树。6.6赫夫曼树及其应用第八十二页，共一百零六页，编辑于2023年，星期三BDACC

AD75244752AC

DB4752CA

BD4752BWPL=7*2+5*2+2*2+4*2=36WPL=7*1+5*2+2*3+4*3=35WPL=7*3+5*3+2*1+4*2=46WPL=7*1+5*2+2*3+4*3=35要使二叉树WPL小,就须在构造树时,将权值大的结点靠近根.第八十三页，共一百零六页，编辑于2023年，星期三2应用举例在求得某些判定问题时，利用哈夫曼树获得最佳判定算法。例编制一个将百分制转换成五分制的程序。最直观的方法是利用if语句来的实现。可用二叉树描述判定过程。6.6赫夫曼树及其应用不及格a70a60a80a90及格中等优秀良好设有10000个百分制分数要转换，设学生成绩在5个等级以上的分布如下：分数0-5960-6970-7980-8990-100比例数0.050.150.400.300.10第八十四页，共一百零六页，编辑于2023年，星期三按判定树判定过程:转换一个分数所需的比较次数=从根到对应结点的路径长度转换10000个分数所需的总比较次数=10000

(0.051+0.152+0.43+0.34+0.14）＝31500

二叉树的带权路径长度6.6赫夫曼树及其应用不及格a70a60a80a90及格中等优秀良好第八十五页，共一百零六页，编辑于2023年，星期三转换10000个分数所需的总比较次数=10000

(0.053+0.153+0.42+0.32+0.12）＝22000构造以分数的分布比例为权值的哈夫曼树：a80a90不及格良好中等及格优秀a60a706.6赫夫曼树及其应用第八十六页，共一百零六页，编辑于2023年，星期三3哈夫曼树的构造构造哈夫曼树的步骤：1．根据给定的n个权值，构造n棵只有一个根结点的二叉树，n个权值分别是这些二叉树根结点的权。设F是由这n棵二叉树构成的集合2．在F中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值=左、右子树根结点权值之和；3．从F中删除这两颗树，并将新树加入F；4．重复2、3，直到F中只含一颗树为止；6.6赫夫曼树及其应用第八十七页，共一百零六页，编辑于2023年，星期三403060155101530例：构造以W=（5，15，40，30，10）为权的哈夫曼树。3051015404030155101540303015510154010030601551015306.6赫夫曼树及其应用（1）（2）（3）（4）（5）第八十八页，共一百零六页，编辑于2023年，星期三6.6.2哈夫曼编码

在进行数据通讯时，涉及数据编码问题。所谓数据编码就是数据与二进制字符串的转换。例如：邮局发电报：

例要传输的原文为ABACCDA

（1）等长编码A：00B：01C：10D：11 发送方：将ABACCDA转换成00010010101100 接收方：将00010010101100还原为ABACCDA原文电文（二进制字符串）原文发送方接收方6.6赫夫曼树及其应用第八十九页，共一百零六页，编辑于2023年，星期三设A：0B：110C：10D：111发送方：将ABACCDA转换成0110010101110总长度是13所得的译码是唯一的前缀编码：任何字符编码不是其它字符编码的前缀6.6赫夫曼树及其应用（2）不等长编码A：0B：00C：1D：01 发送方：将ABACCDA转换成000011010 接收方：000011010转换成AAAACCDABBCCDAA的编码是B的前缀第九十页，共一百零六页，编辑于2023年，星期三可利用二叉树设计前缀编码：例某通讯系统只使用8种字符a、b、c、d、e、f、g、h，其使用频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，利用二叉树设计一种不等长编码：1）构造以a、b、c、d、e、f、g、h为叶子结点的二叉树；2）将该二叉树所有左分枝标记1，所有右分枝标记0；3）从根到叶子结点路径上标记作为叶子结点所对应字符的编码；6.6赫夫曼树及其应用第九十一页，共一百零六页，编辑于2023年，星期三a:0110b:10c:1110d:1111e:110f:00g:0111h:01029195842100158735811231429构造以字符使用频率作为权值的哈夫曼树如何得到使二进制串总长最短编码？6.6赫夫曼树及其应用第九十二页，共一百零六页，编辑于2023年，星期三6.6赫夫曼树及其应用由此可见，设计电文总长最短的二进制前缀编码即以n种字符出现的频率作权，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码称为赫夫曼编码。赫夫曼编码是一种最优的前缀编码。第九十三页，共一百零六页，编辑于2023年，星期三6.6赫夫曼树及其应用6.6.3赫夫曼编码算法由于哈夫曼树中没有度为1的结点（严格/正则二叉树），则一棵有n个叶子的哈夫曼树共有2×n-1个结点，可用一个大小为2×n-1的一维数组来存放各个结点。因为每个结点同时还包含其双亲信息和孩子结点信息，所以构成一个静态三叉链表。静态三叉链表描述如下：typedefstruct{unsignedintweight;/*存放各结点的权值*/unsignedintparent,LChild,RChild;/*指向双亲、孩子结点的指针*/}HTNode,*HuffmanTree;/*动态分配数组，存储哈夫曼树*/

typedefchar**HuffmanCode;/*动态分配数组，存储哈夫曼编码*/第九十四页，共一百零六页，编辑于2023年，星期三创建哈夫曼树并求哈夫曼编码的算法：viodCrtHuffmanTree(HuffmanTree*ht,*HuffmanCode*hc,int*w,intn){/*w存放n个权值,构造哈夫曼树ht,并求出哈夫曼编码h