大学教程(零起点)数据结构-树课件

第六章树6.1树的概念6.2二叉树6.3二叉树的遍历6.4线索二叉树6.5树和森林6.6哈夫曼树及其应用1描述层次结构，是一种一对多的逻辑关系FGIJABCEDHFGIJABCEDH2树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。有且仅有一个称为根的结点；n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合又是一棵树，称为子树FGIJABCEDH6.1树的概念35结点：数据元素的内容及其指向其子树根的分支结点的度：结点拥有的子树的数目。树的度：树内各结点的度的最大值；叶子（终端结点），非终端结点：度为0的结点称为叶子结点；度不为0的结点称为非终端结点。树的相关概念ABCDEFGHIJMKL6结点的层数：树中根结点的层次为1，根结点子树的根为第2层，以此类推。树的高度（深度）：树中所有结点层次的最大值ABCDEFGHIJMKL7孩子，双亲，兄弟，堂兄：结点的子树的根称为该结点的孩子；该结点称为孩子的双亲；同一个双亲的孩子之间互称兄弟；双亲在同一层的结点互为堂兄弟。子孙，祖先：以某结点为根的子树中的所有结点都被称为是该结点的子孙。从根结点到该结点路径上的所有结点称为该结点的祖先。ABCDEFGHIJMKL8n(n>0)个结点的树的高度:最低是多少？最高是多少？答案：1，n习题106.2二叉树二叉树(BinaryTree)：或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子树和右子树同样也都是二叉树12345678910111213141512二叉树的五种形态(a)(b)(c)(d)(e)141.一个非空二叉树的第i层上至多有2i-1个结点（i1）证明：i=1,只有根结点，显然成立 设i=k时成立，最多有2k-1个结点 当i=k+1时，最多的结点个数： 2k-1*2=2k-1+1=2k=2(

k+1)-1二叉树的性质123456789101112131415152.深度为k的二叉树至多有2k-1个结点(k1)

证明：二叉树的结点个数为： 1+2+…+2k-1=2k-1123456789101112131415163.对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：设n1为T中度为1的结点数，则总结点数： n=n0+n1+n2(1)另：根据各个结点的前驱和后继情况分支条数=n-1分支条数=n1+2*n2(2)由(1)和(2)有：n1+2*n2=n0+n1+n2-1故n0=n2+1;17考虑到有序性，任一结点在树中都有确切的位置，因此可以对满二叉树进行编号。编号方式为：从上到下，从左到右。满二叉树深度为k且有2k-1个结点的二叉树123456789101112131415181.满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。(√)2.满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。

(√)判断题204.具有n个结点的完全二叉树的深度:k=log2(n)+1证明：假设n个结点的完全二叉树的深度为k，则n的值应大于深度为k-1的满二叉树的结点数2k-1-1，小于等于深度为k的满二叉树的结点数2k-1，即2k-1-1<n≤2k-1进一步可推导出2k-1≤n<2k两边取对数后，有k-1≤log2(n)<k进一步可推导出log2(n)<k≤log2(n)+1因为k是整数，所以有k＝log2(n)+1211.一棵树高为K的完全二叉树至少有（）个结点A.2k–1B.2k-1–1C.2k-1

D.2k习题答案：C232.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。习题结点总个数n=2+3+4+x前驱后继n-1=2*1+3*2+4*3故x=12答案：12246.2.3二叉树的存储结构顺序存储结构链式存储结构26abcdefghij二叉树的顺序存储结构整个二叉树可以按照从上到下，从左到右的顺序编号27将一棵二叉树按完全二叉树顺序存放到一维数组中abcdefghm123456789101112131415

