第六章-树和二叉树2课件

第六章树和二叉树(2)第六章树和二叉树(2)1主要内容树的定义和基本术语二叉树遍历二叉树线索二叉树树、森林与二叉树赫夫曼树及其应用主要内容树的定义和基本术语24、线索二叉树4.1何谓线索二叉树？4.2线索二叉树的存储结构4.3线索二叉树的遍历4、线索二叉树34.1何谓线索二叉树？为什么要线索？1）二叉树的存储结构中没有反映出某结点的直接前驱结点和直接后继结点是什么。2）二叉树的二叉链表存储结构中的那些空指针域可利用。4.1何谓线索二叉树？为什么要线索？1）二叉树的存储结构中4ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如:先序序列:中序序列:后序序列:遍历二5ABCDEFGHK^

D^

C^^

B

E^指向该线性序列中的“前驱”和“后继”的指针，称作“线索”。包含“线索”的存储结构，称作“线索链表”。加上线索的二叉树，称作“线索二叉树”。ABCDEFGH6lchild

ltag

data

rtag

rchild0:lchild指向该结点的左孩子1:lchild指向该结点的前驱结点0:rchild指向该结点的右孩子1:rchild指向该结点的后继结点ltag=rtag=4.2线索二叉树的存储结构结点结构线索链表如此定义的二叉树的存储结构称作“线索链表”。lchildltagdatartagrchild07第六章--树和二叉树2课件8第六章--树和二叉树2课件9先序线索二叉树：先序序列为：ABCD线索二叉树画法先序线索二叉树：线索二叉树画法10中序线索二叉树：中序序列为：BADC中序线索二叉树：11后序线索二叉树：后序序列为：BDCA后序线索二叉树：125、树、森林与二叉树5.1树的三种存储结构5.2树、森林和二叉树的转换5、树、森林与二叉树135.1树的三种存储结构一、双亲表示法二、孩子链表表示法三、树的二叉链表(孩子-兄弟） 存储表示法5.1树的三种存储结构一、双亲表示法二、孩子链表表示法三、14ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5dataparent一、双亲表示法:ABCDEFG0A-1datapare15

typedefstructPTNode{Elemdata;

intparent;//双亲位置域

}

PTNode;

dataparent#defineMAX_TREE_SIZE100结点结构:C语言的类型描述:typedefstructPTNode{dat16typedefstruct{PTNodenodes[MAX_TREE_SIZE];

intr,n;//根结点的位置和结点个数

}

