第五章二叉树及应用课件

第五章第五章 二叉树及应用二叉树及应用一种重要的非线性结构一种重要的非线性结构学习要点：学习要点：二叉树的递归概念，这与二叉树各种基本运算具有密切关联。二叉树的递归概念，这与二叉树各种基本运算具有密切关联。满二叉树和完全二叉树概念，二叉树和完全二叉树基本性质。满二叉树和完全二叉树概念，二叉树和完全二叉树基本性质。二叉树的顺序存储与二叉链表存储结构。二叉树的顺序存储与二叉链表存储结构。二叉树遍历的基本思想和基于递归与非递归实现算法。二叉树遍历的基本思想和基于递归与非递归实现算法。线索二叉树概念，二叉树的线索化和遍历。线索二叉树概念，二叉树的线索化和遍历。Huffman树概念与基本算法；树概念与基本算法；Huffman编码和实现算法。编码和实现算法。25.1 二叉树及其基本性质二叉树及其基本性质5.1.1 二叉树基本概念二叉树基本概念“二叉树二叉树”是一个满足下述条件的由结点组成的有限集合是一个满足下述条件的由结点组成的有限集合E：当当E为空集时，定义其为空二叉树；为空集时，定义其为空二叉树；当当E非空时，分为两种情形。非空时，分为两种情形。如果如果E为单元素集合，定义其为一棵为单元素集合，定义其为一棵根二叉树根二叉树；如果如果E为多于一个结点的集合，则为多于一个结点的集合，则E中应当具有唯一一个结点中应当具有唯一一个结点r称称其为根结点，而集合其为根结点，而集合E=E r也是一棵二叉树，称为也是一棵二叉树，称为r的子二叉的子二叉树。此时，结点树。此时，结点r至多只能有两棵不相交的子二叉树，并且相应至多只能有两棵不相交的子二叉树，并且相应子二叉树有左右之分，分别称为子二叉树有左右之分，分别称为r的的左子树左子树和和右子树右子树。3其它一些相关概念：其它一些相关概念：结点的结点的度：度：结点拥有的子树棵数结点拥有的子树棵数 结点的结点的深度深度（层次层次）：）：根结点看做第根结点看做第0层，其余结点的层次值为其层，其余结点的层次值为其父结点所在层值加父结点所在层值加1 树的度：树的度：树中所有结点度的最大值树中所有结点度的最大值树的深度：树的深度：树中最大层次数树中最大层次数 4根结点、叶结点、内部结点根结点、叶结点、内部结点子结点、父结点、兄弟结点、堂兄弟结点、子结点、父结点、兄弟结点、堂兄弟结点、子孙结点、祖先结点；子孙结点、祖先结点；5.1.1 二叉树基本概念二叉树基本概念21、二叉树的特征、二叉树的特征二叉树可以没有任何结点，即是一个空二叉树。二叉树可以没有任何结点，即是一个空二叉树。二叉树中每个结点至多只有两棵子树，而这两棵子树作为结点二叉树中每个结点至多只有两棵子树，而这两棵子树作为结点集合互不相交；集合互不相交；二叉树中结点的两棵子树有左、右之分，次序不能颠倒。二叉树中结点的两棵子树有左、右之分，次序不能颠倒。2、二叉树基本类型、二叉树基本类型55.1.2 满二叉树和完全二叉树满二叉树和完全二叉树1、满二叉树、满二叉树 如果一棵二叉树满足下述条件，就称其为满二叉树（如果一棵二叉树满足下述条件，就称其为满二叉树（full binary tree）：）：每个结点或是度数为每个结点或是度数为2（具有两个非空子树）的结点，或是（具有两个非空子树）的结点，或是度数为度数为0的（叶）结点；的（叶）结点；所有叶结点都在同一层。所有叶结点都在同一层。65.1.2 满二叉树和完全二叉树满二叉树和完全二叉树22、完全二叉树、完全二叉树若一棵二叉树满足下述条件，就称其为完全二叉树若一棵二叉树满足下述条件，就称其为完全二叉树（complete binary tree）：）：至多只有最下两层中结点的度数小于至多只有最下两层中结点的度数小于2；最下一层的叶结点都依次排列在该层最左边位置。最下一层的叶结点都依次排列在该层最左边位置。75.1.2 满二叉树和完全二叉树满二叉树和完全二叉树22、完全二叉树、完全二叉树2重点理解：重点理解：满二叉树是完全二叉树，但完全二叉树却不一定是满二叉树。满二叉树是完全二叉树，但完全二叉树却不一定是满二叉树。空二叉树和根二叉树既是满二叉树，也是完全二叉树。空二叉树和根二叉树既是满二叉树，也是完全二叉树。完全二叉树可以看作是在满二叉树的最下一层，从右向左连续去完全二叉树可以看作是在满二叉树的最下一层，从右向左连续去掉若干个结点后得到二叉树。掉若干个结点后得到二叉树。完全二叉树中的一个结点如果没有左子结点，就一定没有右子结完全二叉树中的一个结点如果没有左子结点，就一定没有右子结点。点。8练习：练习：1、完全二叉树某结点若无右子树则定无左子树。、完全二叉树某结点若无右子树则定无左子树。2、完全二叉树某结点若无左子树则定无右子树。、完全二叉树某结点若无左子树则定无右子树。95.1.3 二叉树基本性质二叉树基本性质性质性质5-1 一棵二叉树第一棵二叉树第i（i0）层上至多只能有）层上至多只能有 个结点。个结点。102i证明：应用数学归纳法。证明：应用数学归纳法。二叉树第二叉树第0层有一个结点，即当层有一个结点，即当i=0时，时，2i=20=1成立。成立。假设结论对第假设结论对第i层成立，即第层成立，即第i层至多只能有层至多只能有2i个结点。注意到个结点。注意到二叉树每个结点的度最多为二叉树每个结点的度最多为2，第，第i+1层结点个数至多只能层结点个数至多只能是第是第i层结点个数的层结点个数的2倍，即倍，即2*2i=2i+1，归纳完成，命题得，归纳完成，命题得证。证。5.1.3 二叉树基本性质二叉树基本性质211性质性质5-2 树高为树高为k（k0）的二叉树，最多有）的二叉树，最多有 个结点。个结点。2k+1-1证明证明：由性质由性质5-1可知在树高为可知在树高为k的二叉树当中，第的二叉树当中，第0层有层有20个结点，第个结点，第1层有层有21个结点，第个结点，第2层有层有22个结点，个结点，第，第k层有层有2k个结点。由个结点。由此可知，树高为此可知，树高为k的二叉树结点个数总数为的二叉树结点个数总数为20+21+22+2k。这是一个公比为这是一个公比为p=2的等比数列，前的等比数列，前k+1项和项和Sk+1为：为：Sk+1=（a0 ak p）/（1p）=(202k 2)/(12)=(12k+1)/(12)=2k+115.1.3 二叉树基本性质二叉树基本性质3性质性质5-3 如果二叉树中度为如果二叉树中度为0结点数为结点数为n0，度为，度为2结点数为结点数为n2，则则 成立。成立。12n0=n2+1证明：设结点总数证明：设结点总数 n=n0+n1+n2 又因为：结点数又因为：结点数n=边数边数+1 边数边数=n1+2*n2 即即n0+n1+n2=n1+2n2+1 所以：所以：n0=n2+1结点数结点数n=边数边数+1练习：练习：一棵树的度为一棵树的度为4，n4=2，n3=3，n2=4，求，求n0？13解：解：结点数结点数=边数边数+1 n0+n1+n2+n3+n4=n1+2*n2+3*n3+4*n4+1 n0+2+3+4=8+9+8+1 n0=17练习：练习：设完全二叉树有设完全二叉树有1000个结点，求叶子结点个数？有多少个个结点，求叶子结点个数？有多少个度为度为1的结点？度为的结点？度为2的结点呢？的结点呢？14解：设二叉树中叶子结点、度为解：设二叉树中叶子结点、度为1、度为、度为2的结点数目的结点数目 分别分别n0、n1、n2，其中完全二叉树中其中完全二叉树中n1只能为只能为1或或0，则：，则：n0+n1+n2=1000n0=n2+1n1=0 或或 n1=1n0=500n1=1n2=499复习两个概念：复习两个概念：（1）满二叉树满二叉树：深度为：深度为k的满二叉树有的满二叉树有 个结点。个结点。152k+1-1 对满二叉树按层次从上到下，从左到右，不留一个空对满二叉树按层次从上到下，从左到右，不留一个空位进行编号，号码位进行编号，号码1n。（2）完全二叉树完全二叉树：结点数为：结点数为n的完全二叉树上各个结点与同深的完全二叉树上各个结点与同深度的满二叉树前度的满二叉树前n个相应位置结点编号一一对应。个相应位置结点编号一一对应。5.1.3 二叉树基本性质二叉树基本性质416性质性质5-4 设设BT为具为具n个结点的完全二叉树，将个结点的完全二叉树，将BT所有结点按照所有结点按照从上到下、从左到右的顺序（二叉树的层序）进行编号。则从上到下、从左到右的顺序（二叉树的层序）进行编号。则BT中任意结点中任意结点N的序号的序号i（1in）具有下述性质。）具有下述性质。（1）若）若i=1，则，则N为为BT根结点，根结点，N无父结点；无父结点；（2）若）若i1，则，则N父结点序号为父结点序号为 （即（即i除以除以2后向下取整）；后向下取整）；（3）若）若2in，则，则N无左子树，否则其左子结点（即左子树的根无左子树，否则其左子结点（即左子树的根结点）序号为结点）序号为2i；（4）若）若2i+1n，则，则N无右子树，否则其右子结点（即右子树的无右子树，否则其右子结点（即右子树的根结点）序号为根结点）序号为2i+1。练习：练习：1、1000个结点的完全二叉树最大的分支结点编号为个结点的完全二叉树最大的分支结点编号为 。2、n个结点的完全二叉树深度为个结点的完全二叉树深度为 。17500int（log2n）5.2 二叉树存储二叉树存储5.2.1 二叉树顺序存储二叉树顺序存储 预留最大空间预留最大空间 深度为深度为k的二叉树预留的二叉树预留2k+1-1个存储单元，按编号顺序存个存储单元，按编号顺序存储，遇空结点留空位。储，遇空结点留空位。185.2.1 二叉树顺序存储二叉树顺序存储2适合满（完全）二叉树，求双亲、孩子方便适合满（完全）二叉树，求双亲、孩子方便不适合深度较大、结点不多的二叉树不适合深度较大、结点不多的二叉树195.2.2 二叉树链式存储二叉树链式存储1、二叉链表存储、二叉链表存储 让一个存储结点只包含与其子树的邻接关系，那么就是让一个存储结点只包含与其子树的邻接关系，那么就是二叉树的二叉链表存储结构。二叉树的二叉链表存储结构。205.2.2 二叉树链式存储二叉树链式存储1、二叉链表存储、二叉链表存储221用用C语言定义二叉链表的结构类型如下：语言定义二叉链表的结构类型如下：struct node DataType data;/*定义数据域，定义数据域，DataType代表实际需要的类型代表实际需要的类型*/struct node *lch;/*定义左孩子域，指向左孩子地址定义左孩子域，指向左孩子地址*/struct node *rch;/*定义右孩子域，指向右孩子地址定义右孩子域，指向右孩子地址*/;typedef struct node bitree;/*定义二叉树结点类型为定义二叉树结点类型为bitree*/1、二叉链表存储、二叉链表存储3算法算法5-1 创建一棵只有根结点的二叉树算法。创建一棵只有根结点的二叉树算法。创建只有以创建只有以x为根结点的二叉树为根结点的二叉树Bt，x的数据类型为的数据类型为DataType，相，相应结点的应结点的Lchild和和Rchild域均取值域均取值NULL，返回指向根结点的指针。，返回指向根结点的指针。2200Create_Bt(DataType x)01 02 bitree*Bt,*ptr;03 ptr=(bitree*)malloc(sizeof(bitree);/*申请存储结点申请存储结点*/04 Bt=ptr;05 ptr-data=x;06 ptr-lch=NULL;07 ptr-rch=NULL;08 return(Bt);09 1、二叉链表存储、二叉链表存储4算法算法5-2 在指定左子结点处插入一个新结点。在指定左子结点处插入一个新结点。已知二叉链表已知二叉链表Bt，在指针，在指针Parent所指结点左子结点处插入一个数所指结点左子结点处插入一个数据元素值为据元素值为x的新结点，使之成为的新结点，使之成为Parnet所指结点新的左子树根结点。所指结点新的左子树根结点。23 bitree*Inl_Bt(bitree*Bt,bitree*Parent,DataType x)if(Parent=NULL)printf(位置错！位置错！);return(NULL);ptr=(bitree*)malloc(sizeof(bitree);/*申请存储结点空间申请存储结点空间*/ptr-data=x;ptr-lch=NULL;ptr-rch=NULL;if(Parent-lch=NULL)/*Parent所指结点左子树为空所指结点左子树为空*/Parent-lch=ptr;else /*Parent所指结点左子树非空所指结点左子树非空*/ptr-lch=Parent-lch;Parent-lch=ptr;return(Bt)5.2.2 二叉树链式存储二叉树链式存储22、三叉链表存储、三叉链表存储 同时反映当前结点与其左子树的根结点、右子树的根同时反映当前结点与其左子树的根结点、右子树的根结点和与其父结点关联。结点和与其父结点关联。245.2.2 二叉树链式存储二叉树链式存储22、三叉链表存储、三叉链表存储2255.3 二叉树的遍历二叉树的遍历按照某种确定方式对二叉树进行访问，但要求二叉树中每按照某种确定方式对二叉树进行访问，但要求二叉树中每个结点被访问一次且只被访问一次。个结点被访问一次且只被访问一次。1、先序、中序和后序遍历、先序、中序和后序遍历对左、右子树，限定对左、右子树，限定“先访左后访右先访左后访右”，那么访问结点的，那么访问结点的顺序顺序有有三种不同的组合形式：三种不同的组合形式：TLR、LTR、LRT。通常，称通常，称TLR为二叉树的先序（先根）遍历，为二叉树的先序（先根）遍历，LTR为中序为中序（中根）遍历，（中根）遍历，LRT为后序（后根）遍历。为后序（后根）遍历。26例子：例子：以三种遍历方式访问如图所示的二叉树。以三种遍历方式访问如图所示的二叉树。27解：解：先序遍历序列先序遍历序列 A-B-D-H-E-C-F-I-G-J-K中序遍历序列中序遍历序列 D-H-B-E-A-I-F-C-J-G-K后序遍历序列后序遍历序列 H-D-E-B-I-F-J-K-G-C-A例子：例子：已知二叉树已知二叉树先先序遍历序列是序遍历序列是A-B-C-D-E-F-G，中序遍历序，中序遍历序列是列是C-B-D-A-E-G-F。由这两个序列可唯一确定一棵二叉树。由这两个序列可唯一确定一棵二叉树。28解：从先序遍历序列第一个结点可知二叉树根结点是解：从先序遍历序列第一个结点可知二叉树根结点是A。由结点。由结点A在在中序遍历序列里位置可知该根结点左子树包含结点中序遍历序列里位置可知该根结点左子树包含结点C-B-D，右子树包，右子树包含结点含结点E-G-F，如图，如图5-22所示。由中序序列片段所示。由中序序列片段C-B-D可知，可知，B是是A左子树根结点，再结合先序序列片段左子树根结点，再结合先序序列片段B-C-D可知，可知，C和和D分别是分别是B的的左右子结点。由先序序列片段左右子结点。由先序序列片段E-F-G可知，可知，E是是A的右子结点，再由的右子结点，再由先序序列片段先序序列片段F-G和中序序列片段和中序序列片段G-F可知，可知，F不能是不能是E的左子结点，的左子结点，故只能是故只能是E的右子结点，并且的右子结点，并且G是是F的左子结点。的左子结点。29练习：练习：1、已知二叉树先序遍历序列为、已知二叉树先序遍历序列为ABCDEFGH，中序遍历序列为，中序遍历序列为CDBAFEHG，试画出此二叉树。，试画出此二叉树。2、已知二叉树后序遍历序列为、已知二叉树后序遍历序列为DCBFHGEA，中序遍历序列为，中序遍历序列为CDBAFEHG，求先序遍历序列。，求先序遍历序列。305.3 二叉树的遍历二叉树的遍历22、基于递归遍历算法、基于递归遍历算法递归步骤递归步骤（先序遍历先序遍历）：）：访问根结点；访问根结点；先序遍历访问左子二叉树；先序遍历访问左子二叉树；先序遍历访问右子二叉树。先序遍历访问右子二叉树。312、基于递归遍历算法、基于递归遍历算法2算法算法5-4 二叉树先序遍历递归算法。二叉树先序遍历递归算法。已知二叉树已知二叉树Bt，对其进行先序遍历，若二叉树为空，则为空操作；否则进，对其进行先序遍历，若二叉树为空，则为空操作；否则进行如下操作：访问二叉树根结点；先序遍历二叉树的左子树；先序遍历二叉树行如下操作：访问二叉树根结点；先序遍历二叉树的左子树；先序遍历二叉树的右子树。的右子树。3200 Pret_Bt(bitree*Bt)01 02 if(Bt!=NULL)03 04 printf(%c,Bt-data);/*访问根结点访问根结点*/05 Pret_Bt(Bt-lch);/*先序遍历左子树先序遍历左子树*/06 Pret_Bt(Bt-rch);/*先序遍历右子树先序遍历右子树*/07 08 2、基于递归遍历算法、基于递归遍历算法2基于递归调用先序遍历基于递归调用先序遍历:332、基于递归遍历算法、基于递归遍历算法2先序递归算法应用实例先序递归算法应用实例:先序建立二叉树先序建立二叉树bitree *creat()bitree *t;int x;scanf(“%d”,&x);if(x=0)t=NULL;else t=(bitree*)malloc(sizeof(bitree);t-data=x;t-lch=creat();t-rch=creat();return t;2、基于递归遍历算法、基于递归遍历算法2先序递归算法应用实例先序递归算法应用实例:先序建立二叉树先序建立二叉树(续续)主程序调用主程序调用:main()bitree *root;root=creat();例：例：建立如图二叉树应该如何输入？建立如图二叉树应该如何输入？练习：练习：测试用例：测试用例：1 2 3 0 0 4 0 5 0 0 6 0 0 问：画出建立的二叉树？问：画出建立的二叉树？2、基于递归遍历算法、基于递归遍历算法3算法算法5-5 二叉树中序遍历递归算法。二叉树中序遍历递归算法。已知二叉树已知二叉树Bt，对其进行中序遍历，若二叉树为空，则为空操作；否则进，对其进行中序遍历，若二叉树为空，则为空操作；否则进行如下操作：中序遍历二叉树的左子树；访问二叉树根结点；中序遍历二叉树行如下操作：中序遍历二叉树的左子树；访问二叉树根结点；中序遍历二叉树的右子树。的右子树。3600 Indt_Bt(bitree*Bt)01 02 if(Bt!=NULL)03 04 Indt_Bt(Bt-lch);/*中序遍历左子树中序遍历左子树*/05 printf(%c,Bt-data);/*访问根结点访问根结点*/06 Indt_Bt(Bt-rch);/*中序遍历右子树中序遍历右子树*/07 08 2、基于递归遍历算法、基于递归遍历算法3基于递归调用基于递归调用中中序遍历序遍历:372、基于递归遍历算法、基于递归遍历算法4算法算法5-6 二叉树后序遍历递归算法。二叉树后序遍历递归算法。已知二叉树已知二叉树Bt，对其进行后序遍历，若二叉树为空，则为空操作；否则进，对其进行后序遍历，若二叉树为空，则为空操作；否则进行如下操作：后序遍历二叉树的左子树；后序遍历二叉树的右子树；访问二叉行如下操作：后序遍历二叉树的左子树；后序遍历二叉树的右子树；访问二叉树根结点。树根结点。3800 Postv_Bt(bitree*Bt)01 02 if(Bt!=NULL)03 04 Postv_Bt(Bt-lch);/*后序遍历左子树后序遍历左子树*/05 Postv_Bt(Bt-rch);/*后序遍历右子树后序遍历右子树*/06 printf(%c,Bt-data);/*访问根结点访问根结点*/07 08 2、基于递归遍历算法、基于递归遍历算法4基于递归调用基于递归调用后后序遍历序遍历:395.3 二叉树的遍历二叉树的遍历33、基于非递归遍历算法、基于非递归遍历算法非递归遍历算法中，需要做出三条假设：非递归遍历算法中，需要做出三条假设：设置一个一维数组设置一个一维数组Ss作为顺序栈以临时保存遍历时遇到的结作为顺序栈以临时保存遍历时遇到的结点信息，其栈顶指针为点信息，其栈顶指针为Ss-top，初始时为，初始时为0。采用二叉链表结构保存需要遍历的二叉树，起始指针为采用二叉链表结构保存需要遍历的二叉树，起始指针为Bt，每个结点包含每个结点包含Data、Lchild和和Rchild等三个域。等三个域。对结点进行的对结点进行的“访问访问”理解为将该结点的理解为将该结点的Data域的值打印出域的值打印出来。来。403、基于非递归遍历算法、基于非递归遍历算法2算法算法5-7 先序遍历二叉树的非递归算法。先序遍历二叉树的非递归算法。已知二叉树已知二叉树Bt，顺序栈，顺序栈Ss，要求打印出该二叉树的先序遍历序列。，要求打印出该二叉树的先序遍历序列。4100 Pre_Bt(bitree*Bt)01 02 bitree*p;03 bitree*stack10;/*定义栈数组定义栈数组*/04 int top=-1;/*定义栈顶下标定义栈顶下标top并赋初值并赋初值-1*/05 printf(nOutput preorder:);06 p=Bt;07 while(p!=NULL|top!=-1)08 if(p!=NULL)09 10 printf(%d ,p-data);/*访问该结点访问该结点*/11 top=top+1;stacktop=p;/*访问后入栈访问后入栈*/12 p=p-lch;/*继续深入左孩子继续深入左孩子*/13 14 else15 16 p=stacktop;top=top-1;/*遇空出栈，栈顶给遇空出栈，栈顶给p*/17 p=p-rch;/*转向右孩子转向右孩子*/18 19 3、基于非递归遍历算法、基于非递归遍历算法2基于非递归二叉树先序遍历：基于非递归二叉树先序遍历：423、基于非递归遍历算法、基于非递归遍历算法3中序非递归遍历算法流程中序非递归遍历算法流程:v bitree*p;定义及初始化栈定义及初始化栈;v p=root;v while(p!=NULL|栈不空栈不空)v if(p!=NULL)v p进栈；进栈；p=p-lch;v elsev 栈顶给栈顶给p并出栈；并出栈；输出输出p；p=p-rch;3、基于非递归遍历算法、基于非递归遍历算法3算法算法5-8 中序遍历二叉树的非递归算法。中序遍历二叉树的非递归算法。已知二叉树已知二叉树Bt，顺序栈，顺序栈Ss，要求打印出该二叉树的中序遍历序列。，要求打印出该二叉树的中序遍历序列。4400 In_Bt(bitree*Bt)01 02 bitree*stack10;/*定义栈数组定义栈数组*/03 int top=-1;/*定义栈顶下标定义栈顶下标top并赋初值并赋初值-1*/04 bitree*ptr;05 ptr=Bt;/*ptr是工作指针是工作指针*/06 do07 08 while(ptr!=NULL)/*一直朝左子树深入下去一直朝左子树深入下去*/09 10 top+;/*调整栈顶指针调整栈顶指针*/11 stacktop=ptr;/*ptr所指结点进栈所指结点进栈*/12 ptr=ptr-lch;1314 if(Ss_top!=-1)15 16 ptr=stacktop;/*栈顶元素赋值给栈顶元素赋值给ptr*/17 top-;/*出栈出栈*/18 printf(%d ,ptr-data);/*访问该结点访问该结点*/19 ptr=ptr-rch;/*进入右子树访问进入右子树访问*/20 21 while(ptr!=NULL)|(top!=-1);22 3、基于非递归遍历算法、基于非递归遍历算法3基于非递归二叉树中序遍历（基于非递归二叉树中序遍历（1-4趟）：趟）：453、基于非递归遍历算法、基于非递归遍历算法3基于非递归二叉树中序遍历（基于非递归二叉树中序遍历（1-4趟）：趟）：463、基于非递归遍历算法、基于非递归遍历算法4算法算法5-9 后序遍历二叉树的非递归算法（略）。后序遍历二叉树的非递归算法（略）。已知二叉树已知二叉树Bt，顺序栈，顺序栈Ss，要求打印出该二叉树的后序遍历序列。，要求打印出该二叉树的后序遍历序列。47算法要点：算法要点：由于后序遍历是由于后序遍历是“左、右、根左、右、根”，因此在后序遍历过程中搜索，因此在后序遍历过程中搜索到某个结点时，不是马上访问它，而是将其作为相应子树根结点保到某个结点时，不是马上访问它，而是将其作为相应子树根结点保存在工作栈中，然后沿着其左子树继续深入直到存在工作栈中，然后沿着其左子树继续深入直到“最左下最左下”结点。结点。完成对其左子树访问后，从工作栈顶元素中获得相应根结点信息，完成对其左子树访问后，从工作栈顶元素中获得相应根结点信息，但仍然不能马上进行访问，而是在工作栈中对其进行但仍然不能马上进行访问，而是在工作栈中对其进行第二次保存第二次保存，同时对其右子树进行遍历。在访问完右子树后，从工作栈中得到根同时对其右子树进行遍历。在访问完右子树后，从工作栈中得到根结点信息，由此实现对相应根结点访问。结点信息，由此实现对相应根结点访问。3、基于非递归遍历算法、基于非递归遍历算法4基于非递归二叉树后序遍历第基于非递归二叉树后序遍历第1-3趟运算变化：趟运算变化：483、基于非递归遍历算法、基于非递归遍历算法4基于非递归二叉树后序遍历第基于非递归二叉树后序遍历第4趟运算变化：趟运算变化：493、基于非递归遍历算法、基于非递归遍历算法4基于非递归二叉树后序遍历第基于非递归二叉树后序遍历第5-7趟运算变化：趟运算变化：50上机：上机：1、用先序、用先序递归方法递归方法建立一棵二叉树；建立一棵二叉树；2、用中序、用中序非递归非递归方法遍历该二叉树。方法遍历该二叉树。515.4 线索二叉树线索二叉树5.4.1 线索与线索二叉树线索与线索二叉树 结合遍历方式特点使用这些空链域来存放相应前驱或后继信结合遍历方式特点使用这些空链域来存放相应前驱或后继信息即前驱或后继的地址。息即前驱或后继的地址。当前结点左孩子域非空时，保留原指针不变；当左孩子域为空时，当前结点左孩子域非空时，保留原指针不变；当左孩子域为空时，添加该结点在相应历序列中前驱结点地址。添加该结点在相应历序列中前驱结点地址。当前结点右孩子域非空时，保留原指针不变；当右孩子域为空时，当前结点右孩子域非空时，保留原指针不变；当右孩子域为空时，添加该结点在相应遍历序列中后继结点地址。添加该结点在相应遍历序列中后继结点地址。525.4.1 线索与线索二叉树线索与线索二叉树2一个中序线索二叉树的例子：一个中序线索二叉树的例子：535.4.2 创建线索二叉树创建线索二叉树1、创建线索二叉树结点、创建线索二叉树结点54算法算法5-10（线索二叉树结点结构）（线索二叉树结点结构）01 struct ThreadNode /*线索二叉树结点的定义线索二叉树结点的定义*/02 03 DataType info;04struct ThreadNode llink,rlink;05 int ltag,rtag;06 ;07 typedef struct ThreadNode ThreadTree;/*线索二叉树类型的定义线索二叉树类型的定义*/5.4.2 创建线索二叉树创建线索二叉树22、二叉树的线索化、二叉树的线索化55在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱前驱”和和“后继后继”信息。遍历过程中，附设指针信息。遍历过程中，附设指针pre，并始终保持指针，并始终保持指针pre指向当前访问的、指针指向当前访问的、指针p所指结点的前驱。将给定二叉树扩充为线索二所指结点的前驱。将给定二叉树扩充为线索二叉树的过程称为二叉树的线索化，也就是线索二叉树的创建。叉树的过程称为二叉树的线索化，也就是线索二叉树的创建。线索化实际上就是在遍历过程中线索化实际上就是在遍历过程中在当前结点的空链域中添加前驱或后在当前结点的空链域中添加前驱或后继指针继指针。为了保留遍历过程中访问结点的前驱与后继关系，需要设置一个。为了保留遍历过程中访问结点的前驱与后继关系，需要设置一个工作指针工作指针pre始终指向刚访问过的结点，也就是说，当指针始终指向刚访问过的结点，也就是说，当指针p指向当前访问指向当前访问结点时，结点时，pre就指向就指向p的前驱结点。的前驱结点。5.4.2 创建线索二叉树创建线索二叉树33、线索二叉树遍历、线索二叉树遍历56以下以对中序线索化链表为例讨论基于线索的二叉树中序遍历算以下以对中序线索化链表为例讨论基于线索的二叉树中序遍历算法。此时，算法关键点有二：法。此时，算法关键点有二：怎样获取中序遍历的首结点？怎样获取中序遍历的首结点？从根结点沿着左指针不断向左下搜寻，直到给定二叉树左子树的从根结点沿着左指针不断向左下搜寻，直到给定二叉树左子树的处于处于“最左下最左下”的结点，结点是的结点，结点是“最左下最左下”的含义是该结点再无左子的含义是该结点再无左子结点，亦即该结点的左指针域为空。结点，亦即该结点的左指针域为空。怎样获取在中序线索化链表中当前结点的后继结点？怎样获取在中序线索化链表中当前结点的后继结点？如果当前结点没有无右子树，则其后继结点即为其右指针域中后如果当前结点没有无右子树，则其后继结点即为其右指针域中后继线索所指结点；如果当前结点存在右子树，则从该右子树根结点开继线索所指结点；如果当前结点存在右子树，则从该右子树根结点开始沿左指针行进，直到右子树始沿左指针行进，直到右子树“最左下最左下”结点，此即为当前结点的后结点，此即为当前结点的后继。继。5.4.2 创建线索二叉树创建线索二叉树33、线索二叉树遍历、线索二叉树遍历257算法算法5-12基于中序线索二叉树中序遍历算法基于中序线索二叉树中序遍历算法00 void thrInOrder(ThreadTree *root)01 02 ThreadTree *p;03 p=root-llink;04 if(p=NULL)05 return;06 while(p-llink!=NULL&p-ltag=0)07 p=p-llink;/*一直到一直到“最左下最左下”*/08 while(p!=root)09 10 printf(%d ,p-info);11 if(p-rlink!=NULL&p-rtag=0)/*右子树不是线索时右子树不是线索时*/12 13 p=p-rlink;14 while(p-llink!=NULL&p-ltag=0)15 p=p-llink;/*顺右子树的左子树一直向下顺右子树的左子树一直向下*/16 17 else18 p=p-rlink;19 20 5.5 Huffman编码编码5.5.1 等长与非等长编码等长与非等长编码 所谓编码（所谓编码（code），就是用一组不同的代码表示一个数据对），就是用一组不同的代码表示一个数据对象集合中的每个元素的过程。象集合中的每个元素的过程。1、两种基本编码类型、两种基本编码类型编码三要素：编码三要素：唯一性：唯一性：发送方传输编码字段，接收方解码后必须具有唯一性，发送方传输编码字段，接收方解码后必须具有唯一性，解码结果与发送原文保持相同；解码结果与发送原文保持相同；简洁性：简洁性：发送的编码应该尽可能做到简洁短小，减少存储代价和发送的编码应该尽可能做到简洁短小，减少存储代价和提高传输效率。提高传输效率。前缀性：前缀性：两个编码字节不使用特殊标记如标点符号进行分隔，一两个编码字节不使用特殊标记如标点符号进行分隔，一个编码字节不能是另一个编码字节的前缀，应具有个编码字节不能是另一个编码字节的前缀，应具有“前缀性前缀性”（Prefix Property）；）；585.5.1 等长与非等长编码等长与非等长编码22、最优二叉树与、最优二叉树与Huffman树树二叉树路径长度二叉树路径长度：一棵二叉树的所有从根结点到每个叶结点路径：一棵二叉树的所有从根结点到每个叶结点路径长度之和称为该二叉树的长度之和称为该二叉树的“路径长度路径长度”。叶结点的权叶结点的权：赋给二叉树叶结点一个具有某种意义的实数，则称：赋给二叉树叶结点一个具有某种意义的实数，则称此数为该叶结点的此数为该叶结点的“权权”。二叉树带权路径长度二叉树带权路径长度：设二叉树具有：设二叉树具有n个带权的叶结点，则从根结个带权的叶结点，则从根结点到各叶结点的路径长度与相应结点权值乘积之和称为该二叉点到各叶结点的路径长度与相应结点权值乘积之和称为该二叉树的树的“带权路径长度带权路径长度”，记为：，记为：59WPL=wklk（wk是第是第k个叶结点权值，个叶结点权值，lk是第是第k个叶结点路径长度个叶结点路径长度）“Huffman树树”：由由带有权值的一组相同叶结点所构成二叉树当中，带有权值的一组相同叶结点所构成二叉树当中，称其中带权路径长度最小的二叉树为是称其中带权路径长度最小的二叉树为是“最优二叉树最优二叉树”。5.5.2 Huffman树构建思想树构建思想设有设有n个权值个权值w1、w2、w3、wn，则可按照下述步骤，则可按照下述步骤构造构造Huffman树：树：Step 1.构造构造n棵只有一个根结点的二叉树森林棵只有一个根结点的二叉树森林 HT=T1，T2，T3，Tn，它们分别以，它们分别以w1、w2、w3、wn作为权值。作为权值。Step 2.在在HT集合中，选取权值最小和次小的两个根结点作为一集合中，选取权值最小和次小的两个根结点作为一棵新二叉树的左子树和右子树。新二叉树根结点权值是其左、右子棵新二叉树的左子树和右子树。新二叉树根结点权值是其左、右子树根结点权值之和；树根结点权值之和；Step 3.在在HT集合中，删除已经取为左、右子树的原两棵二叉集合中，删除已经取为左、右子树的原两棵二叉（根）树，并将新构成二叉树添加到（根）树，并将新构成二叉树添加到HT中；中；Step 4.重复重复Step 2和和Step 2至至HT只剩下一棵二叉树，此即是所只剩下一棵二叉树，此即是所求求Huffman树。树。605.5.2 Huffman树构建思想树构建思想2构造具有四个分别带有权值构造具有四个分别带有权值1、3、5、7的的Huffman树如下图所示：树如下图所示：61练习：练习：已知有已知有6个叶子，值分别为个叶子，值分别为A、B、C、D、E、F，它们的权值分别为，它们的权值分别为4，9，1，3，2，1，试构造哈夫，试构造哈夫曼树（左权曼树（左权右权）。右权）。625.5.3基于顺序存储基于顺序存储Huffman树构造树构造1、Huffman树结点结构树结点结构问题：若哈夫曼树有问题：若哈夫曼树有n0个叶子结点，则所有结点个叶子结点，则所有结点 个。个。632n0-1解：因为树中无度为解：因为树中无度为1的结点，的结点，由二叉树的性质由二叉树的性质3知：知：n0=n2+1 所以：所以：n=n0+n2=n0+n0-1 =2n0-1u由于最终结果中结点个数已经确定，因此可采用顺序结由于最终结果中结点个数已经确定，因此可采用顺序结构存储存放所建构存储存放所建Huffman树树5.5.3基于顺序存储基于顺序存储Huffman树构造树构造1、Huffman树结点结构树结点结构2问题：结点结构如何构造？问题：结点结构如何构造？6400 struct node01 02 int weight;03 int parent,lch,rch;04 ;05 struct node HtreeMAX;5.5.3基于顺序存储基于顺序存储Huffman树构造树构造22、Huffman树构造算法树构造算法问题：算法如何构造问题：算法如何构造Huffman树？树？65原理：原理：找两找两无双亲无双亲且且权值最小权值最小结点合并，生成新结点，填写结点合并，生成新结点，填写相关信息（相关信息（两结点双亲，新结点权值，新结点左、右孩子两结点双亲，新结点权值，新结点左、右孩子）。算法算法5-13 基于顺序存储基于顺序存储Huffman树构造算法树构造算法 00 creat_huff(struct node Htree)01 02 int i,j,min1,min11,min2,min22;03 printf(nInput the count of leaves(10):);04 scanf(%d,&n);/*读取叶子结点个数读取叶子结点个数n*/05 for(i=0;i2*n-1;i+)/*数组数组Htree初始化初始化*/06 07 Htreei.parent=-1;08 Htreei.lch=-1;09 Htreei.rch=-1;10 11 printf(nInput the leavess weight:);12 for(i=0;in;i+)/*读取各个叶子的权值并赋值到读取各个叶子的权值并赋值到Htree数组数组*/13 scanf(%d,&Htreei.weight);66算法算法5-13 基于顺序存储基于顺序存储Huffman树构造算法树构造算法2 14 for(i=n;i2*n-1;i+)/*控制控制n-1次二叉树的合并次二叉树的合并*/15 16 min2=min1=MAX;/*min1、min2记录当前最小、次小权值记录当前最小、次小权值*/17 min11=min22=0;/*min11、min22记录当前最小、次小权值结记录当前最小、次小权值结点位置点位置*/18 for(j=0;ji;j+)/*在在j的范围内，找最小、次小结点的范围内，找最小、次小结点*/19 20 if(Htreej.parent=-1)21 if(Htreej.weightmin1)/*如当前权值比最小结点还小如当前权值比最小结点还小*/22 23 min22=min11;24 min2=min1;/*最小结点信息赋给次小最小结点信息赋给次小*/25 min11=j;26 min1=Htreej.weight;/*当前权值信息赋给最小当前权值信息赋给最小*/27 28 else67算法算法5-13 基于顺序存储基于顺序存储Huffman树构造算法树构造算法3 29 if(Htreej.weightmin2)/*如当前权值比次小结点小如当前权值比次小结点小*/30 31 min22=j;32 min2=Htreej.weight;/*当前权值信息赋给次小当前权值信息赋给次小*/33 34 35 Htreemin11.parent=i;/*设置最小权值结点的设置最小权值结点的parent域域*/36 Htreemin22.parent=i;/*设置次小权值结点的设置次小权值结点的parent域域*/37 Htreei.weight=Htreemin11.weight+Htreemin22.weight;/*设置新结点的权值域设置新结点的权值域*/38 Htreei.lch=min11;/*设置新结点的设置新结点的lch域为最小结点域为最小结点*/39 Htreei.rch=min22;/*设置新结点的设置新结点的rch域为次小结点域为次小结点*/40 41 Htree2*n-2.parent=-1;/*最后一个结点为根结点，最后一个结点为根结点，parent域为域为-1*/42 ;685.5.3基于顺序存储基于顺序存储Huffman树构造树构造33、Huffman树算法分析树算法分析69设有叶结点相应权值分别为设有叶结点相应权值分别为1，3，5，7。按照算法构建。按照算法构建Huffman树树过程如过程如下下图所示图所示：5.5.3基于顺序存储基于顺序存储Huffman树构造树构造33、Huffman树算法分析树算法分析70设有设有叶结点相应权值分别为叶结点相应权值分别为1，3，5，7。按照算法构建按照算法构建Huffman树过树过程如程如下下图所示图所示（续）：（续）：5.5.4 Huffman编码编码1、Huffman编码概念编码概念基于具体基于具体Huffman树的不等长编码就称为树的不等长编码就称为Huffman编码编码。首先得到需要编码的字符首先得到需要编码的字符c1、c2、cn在相应数据信息中出现的在相应数据信息中出现的频率为频率为p1、p2、pn；再以；再以c1、c2、cn作为叶结点，作为叶结点，p1、p2、pn作为相应权值，按照作为相应权值，按照Huffman算法构造一棵算法构造一棵Huffman树。树。其次，由构造的其次，由构造的Huffman树的根结点开始，在每个左分支上标注树的根结点开始，在每个左分支上标注0，右分支上标注右分支上标注1。这样，从根结点到每个叶结点的路径上由。这样，从根结点到每个叶结点的路径上由0、1组成组成的序列，就是该结点对应字符的编码。的序列，就是该结点对应字符的编码。715.5.4 Huffman编码编码1、Huffman编码概念编码概念2编码编码步骤步骤1：先建先建Huffman树树725.5.4 Huffman编码编码1、Huffman编码概念编码概念2编码编码步骤步骤1：先建先建Huffman树树（续）（续）735.5.4 Huffman编码编码1、Huffman编码概念编码概念2编码编码步骤步骤2：再编码再编码745.5.4 Huffman编码编码22、Huffman编码算法编码算法问题：如何编码？问题：如何编码？原理：原理：从叶子结点到根结点顺着路径分支为其编码。从叶子结点到根结点顺着路径分支为其编码。75算法算法5-14 Huffman编码算法编码算法00 code_huff(struct node Htree)01 02 int i,j,k,pr,start;03 for(i=0;in;i+)04 05 j=n-2;06 k=i;/*k记录当前编码结点，初始为叶结点位置记录当前编码结点，初始为叶结点位置*/07 while(Htreek.parent!=-1)08 09 pr=Htreek.parent;/*记录记录k的父结点的父结点*/10 if(k=Htreepr.lch)11 codeij=0;/*左分支编码为左分支编码为0*/12 else13 codeij=1;/*右分支编码为右分支编码为1*/14 j=j-1;15 k=pr;/*进到路径的上一个结点，直至根结点进到路径的上一个结点，直至根结点*/16 17 codein-1=j+1;/*存放编码的起始位置是存放编码的起始位置是j+1*/18 76算法算法5-14 Huffman编码算法编码算法219 printf(n The code are:n);20 for(i=0;in;i+)21 22 start=codein-1;/*取出编码的起始位置取出编码的起始位置*/23 for(j=start;jn-1;j+)/*逐个输出编码逐个输出编码*/24 printf(%-3d,codeij);25 printf(n);26 27 775.5.4 Huffman编码编码33、Huffman编码算法分析编码算法分析Huffman编码过程如编码过程如下下图所示图所示：78练习：练习：设有设有7个带权结点个带权结点A，B，C，D，E，F，G，其权值分别为，其权值分别为3，7，8，2，5，8，4，试以这，试以这7带权结点为叶子结点，构造一带权结点为叶子结点，构造一棵哈夫曼树（左权棵哈夫曼树（左权右权）。右权）。79练习：练习：在一份报文中有五种字符，在一份报文中有五种字符，A，B，C，D，E，它们在报文，它们在报文中出现的频率比例为中出现的频率比例为4，7，5，2，9，试通过构造最优二叉树，试通过构造最优二叉树来确定每种字符的哈夫曼编码（左权来确定每种字符的哈夫曼编码（左权右权）。右权）。80上上 机：机：81理解建立理解建立huffman树的过程及编码过程。树的过程及编码过程。v1.结点定义（需要至少结点定义（需要至少4个域：个域：weight，parent，lch，rch）v2.定义数组定义数组v3.输入叶子的个数输入叶子的个数nv4.数组初始化数组初始化v5.输入叶子的权值输入叶子的权值v6.循环循环n1次做：次做：v （1）找两个最小权值及其下标）找两个最小权值及其下标v （2）合并，填写相关信息）合并，填写相关信息v7.输出数组输出数组v8.编码并输出编码并输出本章小结本章小结本章基本内容本章基本内容