树的定义和基本术语课件.ppt

6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.5 Huffman树及其应用,第六章 树与二叉树,树形结构是一种非线性结构，应用十分广泛。如：行政机构、家谱、磁盘目录等,磁盘目录,根-根结点分枝-分枝结点叶-叶结点,6.1 树（Tree）的定义和基本术语,树的定义：树是n（n=0）结点的有限集，在任意非空树中：(1)有且仅有一个特定的结点称为根（Root）的结点.(2)当n1时，其余的结点可分为m个互不相交的子 集 T1,T2,Tm,每个子集又都是树，称为根 的子树（Sub tree）.,6.1 树（Tree）的定义和基本术语,树的定义具有递归性,Tree=D=Book,C1,C2,C3,S1.1,S1.2,S2.1,S2.2,S2.3,S2.1.1,S2.1.2 R=,例6.1,6.1 树（Tree）的定义和基本术语,术语主要来源于家谱和树：双亲、父母（Parent）；子女、孩子（Child）：若a,b R，则称a是b的双亲，b是a 的子女(孩子).叶结点（Leaf）：度为0的结点；分枝结点（Branch node）：度大于0的结点；结点度（Degree）：该结点所拥有的子女数；树的度：树内各结点度的最大值；结点的层次（Level）：设根结点的层次为1，其它任一结点 所在的层次是其双亲的层次加1；,6.1 树（Tree）的定义和基本术语,树是一种层次结构（hiberarchy）,1,2,3,4,5,6.1 树（Tree）的定义和基本术语,堂兄弟（Cousin）：双亲在同一层的结点之间互称堂兄弟；路径（Path）：如果有结点序列n1,n2,n3,nk，并且前1个结 点是后1个结点的双亲；它的长度是k-1;祖先、后代（ancestor）:一个结点是它所有子树中的结点 的祖先，这些结点是它的后代(子孙);有序树（Ordered tree）：每个结点的子女由左到右是有次 序的称有序树；否则是无序树；,6.1 树（Tree）的定义和基本术语,深度（Depth）：树中结点的最大层次；或称为高；兄弟（Sibling)：具有同一双亲的结点互称兄弟；,结点A的度：3结点B的度：2结点M的度：0,叶子：K，L，F，G，M，I，J,结点A的孩子：B，C，D结点B的孩子：E，F,结点I的双亲：D结点L的双亲：E,结点B，C，D为兄弟结点K，L为兄弟,树的度：3,结点A的层次：1结点M的层次：4,树的深度：4,结点F，G为堂兄弟结点A是结点F，G的祖先,T1,T2,T3,T4,T5,T6,6.1 树（Tree）的定义和基本术语,森林（Forest）：是m(m 0)棵互不相交的树的集合,(例如删除树根后的子树构成一个森林),任何一棵非空树是一个二元组 Tree=（root，F）其中：root 被称为根结点，F 被称为子树森林,抽象数据类型树的定义：,6.1 树（Tree）的定义和基本术语,ADT Tree,数据对象D：D是具有相同特性的数据元素的集合。,数据关系R：若D为空集，则称为空树；,若D仅含一个数据元素，则R为空集，否则R=H，H是如下二元关系：,(1)在D中存在唯一的称为根的数据元素root，它在关系H下 无前驱；,(2)若D-root，则存在D-root的一个划分D1，D2，Dm，(m0)，对任意jk(1j,km)有DjDk=,且对任意的i(1im)，唯一存在数据元素xiDi，有H；,(3)对应于D-root的划分，H，有唯一的一个划分H1,H2，Hm(m0)，对任意jk(1j，km)有HjHk=,且对任意i(1im),Hi是Di上的二元 关系,(Di,Hi)是一棵符合本定义的树,称为根root的子树.,基本操作:InitTree(&T)操作结果：构造空树T。DestroyTree(&T)初始条件：树T存在。操作结果，销毁树T。,CreateTree(&T，definition)初始条件：definition给出树T的定义。操作结果：按definition构造树T。ClearTree(&T)初始条件；树T存在。操作结果：将树T清为空树。TreeEmpty(T)初始条件：树T存在。操作结果：若T为空树，则返回TRUE，否则FALSE。TreeDepth(T)初始条件：树T存在。操作结果；返回T的深度。,基本操作:,Root(T)初始条件：树T存在。操作结果：返回T的根。Value(T，cur_e)初始条件：树T存在，cur_e是T中某个结点。操作结果：返回cur_e的值。Assign(T，cur_e，value)初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e 赋值为value。Parent(T，cur_e)；初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非根结点，则返回它的双亲，否则返回“空”。,基本操作:,LeftChild(T，cur_e)；初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非叶子结点，则返回它的 最左孩子，否则返回“空”。RightSibling(T，cur_e)；初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回“空”。,基本操作:,InsertChild(&T，&P，i，c)；初始条件：树T存在,p指向T中某个结点，i指结点的度,非空树c与T不相交。操作结果：插入c为T中p所指结点的第i棵子树。DeleteChild(&T，&p，i)；初始条件：树T存在，p指向T中某个结点，i指结点的度,操作结果：删除T中p所指结点的第i棵子树。TraverseTree(T)；初始条件；树T存在。操作结果：按某种次序对T的每个结点进行遍历。ADT Tree,基本操作:,树的表示方法：1.树形表示：,6.1 树（Tree）的定义和基本术语,2.括号表示(广义表表示)：,3.凹入表表示(目录表示法)：,6.1 树（Tree）的定义和基本术语,4.文氏图表示(集合表示):,6.1 树（Tree）的定义和基本术语,二叉树是另一种树形结构。6.2.1 二叉树的定义二叉树：是n（n=0）结点的有限集，在任意非空树中：(1)有且仅有一个特定的称为根（Root）的结点;(2)当n1时，其余的结点最多分为2个互不相交的子集 T1,T2,每个又都是二叉树，分别称为根的左子树和右子树.,6.2 二叉树（Binary Tree）,例,6.2.1 二叉树的定义,二叉树,注意：二叉树不是树，它是另外单独定义的一种树形结构，并非一般树的特例。它的子树有顺序规定，分为左子树和右子树。不能随意颠倒。,二叉树的5种基本形态：,具有3个结点的二叉树可能有几种不同形态？,抽象数据类型二叉树的定义：ADT BinaryTree数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=，则R=，称Binary为空二叉树；若D，则R=H，H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-root，则存在D-root的一个划分Dl，Dr，且DlDr=；(3)若Dl,则Dl中存在唯一的元素x1,H,且存在Dl上的关系HlH,若Dr,则Dr中存在唯一的元素xr,H,且存在Dr上的关系HrH;H=,Hl,Hr(4)(Dl,Hl)是一颗符合本定义的二叉树，称为根的左子树(Dr,Hr)是一颗符合本定义的二叉树，称为根的右子树,6.2.1 二叉树的定义,基本操作:InitBiTree(初始条件：definition给出二叉树T的定义。操作结果：按definition构造二叉树T。ClearBiTree(&T)；初始条件：二叉树T存在。操作结果：将二叉树T清为空树。,BiTreeEmpty(T)；初始条件：二叉树T存在。操作结果：若T为空二叉树,则返回TRUE,否则FALSE.BiTreeDepth(T)；初始条件：二叉树T存在。操作结果：返回T的深度。Root(T)；初始条件:二叉树T存在。操作结果：返回T的根。Value(T，e)初始条件：二叉树T存在，e是T中某个结点。操作结果；返回e的值。,基本操作:,Assign(T，&e，value)；初始条件；二叉树T存在，e是T中某个结点。操作结果：结点e赋值为value。Parent(T，e)；初始条件：二叉树T存在，e是T中某个结点。操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”。LeftChild(T，e)；初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左孩子，若e无左孩子，则返回“空”。RightChild(T，e)；初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右孩子,若e无右孩子，则返回“空”。,基本操作:,LeftSibling(T，e)；初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则 返回“空”。,Rightsibling(T，e)；初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”。,基本操作:,InsertChild(T，p，LR，c)；初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。,操作结果：根据LR为0或1，插入c为T中p所指结点的左或 右子树。P所指结点的原有左或右子树则成为c 的右子树。,基本操作:,DeleteChild(T，p，LR)；初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。,PreOrderTraverse(T)；初始条件：二叉树T存在。操作结果：先序遍历T中对每个结点一次且仅一次。,基本操作:,InOrderTraverse(T)；初始条件：二叉树T存在。操作结果：中序遍历T中每个结点一次且仅一次。,PostOrderTraverse(T)；初始条件：二叉树T存在。操作结果：后序遍历T中每个结点一次且仅一次。,基本操作:,LevelOrderTraverse(T)；初始条件：二叉树T存在。操作结果：层序遍历T中每个结点一次且仅一次.ADT BinaryTree,性质1:在二叉树的第i层最多有2i-1 个结点(i=1).,用归纳法证明：归纳基：归纳假设：归纳证明：,i=1 层时，只有一个根结点，2i-1=20=1；,i=k时命题成立;,i=k+1时,二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2k-1 2=2(k+1)-1=2i-1。,6.2.2 二叉树的性质,性质2:深度为k的二叉树最多有2k 1个结点（k=1).,证明：,基于性质1，深度为 k 的二叉树上的结点数最多为 20+21+2k-1=2k-1,6.2.2 二叉树的性质,性质3:任一二叉树,若叶结点数是n0,度为2的结点数 是 n2,则 n0=n2+1,证明：,设 二叉树上结点总数 n=n0+n1+n2又 二叉树上分支总数 b=n1+2n2 而 b=n-1=n0+n1+n2-1由此，n0=n2+1,6.2.2 二叉树的性质,满二叉树(Full Binary Tree):每一层的结点数都达到了最 大的二叉树.编号的满二叉树:从根开始,由上到下,从左到右地对每个结点 进行编号.也就是说:根的编号是1,一个结点,若它是双亲 的左子女,则它的编号是它的双亲编号的2倍;若它是双亲 的右子女,则它的编号是双亲编号的2倍+1.,6.2.2 二叉树的性质,完全二叉树(Complete Binary Tree):深度为k的满二叉树,删去第k层上最右边的j(0 j2k-1)个结点,就得到一个深度为k的完全二叉树.编号的完全二叉树:与满二叉树编号相同,6.2.2 二叉树的性质,性质4:具有n个结点的完全二叉树,其深度为。,证明：,6.2.2 二叉树的性质,性质5：在编号的完全二叉树中，对任一结点i（1i n）有：（1）若i=1,是根;若i1，则它的双亲是（2）若2i n，则结点i的左子女是2i;否则无左子女；（3）若2i+1 n，则结点i的右子女是2i;否则无右子女；,1,2,3,4,6,5,i,i+1,2i,2i+1,6.2.2 二叉树的性质,2i+2,6.2.3 二叉树的存储结构一、二叉树的顺序存储完全二叉树的顺序存储：,A B C E H F,0 1 2 3 4 5 6,ST,根据性质5知：STi 的双亲是ST,左子女是ST2*i，右子女是ST2*i+1,一、二叉树的顺序存储,A B C E F H,0 1 2 3 4 5 6 7 8 9,ST,根据性质5知：STi 的双亲是ST,左子女是ST2*i,右子女是ST2*i+1.,6.2.3 二叉树的存储结构,这样太浪费空间,适合完全二叉树,二、二叉树的链式存储结构(二叉链表),typedef struct BiTNode ElemType data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;,6.2.3 二叉树的存储结构,二、二叉树的链式存储结构(三叉链表),lchild data rchild parent,Left child,Right child,Parent,typedef struct BiTNodeElemType data;struct BiTNode*lchild,*rchild,*parent;BiTNode,*BiTree;,6.2.3 二叉树的存储结构,BiTNode:,二、二叉树的链式存储结构(三叉链表),6.2.3 二叉树的存储结构,6.3 遍历二叉树和线索二叉树,按照某种搜索路径访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。,一、遍历,“访问”的含义特别很广，如：输出结点的信息等。,因二叉树是非线性结构，每个结点可能有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。,前(先)序 遍历,中序遍历,后序遍历,N,L,R,1,2,3,二、遍历方法,NLRLNRLRN,NRLRNLRLN,6.3 遍历二叉树和线索二叉树,算法思想6.1前序遍历：若BT非空，则：1.访问根结点；2.前序遍历左子树；3.前序遍历右子树;,算法思想6.2中序遍历：若BT非空，则：1.中序遍历左子树；2.访问根结点；3.中序遍历右子树；,算法思想6.3后序遍历：若BT非空，则：1.后序遍历左子树；2.后序遍历右子树；3.访问结点；,6.3 遍历二叉树和线索二叉树,A,B,C,E,F,H,G,例6,A,B,C,E,F,H,G,前序遍历(NLR)序列：,A,B,E,H,G,C,F,中序遍历(LNR)序列：,A,B,C,E,F,H,G,E,B,G,H,A,F,C,后序遍历(LRN)序列：,A,B,C,E,F,H,G,E,G,H,B,F,C,A,算法思想6.1前序遍历：若BT非空，则：1.访问根结点；2.前序遍历左子树；3.前序遍历右子树;,6.3 遍历二叉树和线索二叉树,前序遍历二叉树的递归算法算法 6.1Void PreOrderTraverse(BiTree BT)if(BT)visit(BT);PreOrderTraverse(BT-lchild);PreOrderTraverse(BT-rchild);/end of PreOrderTraverse,请同学们自己写出InOrderTraverse(BT)和PostOrderTraverse(BT),建立二叉树建立二叉树的方法很多，我们给出以前序遍历序列建立二叉树的方法，但该序列是扩充二叉树的前序遍历序列。是扩充的叶结点，它代表空指针。,该扩充二叉树的前序遍历序列是：ABD*EF*C*该算法是一递归算法，递归三要素：1.递归出口：当遇到*时，是空。2.建立根。3.建立左子树和右子树。,建立二叉树的算法Status CreateBiTree(BiTree 构造右于树return OK；CreateBiTree,A,B,C,D,A,BT,B,C,D,遍历二叉树的非递归算法：我们先观察一下三种遍历行走的路线,*,*,*,*,*,*,*,*,*,前序遍历NLR,#,#,#,#,#,#,#,#,#,中序遍历LNR,&,&,&,&,&,&,&,&,&,后序遍历LRN,三种遍历的访问位置对比：,三种遍历的路线完全一样，只是访问时间不同；,前序：第一次经过*时访问,中序：第二次经过#时访问,后序：第三次经过&时访问,遍历线路的核心规则是：先左后右；我们用一个栈stack记录走过的位置，以便返回；stack 中数据元素的类型：*BiTNode(或BiTree)函数：BiTree P;push(S,p);pop(S,p);Boolean StackEmpty(S);下面给出基于逻辑结构的算法描述,非递归中序遍历二叉树的算法思想 建立栈 stack；P指向根；当p不空 且 stack 不空时反复做：若 p不空,p 入 栈;p指向左子女；否则：出栈顶元素到p中；访问p；p指向右子女；4.结束,如何进行前序遍历？,Void lnorderTraverse(BiTree BT)采用二叉链表存储结构，中序遍历二叉树T的非递归算法.InitStack(S)；p=BT；while(p|!StackEmpty(S)if(p)push(S，p)；p=p-lchild；/根指针进栈，遍历左子树 else 根指针退栈，访问根结点，遍历右子树 pop(S，p)；visit(p);p=p-rchild；/elseInOrderTraverse,非递归中序遍历BT的算法:,例,例,例,例,例,例,例,例,例,例,例,例,例,例,例,非递归后序遍历二叉树的算法思想建立栈 stack；P指向根；当p不空 且 stack 不空时反复做：若 p不空：(p,L)入 栈;p指向左子女；否则：出栈顶元到p和tag中；若tag=R,则访问p；p置空；否则（p,R）入栈；并让 p指向右子女；4.结束,后序遍历时，访问一个结点的时间是：第3次经过时或第2次反回时或从右边返回时；如何区分从左还是右返回的呢？P入栈时带一标记:向左走时带L向左走时带R,非递归后序遍历BT的算法,非递归的后序遍历BT算法:（基于二叉链表存储结构）void PostOrderTraverse(BiTree BT)InitStack(S)；/建立栈 p=BT;/指向根while(p|!StackEmpty(S)if(p)push(p,L)；/p带L入 栈p=p-lchild;/p指向左子女else pop(p,e);/出栈顶元到e中p=e.p;tag=e.tag;if(tag=R)visite(p-data);p=NULL;/访问pelse push(p,R);p=p-rchild;/p指向右子女/else/end of while/end of postOrderTraverse(bt),例,B,E,A,C,Start,(A,L)入栈(A,L)(B,L)入栈(A,L)(B.L)(B.L)退栈，(A,L)(B,R)入栈(A,L)(B,R)(E,L)入栈(A,L)(B,R)(E,L)(E,L)退栈(A,L)(B,R)(E,R)入栈(A,L)(B,R)(E,P)(E,R)退栈(A,L)(B,R)访问E(B,R)退栈(A,L)访问B(A,L)退栈(A,R)入栈(A,R)(C,L)入栈(A,R)(C,L)(C,L)退栈(A,R)(C,R)入栈(A,R)(C,R)(C,R)退栈(A,R)访问C(A,R)退栈 访问A,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,课堂练习前序遍历序列：EDACBGFE中序遍历序列：ADCBEFHG试画出满足以上序列的二叉树,课堂练习中序遍历序列：ADCBHFEG后序遍历序列：ABCDEFGH试画出满足以上序列的二叉树,二、线索二叉树(Threaded Binary Tree)目的：利用二叉树的空指针保存遍历序列的前驱和后继。n个结点的二叉树,有2n个指针,只用了n-1个,有n+1个是空指。用空的左指针指向某一遍历序列的前驱.用空的右指针指向某一遍历序列的后继.这两种指针称为线索(Thread)。为了区分线索与真实指针，给结点增加两个域Ltag和Rtag,Ltag=0:lchild 指向结点的左子女；Ltag=1:lchild 指向某一遍历序列前驱；Rtag=0:rchild 指向结点的右子女；Rtag=1:rchild 指向某一遍历序列后继；,二、线索二叉树(Threaded Binary Tree),Typedef enumLink,Thread PointerTag;Typedef struct BiThrNode ElemType data;struct BiThrNode*lchild,*rchild;PointerTag Ltag,Rtag;BiThrNode,*BiThrTree;,二、线索二叉树(Threaded Binary Tree),加了线索的二叉树是线索二叉树；给二叉树加线索的过程是线索化（穿线）；按前序遍历序列穿线的二叉树是前序线索二叉树；按中序遍历序列穿线的二叉树是中序线索二叉树；按后序遍历序列穿线的二叉树是后序线索二叉树；中序线索二叉树简称线索二叉树；,二、线索二叉树(Threaded Binary Tree),0,0,0,0,1,1,1,1,1,1,二、线索二叉树(Threaded Binary Tree),0,0,0,0,1,1,1,1,1,1,二、线索二叉树(Threaded Binary Tree),0,0,0,0,1,1,1,1,1,1,二、线索二叉树(Threaded Binary Tree),D,B,F,E,A,C,NULL,NULL,中序线索二叉树,二、线索二叉树(Threaded Binary Tree),Void lnorderTraverse(BiTree BT)采用二叉链表存储结构，中序遍历二叉树T的非递归算法.InitStack(S)；p=BT；while(p|!StackEmpty(S)if(p)push(S，p)；p=p-lchild；/根指针进栈，遍历左子树 else 根指针退栈，访问根结点，遍历右子树 pop(S，p)；visit(p);p=p-rchild；/elseInOrderTraverse,非递归中序遍历二叉树的算法(回忆),对以二叉链表存储的二叉树进行中序线索化(非递归的)void InOrderThreading(BiThrTree BT)InitStack(S);/建立栈 p=BT;pre=NULL;/p指向根,pre是p的前驱结点while(p|!StackEmpty(S)if(p)push(S,p);/p入栈p=p-lchild;/p指向左子女else pop(S,p);/出栈顶元到p中if(!p-lchild)p-lchild=pre;p.ltag=true;if(pre/p指向右子女/end of while/end of InOrderThreading(BT),visit(p),(中序)线索二叉树的线索给我们提供了足够的信息,对其进行遍历时，既不需要递归(使用了系统栈),也不需要栈.,对(中序)线索二叉树进行非递归遍历且不需要设栈时需要主要解决的两个问题:,找到某一次序下的第一个结点p;,2)找出给定结点p在某一次序中的后继结点;,关键问题1沿着根的左链走,直到无左子女的结点p，即中序序列中的第一个结点;p=BT;while(!p.ltag)p=p-lchild;,关键问题2，有如下两种情况：P无右子女：则p-rchild是p的后继；P有右子女：则p的右子树中最左的结点就是p的后继，方法同关键问题1。if(p.rtag)p=p-rchild;/P无右子女else p=p-rchild;/P有右子女 while(!p.ltag)p=p-lchild;,中序遍历(中序)线索二叉树时如何解决这两个问题:,void InOrderTraverse(BiThrTree BT)p=BT;while(!p)while(!p-ltag)p=p-lchild;/沿左链走直到无左子女的结点 visit(p);while(p-rtag/inOrderTraverse,中序遍历线索二叉树的算法,同理，我们可以前序非递归遍历中序线索二叉树，同样不需要递归（使用了系统栈）也不需要栈.,关键问题1根就是第一个结点.,关键问题2，有如下3种情况：P有左子女：则p左子女是p的后继；否则P有右子女：则p的右子女是p的后继;否则P是叶：沿着p的线索走，直到空或一个有右子女的结点r为止，若空，则p无后继，否则r的右子女是p 的 后继。,前序遍历线索二叉树的算法void PreOrderTraverse(BiThrTree BT)p=BT;while(p)visit(p);if(!p-ltag)p=p-lchild;/P有左子女 else if(!p-rtag)p=p-rchild;/P有右子女 else r=p-rchild;/p是叶 while(r/PreOrderTraverse,1、双亲表示法是一种顺序存储方法，即用数组存储。每个结点有两个域:data是结点的数据元素；parent是指出该结点的双亲结点在数组中的下标；,一、树的存储结构,6.4 树的存储结构,PTNode:,树的双亲表示法说明：#define MAX-TREE-SIZE 100typedef struct PTNodeElementType data;int parent;/该结点的双亲的下标 PTNode;typedef struct PTNode nodesMAX-TREE-SIZE;int n;/树的结点数 PTree;,一、树的存储结构,例 用双亲法存储树,一、树的存储结构,同样的道理可以存储森林,例 用双亲法存储森林,A-1B-1C 0D-1E 1F 2G 3H 6I 6J 6,01234567891011,9,一、树的存储结构,2、孩子（子女）表示法,结点结构,对不同的结点,k(度)是不同的,因此应取最大数,即树的度;这种方法不可取;所以最自然的方法是为每个结点建立一个单链表，该单链表存储它的所有孩子，所有结点组成一个数组，称表头数组。表头数组中每一项称孩子链表头指针CTBox:(头结点)单链表中每一项称孩子结点(也称表结点)：CTNode:,一、树的存储结构,typedef struct CTNode/孩子结点（表结点）int child；struct CTNode*next；*ChildPtr；tyPedef struct/头结点 TElemType data；ChildPtr firstchild;CTBox；typedef struct/孩子链表头指针CTBox nodesMAX_TREE_SIZE；int n，r；/结点数和根的位置；CTree；,树的孩子链表存储表示说明：,如何找双亲结点,2、孩子表示法(子女表示法),带双亲的孩子链表存储表示:,typedef struct CTNode/孩子结点（表结点）int child；struct CTNode*next；*ChildPtr；typedef struct/头结点 TElemType data；int parent;ChildPtr firstchild;CTBox；typedef struct/孩子链表头指针CTBox nodesMAX_TREE_SIZE；int n，r；/结点数和根的位置；CTree；,带双亲的孩子链表,2、孩子表示法(子女表示法),3、孩子兄弟表示法(也称二叉树表示法 或二叉链表表示法),结点结构（CSNode）:,data firstchild nextsibling,一、树的存储结构,指向该结点的下一个兄弟,指向该结点的第一个孩子,typedef struct CSNode TElemType data；struct CSNode*firstchild，*nextsihling；CSNode，*CSTree；,树的孩子链表存储表示,例 用孩子兄弟法存储树,一、树的存储结构,树的遍历:按根的次序区分有两种遍历次序(1)先根遍历:若树非空，则 访问根结点;从左到右先根遍历根的每棵子树;,二、树与森林的遍历,例 先根遍历树,先根遍历序列:,A B E C F D G H I J,二、树与森林的遍历,（2）后根遍历:若树非空，则 从左到右后根次序遍历根的每棵子树;访问根结点;,二、树与森林的遍历,例 后根遍历树,后根遍历序列:E B F C H I J G D A,二、树与森林的遍历,森林的遍历:森林的遍历是基于树的遍历完成的,对应有两种遍历次序:(1)先序遍历:访问第一棵树的根;先序遍历第一棵树中的根结点的子树森林；先序遍历其余的树所构成的森林；(2)中序遍历:中序遍历第一棵树的子树；访问第一棵树的根;中序遍历其余的树所构成的森林；,二、树与森林的遍历,先序遍历森林,先序遍历序列：,二、树与森林的遍历,先序遍历:访问第一棵树的根;先序遍历第一棵树中的根 结点的子树森林；先序遍历其余的树所构成 的森林；,中序遍历序列：BCDAFEHJIG,中序遍历森林,二、树与森林的遍历,中序遍历:中序遍历第一棵树的子树；访问第一棵树的根;中序遍历其余的树所构成的 森林；,三、森林与二叉树的转换,在森林与二叉树 之间存在一一对应的关系。1).森林=二叉树的转换自然转换法：凡是兄弟用线连起来，然后去掉双亲到子女的连线，但保留双亲到其第一子女的连线，最后转45。,例：森林到二叉树的转换,A,B,C,D,E,F,G,H,I,J,前序序列：ABCDEFGHIJ,前序序列：ABCDEFGHIJ,=,三、森林与二叉树的转换,中序序列：BCDAFEHJIG,中序序列：BCDAFEHJIG,=,2)二叉树=森林的转换,自然转换法：若某结点是其双亲的左孩子，则该结点的右孩子、右孩子的右孩子,都与该结点的双亲连接起来,最后去掉所有双亲到右孩子的连线.,三、森林与二叉树的转换,A,B,C,D,E,F,G,H,I,J,问题提出:在数据通信中，用二进制给每个字符编码,如何使电文总长最短且不产生二义性?,根据字符出现频率，利用Huffman树可以构造一种不等长的二进制编码，并且构造所得的Huffman编码是一种最优前缀编码，即使所传电文的总长度最短。任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。,6.6 Huffman树及其应用,6.6 Huffman树及其应用,最优二叉树（Huffman）如何构造最优二叉树如何求哈夫曼编码,一、哈夫曼树(最优树)的定义,结点的路径长度：从根结点到该结点的路径上分支的 数目。,树的路径长度：树中每个结点的路径长度之和。,(结点)带权路径长度:结点的路径长度*结点的权=li*wi,树的带权路径长度：树中所有叶结点的带权路径长度之和WPL(T)=,设K=k1,k2,kn,它们的权W=w1,w2,wn,构造以k1,k2,kn为叶结点的二叉树，使得WPL=为最小,则称之为“最优二叉树”。,一、哈夫曼树(最优树)的定义,例 W=1,2,4,6,可构造出如下的二叉树：,1,2,4,6,1,2,4,6,6,4,1,2,WPL=(1+2+4+6)*2=26,WPL=1+2*2+(4+6)*3=35,WPL=6+4*2+(1+2)*3=23,(1),(2),(3),根据定义求Huffman树的方法是：对给定的n个叶子结点（外部结点），构造出全部二叉树并求出其WPL，然后找出WPL最小的树。当n较大时，显然这种方法是不可取的。,二、构造huffman树算法思想：1.根据权值w1,w2,wn构造n个二叉树F=T1,T2,Tn，其中 Ti中是只含权值为wi 的结点。2.从F中选两个权值最小的二叉树Ti和Tj，构造一个 根结点R,R的权wR为wi+wj。3.从F中删除Ti和Tj，加入新的树R到F中。4.重复2，3 直到F中只有一棵树(或执行n-1次)为止。,问题:如何证明所构造的二叉树是最优树?,例:已知权值 W=5,6,3,9,7,5,6,3,7,9,9,用n个叶结点构造出的最优二叉树共有几个结点？,构造最优树时共执行n-1次循环，每次增加一个新 结点，共增加了n-1个结点，所以结点总数一定 是n+n-1=2n-1,因为n0=n2+1,所以n2=n0-1,又由于在最优二叉树中 没有度为1的结点,所以在最优二叉树中总的结点数为 n+n-1=2n-1,Huffman 算法的实现：,Huffman编码：设字符集为 c1,c2,cn,看作叶结点出现概率为 w1,w2,wn,叶结点的权（1）构造Huffman树（2）左分支标0，右分支标1（3）根到叶结点ci的路径上的二进制编码就是ci的编码编码长度为 l1,l2,ln 是叶结点的路径长度,则树的带权路径长度WPL是：,根到任何ci的路径都不会经过任何其它ck,因此Huffman编码是无前缀编码，即任何一个编码都不会是另一个编码的前缀。例：字符集a,b,c,d,e,f,g,h出现概率分别是 0.14,0.08,0.11,0.23,0.29,0.05,0.03,0.07,Huffman编码：,构造Huffman 树：,a,b,c,h,d,e,f,g,100,42,58,19,29,15,8,23,3,5,11,29,14,7,8,0,1,1,1,1,1,1,1,0,0,0,0,0,0,(2)编码：a:110b:1111c:011d:00e:10f:0101g:0100h:1110,(3)编码长度：WPL=2*0.23+4*0.03+4*0.05+3*0.11+2*0.29+3*0.14+4*0.08+4*0.07=2.71,0,0,0,0,0,0,1,1,1,1,1,1,1,Huffman 算法的实现：用数组存储Huffman 树，每个数组元素HTNode包括4个域:,1 2 3 n n+1 2n-1,权 w双亲 parent左子女 lchild右子女 rchild,叶子结点(外部结点),内部结点,/哈夫曼树和哈夫曼编码的存储表示typedef struct unsigned int weight；unsigned int parent，lchild，rchild；HTNode，*HuffmanTree；/动态分配数组存储哈夫曼树typedef char*HuffmanCode；/动态分配数组存储哈夫曼编码表,构造哈夫曼树的算法void HuffmanCoding(HuffmanTree HTi.rchild=s2；HTi.weight=HTs1.weight+HTs2.weight；,/从叶子到根逆向求每个字符的哈夫曼编码HC=(HuffmanCode)malloc(n十1)*sizeof(char*);/分配n个字符编码的头指针向量cd=(char*)malloc(n*sizeof(char)；/分配求编码的工作空间cdn-1=0;；/编码结束符。for(i=1;i=n；+i)/逐个字符求哈夫曼编码 start=n-1；/编码结束符位置 for(c=i，f=HTi.parent；f!=0；c=f，f=HTf.parent)/从叶子到根逆向求编码 if(HTf.lchild=c)cd-start=0；else cd-start=1；HCi=(char*)malloc(nstart)*sizeof(char)；/为第i个字符编码分配空间 strcpy(Hci，&cdstart)；/从cd复制编码(串)到Hc free(cd)；/释放工作空间/HuffanCoding,1、定义和性质,2、存储结构,3、遍历,4、线索化：线索树,先序遍历,中序遍历,本章小结,理解树形结构的基本概念和术语；深刻领会二叉树的定义和存储结构，熟悉二叉树的 遍历并熟练掌握遍历算法；理解二叉树线索化的实质，熟练掌握二叉树的线索 化过程以及遍历