数据结构 第6章 树和二叉树

1、第六章第六章 树和二叉树树和二叉树（一）教学目的： 掌握树和二叉树的定义及存储结构；二叉树的基本操作；树和二叉树的应用。（二）教学重点： 1、树的定义及相关术语。 2、二叉树的定义、存储结构和基本运算的实现。 3、二叉树的遍历，二叉树与树和森林的相互转换。 4、哈夫曼树及应用数组的定义及其存储（三）教学难点： 1、二叉树的定义、存储结构和基本运算的实现 2、哈夫曼树及应用。6.1树的概念和基本术语6.2二叉树 6.3遍历二叉树和线索二叉树6.4树与森林6.6哈夫曼树 基本内容：6.16.1树的概念和基本术语树的概念和基本术语一、树的定义一、树的定义树是由树是由 n (n n (n 0) 0)

2、个结点的有限集合。如果个结点的有限集合。如果 n = n = 0 0，称为空树；如果，称为空树；如果 n 0n 0，则有且仅有一个特定的称，则有且仅有一个特定的称之为根之为根(Root)(Root)的结点，它只有直接后继，但没有直接的结点，它只有直接后继，但没有直接前驱；前驱；当当n 1n 1，除根以外的其它结点划分为，除根以外的其它结点划分为 m (m 0) m (m 0) 个互不相交的有限集个互不相交的有限集 T T1 1, T, T2 2 , T , Tm m，其中每个集合，其中每个集合本身又是一棵树，并且称为根的子树本身又是一棵树，并且称为根的子树(SubTree(SubTree) )

3、ACGBDE FKLHMIJ例如例如A只有根结点的树只有根结点的树有有13个结点的树个结点的树其中：其中：A是根；其余结点分成三个互不相交的子集，是根；其余结点分成三个互不相交的子集，T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M,T1,T2,T3都是根都是根A的子树，且本身也是一棵树的子树，且本身也是一棵树二、树的表示1、树型表示法2、集合表示法3、括号表示法 （1（2（4，5），37）4、凹入表示法217543124537124537三、树的基本术语结点(node)表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)结点拥有的子树数叶子(leaf)

4、度为0的结点孩子(child)结点子树的根称为该结点的孩子双亲(parents)孩子结点的上层结点叫该结点的兄弟(sibling)同一双亲的孩子树的度一棵树中最大的结点度数结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层深度(depth)树中结点的最大层次数森林(forest)m(m0)棵互不相交的树的集合ABCDEFGHIJKLM结点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，

5、G为堂兄弟结点A是结点F，G的祖先五种形态五种形态： 一棵二叉树是结点的一个有限集合，该集合或者为空，一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。不相交的二叉树组成。二、特点：二、特点： 每个结点至多只有两棵子树（二叉树中不存在度大于每个结点至多只有两棵子树（二叉树中不存在度大于2 2的的结点）结点）LLRR性质性质1 在二叉树的第 i 层上至多有 2i 1个结点。(i 1) 证明用归纳法证明：当证明：当i=1时，只有根结点，时，只有根结点，2 i-1=2 0=1

6、。假设对所有假设对所有j，ij 1，命题成立，即第，命题成立，即第j层上至多有层上至多有2 j-1 个结点。个结点。由归纳假设第由归纳假设第i-1 层上至多有层上至多有 2i 2个结点。个结点。由于二叉树的每个结点的度至多为由于二叉树的每个结点的度至多为2，故在第，故在第i层上的最大结点数层上的最大结点数为第为第i-1层上的最大结点数的层上的最大结点数的2倍，即倍，即2* 2i 2= 2 i-1。1层2层4层3层height= 4ABDEFJKHLI性质性质2 深度为深度为 k 的二叉树至多有的二叉树至多有 2 k- -1个结点个结点(k 1)。证明：由性质证明：由性质1可见，深度为可见，深度