0123456789101112131415abcdefghm28对于一棵二叉树,若采用顺序存贮时,当它为完全二叉树时,比较方便;若为非完全二叉树,将会浪费大量存贮单元。因此，对于非完全二叉树，宜采用下面的链式存储结构。30链式存储结构二叉链表三叉链表31二叉链表lchilddatarchildABDCEFADEBCFroot32二叉链表的定义structbtnode{//结点结构datatypedata;structbtnode*lchild,*rchild;};结点结构:lchilddatarchild33ADEBCFroot问题：如何找到某结点的子树？如何找到某结点的双亲？34三叉链表lchilddatarchildparentADEBCFroot35三叉链表的定义structbtnode{//结点结构datatypedata;structbtnode*lchild,*rchild}；结点结构:lchilddatarchildparent,*parent;;36链式存储的缺点；

若一棵二叉树有n个结点,采用二叉链表作存贮结构时,共有2n个指针域,其中只有n-1个指针指向左右孩子,其余n+1个指针为空,没有发挥作用。376.3二叉树的遍历遍历一棵二叉树是按某种次序系统地“访问”二叉树上的所有结点，使每个结点恰好被“访问”一次。先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法“访问”的含义可以很广，如：输出结点的信息等38若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：AECBGL39若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：AECBGL40若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：AECBGL41先（根）序的遍历算法：voidPreorder(bitreptrr){//先序遍历二叉树

if(r！=NULL){visit(r);Preorder(r->lchild);Preorder(r->rchild);

}}AECBGL42中（根）序的遍历算法：voidInorder(bitreptrr){//中序遍历二叉树

if(r！=NULL){Preorder(r->lchild);visit(r);Preorder(r->rchild);

}}AECBGL43后（根）序的遍历算法：voidPostorder(bitreptrr){//后序遍历二叉树

if(r！=NULL){Preorder(r->lchild);Preorder(r->rchild);visit(r);

}}AECBGL44二叉树的遍历算法：AECBGLDLRLDR、LRD、DLR45遍历举例ABCDEF前序序列：abcdef中序序列：cbefda后序序列：cfedba46习题1.给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,1,7,5,6,2,4，则其遍历方式是LRNB.NRLC.RLND.RNL答案：D47习题2.假设前序序列为ABDGHCEFI，中序序列为GDHBAECIF，请确定一棵二叉树ABDGHCEFIGDHBAECIF前序中序48习题8.试找出满足下列条件的二叉树1）先序序列与中序序列相同2）中序序列与后序序列相同3）先序序列与后序序列相同答案1）不含左子树的二叉树2）不含右子树的二叉树3）空二叉树或只含根结点的二叉树49习题4.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是()的二叉树A．空或只有一个结点B.高度等于其结点数C．任一结点无左孩子D.任一结点无右孩子先序：根左右后序：左右根答案：B506.4线索二叉树51ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA一、何谓线索二叉树？遍历二叉树的结果是，求得结点的一个线性序列52ADEBCFrootABDCEF缺点：空指针较多，找某个序列的前序后继不方便53指向某遍历序列中的“前驱”和“后继”的指针，称作“线索”包含“线索”的存储结构，称作“线索链表”与其相应的二叉树，称作“线索二叉树”利用链表中空的左指针指向遍历序列的前驱利用链表中空的右指针指向遍历序列的后继5455对线索链表中结点的约定：在二叉链表的结点中增加两个标志域，标志二叉树中的左右指针指向的是前驱还是后继Tag值为1表示存的是线索值为0表示存的是孩子56Tag值为1表示存的是线索值为0表示存的是孩子中序线索57Tag值为1表示存的是线索值为0表示存的是孩子中序线索58typedefstructBiThrNod{TElemTypedata;structBiThrNode*lchild,*rchild;PointerThrLTag,RTag;}BiThrNode,*BiThrTree;线索链表的类型typedefenum{Link,Thread}PointerThr;Link值为0:指针，Thread值为1:线索59二、线索链表的遍历算法:中序线索由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。60中序线索化链表的遍历算法

※中序遍历的第一个结点？

※在中序线索树中结点的后继是哪个结点？左子树上处于”最左下”(没有左子树)的结点。若某节点无右子树，则其后继是右指针所指结点否则为对其右子树进行中序遍历时访问的第一个结点。61若某节点无右子树，则其后继是右指针所指结点ADEBCFroot626.5树和森林树的存储结构树和二叉树之间的转换森林和二叉树的转换树和森林的遍历63树的存储结构ABECDF双亲表示法

孩子链表表示法

孩子兄弟链表表示法

64孩子链表表示法顺序存储结点+链式存储孩子结构；找孩子容易，找双亲难；0123456765孩子兄弟链表表示法两个指针：左孩子指针，右孩子指针66双亲表示法树的双亲表示法主要描述的是结点的双亲关系顺序表示，存放顶点和双亲信息67请画出该树的孩子链表结构图请画出该树的孩子兄弟链表结构图双亲表示法结构图68树的遍历前序遍历树若树非空，则：（1）访问树的根结点；（2）依次前序遍历树的第一棵子树、第二棵子树，……69树的遍历后序遍历树若树非空，则：（1）依次后序遍历树的第一棵子树、第二棵子树，……（2）访问树的根结点；70树的遍历层次遍历树1）访问树的根结点；2）依次前序遍历树的第一层结点、第二结点，……71ABCED前序遍历序列：后序遍历序列：层次遍历序列：ABCDEBCEDAABCDE72森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟树、森林与二叉树的关系树与二叉树的相互转换森林与二叉树的相互转换731.树与二叉树的相互转换树转换成的二叉树其右子树一定为空742.森林与二叉树的相互转换75森林转换为二叉树76森林转换为二叉树77习题将二叉树转换成树ABCDEFGHIJKLABCDEFGHIJKLCDABCDEFGHIJKLC78DEFGHIJLABCKFILCABEGHJKD习题二叉树到森林的转换79习题设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是()。A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右边兄弟C.在树T中，X一定是叶子结点D.在树T中，X一定有左边兄弟答案：D806.6哈夫曼树及其应用6.6.1哈夫曼树树的路径长度：树的根结点到树中每一个结点的路径长度的和。结点的带权的路径长度：该结点到根结点之间的路程长度与该结点上权的乘积81树的带权的路径长度：树中所有叶子结点的带权的路径长度的和。通常记为：WPL(WeightedPathLength)。由n个带权值的叶子结点构成的二叉树中，WPL最小的二叉树称为最优二叉树，或哈夫曼（Huffman）树。82有4个结点，权值分别为7，5，2，4，构造有4个叶子结点二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35dcab247583由n个带权值的叶子结点构成的二叉树中，WPL最小的二叉树称为最优二叉树，或哈夫曼（Huffman）树。abcd7524哈夫曼树的形态是不唯一84根据给定的n个权值{w1,w2,…,wn}，构造n棵只有根结点的二叉树，令其权值为wj;在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和;在森林中删除这两棵树，同时将新得到的二叉树加入森林中;重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。构造Huffman树步骤859例如:已知权值W={5,6,2,9,7}562786957267例如:已知权值W={5,6,2,9,7}8795726713例如:已知权值W={5,6,2,9,7}889572671316例如:已知权值W={5,6,2,9,7}89957267131629例如:已知权值W={5,6,2,9,7}90957262971316根据权值构造得到哈夫曼树构造哈夫曼树的目的是什么呢？例如:已知权值W={5,6,2,9,7}91在计算机及通信中，常用二进制编码来表示字符例如用00、01、10、11分别表示字母A、B、C、D若A、B、C、D出现的频率是一样的，传输100个字母用200个二进制位。前缀码6.6.2哈夫曼编码92A出现的频率为50％B出现的频率为25％C出现的频率为20％D出现的频率为5％用不等长的二进制序列表示字母A、B、C、D使传输的信息的二进制位尽可能少000表示D用001表示C01表示B1表示A传输100个字母所用的二进制位为3×5+3×20+2×25+1×50=175000011001表示什么？2，前缀码DBAC93但当我们用000表示D001表示C00表示B