PTree;树结构:typedefstruct{树结构:17ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4

datafirstchild123456二、孩子链表表示法:-1000224ABCDEFG0A-1datafir18typedefstructCTNode{

intchild;

structCTNode*next;

}*ChildPtr;孩子结点结构:

childnextC语言的类型描述:typedefstructCTNode{孩子结点结构:19

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子链的头指针

}

CTBox;双亲结点结构

datafirstchildtypedefstruct{双亲结点结构data20typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//结点数和根结点的位置

}

CTree;树结构:typedefstruct{树结构:21ABCDEFG

ABCEDFGroot

ABCEDFG

三、树的二叉链表(孩子-兄弟）存储表示法ABCDEFGAroot22typedefstructCSNode{Elemdata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;C语言的类型描述:结点结构:

firstchilddatanextsiblingtypedefstructCSNode{C语言的类型描述235.2树、森林和二叉树的转换树和二叉树之间的对应关系

树：兄弟关系二叉树：双亲和右孩子树：双亲和长子二叉树：双亲和左孩子AEBCFDGABCDEFG5.2树、森林和二叉树的转换树和二叉树之间的对应关系AEB241.兄弟加线.树转换为二叉树示例ABCDEFG1.兄弟加线.树转换为二叉树示例ABCDEFG252.保留双亲与第一孩子连线,删去与其他孩子的连线.ABCDEFG1.兄弟加线.树转换为二叉树示例2.保留双亲与第一孩子连线,删去与其他孩子的连线.ABCDE263.顺时针转动,使之层次分明.2.保留双亲与第一孩子连线,删去与其他孩子的连线.1.兄弟加线.ABCDEFG树转换为二叉树示例3.顺时针转动,使之层次分明.2.保留双亲与第一孩子连线,删273.顺时针转动,使之层次分明.2.保留双亲与第一孩子连线,删去与其他孩子的连线.1.兄弟加线.GDABECF树转换为二叉树示例3.顺时针转动,使之层次分明.2.保留双亲与第一孩子连线,删28树转换为二叉树步骤⑴加线——树中所有相邻兄弟之间加一条连线。

⑵去线——对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。

⑶层次调整——以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。

树转换为二叉树步骤⑴加线——树中所有相邻兄弟之间加一条连线29森林转换为二叉树步骤⑴将森林中的每棵树转换成二叉树；⑵从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。森林转换为二叉树步骤⑴将森林中的每棵树转换成二叉树；30二叉树转换为树或森林步骤⑴加线——若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点y用线连起来；⑵去线——删去原二叉树中所有的双亲结点与右孩子结点的连线；⑶

层次调整——整理由⑴、⑵两步所得到的树或森林，使之层次分明。

二叉树转换为树或森林步骤⑴加线——若某结点x是其双亲y的31FHGEAICDBFHGDCEBAIFEDCBAHGI加线去线层次调整IHGBCDAFE二叉树转换为树或森林示例FHGEAICDBFHGDCEBAIFEDCBAHGI加线去326、赫夫曼树及其应用6.1相关概念6.2如何构造最优二叉树（赫夫曼树）6.3赫夫曼树应用——赫夫曼编码6、赫夫曼树及其应用6.1相关概念336.1相关概念叶子结点的权值：对叶子结点赋予的一个有意义的数值量。

二叉树的带权路径长度：设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。记为：WPL=å=nkkklw1第k个叶子的权值；从根结点到第k个叶子的路径长度最优二叉树（赫夫曼树）：在所有含n个叶子结点、并带相同权值的二叉树中，必存在一棵其带权路径长度取最小值的二叉树，称为“最优二叉树”。6.1相关概念叶子结点的权值：对叶子结点赋予的一个有意义的3427975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=895427975492WPL(T)=735赫夫曼树的特点：1.权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。2.只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点.

2347WPL=32WPL=41WPL=3023477423赫夫曼树的特点：2347WPL=32366.2如何构造最优树赫夫曼算法基本思想：⑴初始化：由给定的n个权值{w1，w2，…，wn}构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合F＝{T1，T2，…，Tn}；⑵选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和；⑶删除与加入：在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中；

⑷

重复⑵、⑶两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是赫夫曼树。

6.2如何构造最优树赫夫曼算法基本思想：37例：W＝{2，3，4，5}

赫夫曼树的构造过程重复第2步5432

554

9重复第3步

554

932例：W＝{2，3，4，5}赫夫曼树的构造过程重复第2步54386.3赫夫曼树应用——赫夫曼编码编码：给每一个对象标记一个二进制位串来表示一组对象。前缀编码：一组编码中任一编码都不是其它任何一个编码的前缀。前缀编码保证了在解码时不会有多种可能。利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。6.3赫夫曼树应用——赫夫曼编码编码：给每一个对象标记一39例：一组字符{A,B,C,D,E,F,G}出现的频率分别是{9,11,5,7,8,2,3}，设计最经济的编码方案。9523510191126871545000000111111ABDCEFG编码方案：A：00B：10C：010D：110E：111F：0110G：0111例：一组字符{A,B,C,D,E,F,G}出现的40本章小结1.理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系。2.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。3.了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。本章小结1.理解二叉树线索化的实质是建立结点与其在相应序41作业：（11月5日交（一））（一）本或纸1、对于下图所示的二叉树，请将它转换成森林。2、设F＝{T1,T2,T3}是森林，请画出其对应的二叉树。其森林如下图所示。ABCDEFGHIJABCDEFGHJIK作业：（11月5日交（一））（一）本或纸ABCDEFGHIJ423、以数据集{2,5,7,9,13}为权值构造一棵赫夫曼树，并计算其带权路径长度。（二）上机（不交）1、赫夫曼树演示2、赫夫曼树实验，体会各算法运算过程3、以数据集{2,5,7,9,13}为权值构造一棵赫夫曼树，43第六章树和二叉树(2)第六章树和二叉树(2)44主要内容树的定义和基本术语二叉树遍历二叉树线索二叉树树、森林与二叉树赫夫曼树及其应用主要内容树的定义和基本术语454、线索二叉树4.1何谓线索二叉树？4.2线索二叉树的存储结构4.3线索二叉树的遍历4、线索二叉树464.1何谓线索二叉树？为什么要线索？1）二叉树的存储结构中没有反映出某结点的直接前驱结点和直接后继结点是什么。2）二叉树的二叉链表存储结构中的那些空指针域可利用。4.1何谓线索二叉树？为什么要线索？1）二叉树的存储结构中47ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如:先序序列:中序序列:后序序列:遍历二48ABCDEFGHK^

D^

C^^

B

E^指向该线性序列中的“前驱”和“后继”的指针，称作“线索”。包含“线索”的存储结构，称作“线索链表”。加上线索的二叉树，称作“线索二叉树”。ABCDEFGH49lchild

ltag

data

rtag

rchild0:lchild指向该结点的左孩子1:lchild指向该结点的前驱结点0:rchild指向该结点的右孩子1:rchild指向该结点的后继结点ltag=rtag=4.2线索二叉树的存储结构结点结构线索链表如此定义的二叉树的存储结构称作“线索链表”。lchildltagdatartagrchild050第六章--树和二叉树2课件51第六章--树和二叉树2课件52先序线索二叉树：先序序列为：ABCD线索二叉树画法先序线索二叉树：线索二叉树画法53中序线索二叉树：中序序列为：BADC中序线索二叉树：54后序线索二叉树：后序序列为：BDCA后序线索二叉树：555、树、森林与二叉树5.1树的三种存储结构5.2树、森林和二叉树的转换5、树、森林与二叉树565.1树的三种存储结构一、双亲表示法二、孩子链表表示法三、树的二叉链表(孩子-兄弟） 存储表示法5.1树的三种存储结构一、双亲表示法二、孩子链表表示法三、57ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5dataparent一、双亲表示法:ABCDEFG0A-1datapare58

typedefstructPTNode{Elemdata;

intparent;//双亲位置域

}

PTNode;

dataparent#defineMAX_TREE_SIZE100结点结构:C语言的类型描述:typedefstructPTNode{dat59typedefstruct{PTNodenodes[MAX_TREE_SIZE];

intr,n;//根结点的位置和结点个数

}

PTree;树结构:typedefstruct{树结构:60ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4

datafirstchild123456二、孩子链表表示法:-1000224ABCDEFG0A-1datafir61typedefstructCTNode{

intchild;

structCTNode*next;

}*ChildPtr;孩子结点结构:

childnextC语言的类型描述:typedefstructCTNode{孩子结点结构:62

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子链的头指针

}

CTBox;双亲结点结构

datafirstchildtypedefstruct{双亲结点结构data63typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//结点数和根结点的位置

}

CTree;树结构:typedefstruct{树结构:64ABCDEFG

ABCEDFGroot

ABCEDFG

三、树的二叉链表(孩子-兄弟）存储表示法ABCDEFGAroot65typedefstructCSNode{Elemdata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;C语言的类型描述:结点结构:

firstchilddatanextsiblingtypedefstructCSNode{C语言的类型描述665.2树、森林和二叉树的转换树和二叉树之间的对应关系

树：兄弟关系二叉树：双亲和右孩子树：双亲和长子二叉树：双亲和左孩子AEBCFDGABCDEFG5.2树、森林和二叉树的转换树和二叉树之间的对应关系AEB671.兄弟加线.树转换为二叉树示例ABCDEFG1.兄弟加线.树转换为二叉树示例ABCDEFG682.保留双亲与第一孩子连线,删去与其他孩子的连线.ABCDEFG1.兄弟加线.树转换为二叉树示例2.保留双亲与第一孩子连线,删去与其他孩子的连线.ABCDE693.顺时针转动,使之层次分明.2.保留双亲与第一孩子连线,删去与其他孩子的连线.1.兄弟加线.ABCDEFG树转换为二叉树示例3.顺时针转动,使之层次分明.2.保留双亲与第一孩子连线,删703.顺时针转动,使之层次分明.2.保留双亲与第一孩子连线,删去与其他孩子的连线.1.兄弟加线.GDABECF树转换为二叉树示例3.顺时针转动,使之层次分明.2.保留双亲与第一孩子连线,删71树转换为二叉树步骤⑴加线——树中所有相邻兄弟之间加一条连线。

⑵去线——对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。

⑶层次调整——以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。

树转换为二叉树步骤⑴加线——树中所有相邻兄弟之间加一条连线72森林转换为二叉树步骤⑴将森林中的每棵树转换成二叉树；⑵从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。森林转换为二叉树步骤⑴将森林中的每棵树转换成二叉树；73二叉树转换为树或森林步骤⑴加线——若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点y用线连起来；⑵去线——删去原二叉树中所有的双亲结点与右孩子结点的连线；⑶

层次调整——整理由⑴、⑵两步所得到的树或森林，使之层次分明。

二叉树转换为树或森林步骤⑴加线——若某结点x是其双亲y的74FHGEAICDBFHGDCEBAIFEDCBAHGI加线去线层次调整IHGBCDAFE二叉树转换为树或森林示例FHGEAICDBFHGDCEBAIFEDCBAHGI加线去756、赫夫曼树及其应用6.1相关概念6.2如何构造最优二叉树（赫夫曼树）6.3赫夫曼树应用——赫夫曼编码6、赫夫曼树及其应用6.1相关概念766.1相关概念叶子结点的权值：对叶子结点赋予的一个有意义的数值量。

二叉树的带权路径长度：设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。记为：WPL=å=nkkklw1第k个叶子的权值；从根结点到第k个叶子的路径长度最优二叉树（赫夫曼树）：在所有含n个叶子结点、并带相同权值的二叉树中，必存在一棵其带权路径长度取最小值的二叉树，称为“最优二叉树”。6.1相关概念叶子结点的权值：对叶子结点赋予的一个有意义的7727975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=895427975492WPL(T)=778赫夫曼树的特点：1.权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。2.只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点.

2347WPL=32WPL=41WPL=3023477423赫夫曼树的特点：2347WPL=32796.2如何构造最优树赫夫曼算法基本思想：⑴初始化：由给定的n个权值{w1，w2，…，wn}构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合F＝{T1，T2