7、为k的二叉树的最大结点数的二叉树的最大结点数为为 kii11220 + 21 + + 2 k-1 = 2 k- -1kii1(层上的最大结点数）第性质性质3 3 ：对任何一棵二叉树：对任何一棵二叉树T, T, 如果其叶结点数为如果其叶结点数为 n0, n0, 度为度为2 2的结点数为的结点数为 n2,n2,则则n0n0n2n21.1.证明：若度为证明：若度为1 1的结点有的结点有n1n1个，总结点个数为个，总结点个数为n n，总边数为，总边数为e e，则根据二叉树的定义，则根据二叉树的定义， n=n0+n1+n2 n=n0+n1+n2 根据分支数与总结点数差个，根据分支数与总结点数差个，则则e

8、=2n2+n1=n-1e=2n2+n1=n-1因此，有因此，有 2 2n2+n1=n0+n1+n2-1n2+n1=n0+n1+n2-1 n2=n0-1 n0=n2+1 n2=n0-1 n0=n2+1 定义定义1 满二叉树满二叉树 (Full Binary Tree) 一棵深度为一棵深度为k且有且有2 k-1个结点的二叉树称为个结点的二叉树称为满二叉树。满二叉树。两种特殊形态的二叉树两种特殊形态的二叉树621754389 10 1113 14 1512满二叉树满二叉树215436 7216543非完全二非完全二叉树叉树定义定义2 完全二叉树完全二叉树 (Complete Binary Tree)

9、 若设二叉树的高度为若设二叉树的高度为h，则共有，则共有h层。除第层。除第 h 层层外，其它各层外，其它各层 (0 h- -1) 的结点数都达到最大个数，的结点数都达到最大个数，第第 h 层从右向左连续缺若干结点，这就是完全二叉层从右向左连续缺若干结点，这就是完全二叉树。树。621754389 10 11 12完全二完全二叉树叉树1231145891213671014151231145891267101234567123456性质性质4 4 具有具有 n (n n (n 0) 0) 个结点的完全二叉树的深个结点的完全二叉树的深度为度为 loglog2 2(n) (n) 1 1证明：证明：设完全

10、二叉树的深度为设完全二叉树的深度为 h h，则根据性质，则根据性质2 2和完全二叉和完全二叉树的定义有树的定义有2 2h h1 1 - 1 n - 1 n 2 2h h- 1- 1或或 2 2h h1 1 n 2 n 2h h取对数取对数 h h1 log1 data);-data);PreOrderTraverse(T-lchildPreOrderTraverse(T-lchild););PreOrderTraverse(T-rchildPreOrderTraverse(T-rchild);); 中序遍历二叉树的递归算法、后序遍历二叉树的递归算法均只是将printf(“%c”,T-data)

11、;放在中间或者最后执行就可。2、遍历二叉树的非递归算法先序遍历：算法1，将右子树根结点 入栈，(栈所需最大容量为n/2+1)；算法2将根结点入栈 中序遍历：在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈中弹出，访问，再遍历右子树后序遍历： 1）设定一个指针，指向 最近访问过的结点。在退栈取出根结点时，需判断：若根结点的右子树为空，或它的右子树非空，但已遍历完毕，即它的右子树根结点恰好是最近一次访问过的结点时，应该遍历该根结点。反之，该根结点应重新入栈，先遍历它的右子树。 2）还可同时设定一个标记，指示该根结点是第一次还是第二次入栈需用到栈，顺序栈的定义如下：typedef BiTN

12、ode* SElemType;typedef structSElemType *base;SElemType *top;int stacksize;SqStack;void preorder(BiTree T) SqStack S; BiTree P=T;InitStack(S);Push(S,NULL);while (P) printf(%c,P-data);if (P-rchild)Push(S,P-rchild);if (P-lchild)P=P-lchild;else Pop(S,P); void preorder(BiTree T)int top=0;BiTree stack20,

13、P=T;do while (P)printf(%c,P-data);stacktop=P; top+;P=P-lchild;if (top)top-;P=stacktop;P=P-rchild;while (top | P);中1void inorder(BiTree T)SqStack S; BiTree P=T;InitStack(S);dowhile(P) * (S.top) = P;S.top+;P=P-lchild;if (S.top)S.top-;P=*(S.top);printf(%c,P-data);P=P-rchild;while(S.top!=S.base) | P);vo

14、id inorder(BiTree T) SqStack S; BiTree P=T;InitStack(S);while( P | !Empty(S) if (P) Push(S,P);P=P-lchild; else Pop(S,P);printf(%c,P-data);P=P-rchild; 后序遍历的非递归算法后序遍历的非递归算法1 1void Postorder(BiTree T) BiTree p=T,q=NULL; SqStack S; InitStack(S); Push(S,p); while (!StackEmpty(S) if (p & p!=q) Push(S,

15、p); p=p-lchild; else Pop(S,p); if (!StackEmpty(S) if (p-rchild & p-rchild!=q) Push(S,p); p=p-rchild; else printf(%c,p-data); q=p; 后序遍历的非递归算法后序遍历的非递归算法2 2void postorder(BiTree T)BiTree P=T,q; int flag;SqStack S;InitStack(S); do while (P) *(S.top)=P;S.top+;P=P-lchild; q=NULL; flag=1; while (S.top!

16、=S.base) & flag) P=*(S.top-1); if (P-rchild = q) printf(%c,P-data); S.top-; q=p; else P=P-rchild;flag=0; while (S.top!=S.base);五、二叉树遍历应用1、：为二叉树建立二叉链表(递归算法递归算法) 输入：二叉树的先序序列结果：二叉树的二叉链表 基本思想：基本思想：输入（在空子树处添加*的二叉树的）先序序列（设每个元素是一个字符/）按先序编历的顺序，建立二叉链表的所有结点并完成相应结点的链接 D D A A BB C C EE FFT T 先序序列：A B D F C

17、 E（在空子树处添加*的二叉树的）先序序列：A B D * F * * C E * * * * A A F F E E D D C C B B* A A F F E E D D C C B BStatus CreateBiTree(BiTree &T) /输入（在空子树处添加*的二叉树的）先序序列（设每个元素是一个字符）按先序编历的顺序，建立二叉链表，并将该二叉链表根结点指针赋给T scanf (&ch); if (ch= = * ) T=NULL; / 若ch= = * 则T=NULL返回 else / 若ch! = * if (! (T=(BiTNode * )malloc

18、(sizeof(BiTNode) exit(OVERFLOW); T-date = ch; / 建立（根）结点 CreateBiTree(T-lchild); /构造左子树链表，并将左子树根结点指针赋 给（根）结点 的左孩子域 CreateBiTree(T-rchild); /构造右子树链表，并将右子树根结点指针赋给（根）结点 的右孩子域 return OK;/CreateBiTree2、二叉树的显示输出void PrintBiTree(BiTree T,int n)int i; char ch= ;if (T) PrintBiTree(T-rchild,n+1);for (i=1;idata

19、);PrintBiTree(T-lchild,n+1);int Count(BiTtree T) if (T=NULL) return 0; else return 1 + Count (T-lchild)+Count(T-rchild);3.3.计算二叉树结点个数计算二叉树结点个数( (递归算法递归算法) )4.4.求二叉树中叶子结点的个数求二叉树中叶子结点的个数int Countleaf(BiTree T ) /求二叉树中叶子结点的数目 if ( T=NULL ) return 0; /空树没有叶子 if(T-lchild=NULL&T-rchild=NULL) return 1;

20、/叶子结点 return Countleaf(T-lchild)+Countleaf(T-rchild);/左子树的叶子数加上右子树的叶子数int Height ( Bitree T ) /Height of a tree if ( T = NULL ) return -1; else int m = Height ( T-lchild ); int n = Height ( T-rchild ); return (m n) ? m+1 : n+1 ; 5.求二叉树高度(递归算法)6.复制二叉树void CopyTree(BiTree T,BiTree &T1) if (T) T1=(

21、BiTree)malloc(sizeof(BiTNode); if (!T1) printf(Overflown); exit(1); T1-data=T-data; T1-lchild=T1-rchild=NULL; CopyTree(T-lchild,T1-lchild); CopyTree(T-rchild,T1-rchild);7.左右子树互换void Exchange(BiTree &T)BiTree S;if (T) S=T-lchild; T-lchild=T-rchild; T-rchild=S; Exchange(T-lchild); Exchange(T-rchil

22、d); 六、按层次遍历二叉树六、按层次遍历二叉树 从根开始逐层访问，从根开始逐层访问，用用FIFOFIFO队列实现。队列实现。typedef BiTNode* ElemType;typedef structQElemType *base;int front,rear;SqQueue;void LevelOrderTraverse(BiTreevoid LevelOrderTraverse(BiTree T) T) BiTree p; SqQueue Q; InitQueue(Q BiTree p; SqQueue Q; InitQueue(Q);); if (T) Q.baseQ.rear=T

23、; if (T) Q.baseQ.rear=T; Q.rear=(Q.rear+1)%MAXQSIZE; Q.rear=(Q.rear+1)%MAXQSIZE; while (Q.front !=Q.rear) while (Q.front !=Q.rear) p=Q.baseQ.front; p=Q.baseQ.front; printf(%c,p printf(%c,p-data);-data); Q.front=(Q.front+1)%MAXQSIZE; Q.front=(Q.front+1)%MAXQSIZE; if (p-lchild if (p-lchild) ) Q.baseQ.

24、rear=p-lchild Q.baseQ.rear=p-lchild; ; Q.rear=(Q.rear+1)%MAXQSIZE; Q.rear=(Q.rear+1)%MAXQSIZE; if (p-rchild if (p-rchild) ) Q.baseQ.rear=p-rchild Q.baseQ.rear=p-rchild; ; Q.rear=(Q.rear+1)%MAXQSIZE; Q.rear=(Q.rear+1)%MAXQSIZE; 一、基本概念： 1、线索 (Thread): 指向结点前驱和后继的指针 若结点有左孩子，则lchild指示其左孩子，否则lchild中存储该结点的

25、前驱结点的指针；若结点有右孩子，则rchild指示其右孩子，否则rchild中存储指向该结点的后继结点的指针 2、实质：对一个非线性结构进行线性化操作，使每个结点（除第一和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。 3、说明：在线索树中的前驱和后继是指按某种次序遍历所得到的序列中的前驱和后继。概念: (p132) 线索链表、线索、线索化、线索二叉树中序遍历序列：D,B,H,E,A,F,C,G在中序序列中，D的后继是B，H的前趋是B，后继是E A A G G H H E E D D C C B B F F加上结点前趋后继信息（结索）的二叉树称为线索二叉树线索二叉树线索二叉树孩子

26、指针前趋指针后继指针Ltag=0, lchild为左子女指针Ltag=1, lchild为前驱线索Rtag=0, rchild为右子女指针Rtag=1, rchild为后继指针结点结构结点结构LtagRtagABCGEIDHFroot悬空？悬空？悬空？悬空？解：该二叉树中序遍历结果为解：该二叉树中序遍历结果为: : H, D, I, B, E, A, F, C, G所以添加线索应当按如下路径进行：所以添加线索应当按如下路径进行：为避免悬空为避免悬空态，应增设态，应增设一个头结点一个头结点三、线索二叉树的建立过程：三、线索二叉树的建立过程：例例1 1：画出以下二叉树对应：画出以下二叉树对应的中序

27、线索二叉树。的中序线索二叉树。00A00C00B11E11F11G00D11I11H注：此图中序遍历结果为注：此图中序遍历结果为: : H, D, I, B, E, A, F, C, G0-root0对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：四、线索二叉树的生成算法四、线索二叉树的生成算法目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后 继。继。注解：为方便添加结点的前驱或后继，需要设置两个指针：注解：为方便添加结点的前驱或后继，需要设置两个指针： p指针指针当前结点之指针；当前结点之指针； pre指

28、针指针前驱结点之指针。前驱结点之指针。技巧：当结点技巧：当结点p的左的左/右域为空时，只改写它的左域（装入前驱右域为空时，只改写它的左域（装入前驱pre），而其右域（后继）留给下一结点来填写。），而其右域（后继）留给下一结点来填写。 或者说，当前结点的指针或者说，当前结点的指针p应当送到前驱结点的空右域中。应当送到前驱结点的空右域中。若若p-lchildNULL, ,则则p-Ltag=1;p-lchildp-Ltag=1;p-lchildpre; /p /p的前驱结点指针的前驱结点指针pre存入左空域存入左空域若若pre-rchildNULL, 则则pre-Rtagpre-Rtag1;pre-

29、rchild=p; /p存入其前驱结点存入其前驱结点pre的右的右空域空域Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) / 中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。 if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode) exit(OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread；/ 建头结点; Thrt-rchild = Thrt; / 右指针回指 if (!T) Thrt-lchild = Thrt; / 若二叉树空，则

30、左指针回指 else Thrt-lchild = T; pre = Thrt; InThreading(T); / 算法6.7：中序遍历进行中序线索化 pre-rchild = Thrt; pre-RTag = Thread; / 最后一个结点线索化 Thrt-rchild = pre; return OK; / InOrderThreading中序线索二叉树的创建算法：中序线索二叉树的创建算法：void InThreading(BiThrTree p) / 算法6.7 if (p) InThreading(p-lchild); / 左子树线索化 if (!p-lchild) / 建前驱线索

31、p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后继线索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持pre指向p的前驱 InThreading(p-rchild); / 右子树线索化 / InThreading中序线索二叉树的创建算法：中序线索二叉树的创建算法：五、线索二叉树的遍历五、线索二叉树的遍历 理论上，只要找到序列中的第一个结点，然后依次访问结理论上，只要找到序列中的第一个结点，然后依次访问结点的后继直到后继为空时结束。点的后继直到后继为空时结束。在线索化二叉树中，并不是每个

32、结点都能直接找到在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为其后继的，当标志为0 0时，时，R_child=R_child=右孩子地址指针，并非后右孩子地址指针，并非后继！需要通过一定运算才能找到它的后继。继！需要通过一定运算才能找到它的后继。以以中序线索二叉树中序线索二叉树为例：为例：对叶子结点（对叶子结点（RTag=1），直接后继指针就在其），直接后继指针就在其rchild域内；域内；对其他结点（对其他结点（RTag=0），直接后继是其），直接后继是其右子树最左下的结点右子树最左下的结点；（因为中序遍历规则是（因为中序遍历规则是LDR，）Status InOrderTra

33、verse_Thr(BiThrTree T, Status (*Visit)(ElemType) BiThrTree p; p = T-lchild; / p指向根结点 while (p != T) / 空树或遍历结束时， p=T while (p-LTag=Link) p = p-lchild; if (!Visit(p-data) return ERROR; / 访问其左子树为空的结点 while (p-RTag=Thread & p-rchild!=T) p = p-rchild; Visit(p-data); / 访问后继结点 p = p-rchild; / p进至其右子树根

34、return OK;线索二叉树的中序遍历算法：线索二叉树的中序遍历算法：程序注解 (非递归，且不用栈）：P=T-lchild; /从头结点进入到根结点；while( p!=T) while(p-LTag=link)p=p-lchild; /先找到中序遍历起点 if(!visit(p-data) return ERROR; /若起点值为空则出错告警 while(p-RTag=Thread ) p=p-rchild; Visit(p-data); /若有后继标志，则直接提取p-rchild中线索并访问后继结点；p=p-rchild; /当前结点右域不空或已经找好了后继，则一律从结点的右子树开始重复

35、 的全部过程。Return OK;LTag=0RTag=11.1.双亲表示：双亲表示：通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。 以一组连续空间存储树的结点，同时在结点中附设一个以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。指针，存放双亲结点在链表中的位置。6.46.4树与森林树与森林ABCDEFGdataparentA B C D E F G- -1 0 0 0 1 1 30 1 2 3 4 5 6思路：思路：将每个结点的孩子排列起来，形成一个带表头（装父结点）的线性表（n个结点要设立n个链表）；再将n个表头用数组存放起来，这样就形成一

36、个混合结构。例如例如：abecdfhgdefghgfedcbah123456782 2、孩子表示法、孩子表示法bc思路思路：用二叉链表来表示树，但链表中的两个指针域含义不同。左指针指向该结点的第一个孩子；右指针指向该结点的下一个兄弟结点。nextsiblingdatafirstchild3 3、用孩子兄弟表示法来存储、用孩子兄弟表示法来存储指向左孩子指向左孩子指向右兄弟指向右兄弟abecdfhgbacedfgh例如例如：二、树与二叉树的转换二、树与二叉树的转换 二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。树与二叉树转换方法树根结点X的第一个孩子结点X紧邻的右兄弟

37、二叉树根结点X的左孩子结点X的右孩子I IA AC CB BD DH HG GF FE EF FI IA AB BD DH HG GC CE E方法：方法：加加线线抹线抹线旋转旋转 abeidfhgcabeidfhgc兄弟相连兄弟相连长兄为父长兄为父孩子靠左孩子靠左二叉树怎样还原为树？二叉树怎样还原为树？abeidfhgc要点：把所有右孩子变为兄弟！要点：把所有右孩子变为兄弟！ abeidfhgc三、森林三、森林森林森林：树的集合：树的集合 将森林中树的根看成兄弟，可用树孩子兄弟表示法存储森林；用树与二叉树的转换方法，进行森林与二叉树转换；可用树的遍历方法对森林进行遍历； J J O O P

38、P N N M M L L K KI IA AC CB BD DH HG GF FE E包含两棵树的森林T1 T2 T3T1 T2 T3AFHB C DGIJEKAFBCDEGHIKJABCEDHIKJFG3 棵树的森林各棵树的二叉树表示森林的二叉树表示q森林与二叉树的转换森林与二叉树的转换ABCDEFGHJIABCDEFGHJIBCDEFGHJI森林转二叉树举例：森林转二叉树举例：兄弟相连兄弟相连 长兄为父长兄为父孩子靠左孩子靠左 头根为根头根为根 二叉树如何还原为森林？二叉树如何还原为森林？要点：要点：把最右边的子树变为森林，其余右子树变为兄弟把最右边的子树变为森林，其余右子树变为兄弟 A

39、BCDEFGHJIABCDEFGHJIEFABCDGHJI即即B=root, LB, RB F=TB=root, LB, RB F=T1 1, T, T2 2, , ,T,Tm m 当树非空时当树非空时u访问根结点访问根结点u依次先根遍历根的各棵子树依次先根遍历根的各棵子树树先根遍历树先根遍历 ABEFCDGABEFCDG对应二叉树前序遍历对应二叉树前序遍历 ABEFCDGABEFCDG树的先根遍历结果与其对应二叉树树的先根遍历结果与其对应二叉树 表示的前序遍历结果相同表示的前序遍历结果相同树的先根遍历可以借助对应二叉树的前序遍历算法实现树的先根遍历可以借助对应二叉树的前序遍历算法实现ABCE

40、DGF1、树的、树的先根次序先根次序遍遍历历四、树和森林的遍历：2、树的后根次序遍历、树的后根次序遍历:当树非空时当树非空时u依次后根遍历根的各棵子树依次后根遍历根的各棵子树u访问根结点访问根结点树后根遍历树后根遍历 EFBCGDAEFBCGDA对应二叉树中序遍历对应二叉树中序遍历 EFBCGDAEFBCGDA树的后根遍历结果与其对应二叉树树的后根遍历结果与其对应二叉树 表示的中序遍历结果相同表示的中序遍历结果相同树的后根遍历可以借助对应二叉树的中序遍历算法树的后根遍历可以借助对应二叉树的中序遍历算法实现实现ABCEDGF6.66.6哈夫曼树哈夫曼树 (Huffman Tree)(Huffman Tree)一、基本概念一、基本概念1、路径长度、路径长度 (Path Length)两个结点之间的路径长度 是连接两结点的路径上的分支数。 树的路径长度是各结点(包括叶结点和非叶结点)到根结点的路径长度之和8123456712345678树的路径长度：树的路径长度：PL = 2*1+2*4+3*1 =13树的路径长度树的路径长度PL = 2*1+2*2+3*3+4*1 = 19234567812、带权路径长度、带权路径长度 (We