《第6章树和二叉树TreeandBinaryTree》由会员分享，可在线阅读，更多相关《第6章树和二叉树TreeandBinaryTree（132页珍藏版）》请在金锄头文库上搜索。
1、第6章树和二叉树Tree and Binary Tree第六章 树和二叉树目录 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树 6.4 线索二叉树 6.5 树和森林 6.6 哈夫曼树及其应用6.1 树的定义和基本术语6.1.1 树的定义 6.1.2 树的术语 树的定义和基本术语树的定义和基本术语6.1.1 树的定义v树是树是n（n0）个）个结点的有限集。在任意一棵非空点的有限集。在任意一棵非空树中，有且中，有且仅有一个称有一个称为根的根的结点；其余点；其余结点分点分为m（m0）个互不相交的子集，每个子集又是一）个互不相交的子集，每个子集又是一棵棵树，称，称为根的子根的子树。v这
2、是一个是一个递归的定的定义在在树的定的定义中又用到了中又用到了树的概念。的概念。v递归是是树的固有特性的固有特性。 树的定义和基本术语树的定义和基本术语 树的定义树的定义AFEDCBIHGKJ8树根：A8三个互不相交的子集： B，E，F，J C D，G，H，I，K 8每个子集都是满足树的定义的树，称为A的子树B子树、C子树、D子树。8树根A没有直接前驱；其余结点有且仅有一个直接前驱有，有0个或多个直接后继。树的特征：层次性和分支性树的定义和基本术语树的定义和基本术语 树的定义树的定义6.1 树的定义和基本术语 6.1.1 树的定义 6.1.2 树的术语 树的定义和基本术语树的定义和基本术语 树
3、的定义树的定义6.1.2 树的术语8结点的度：结点的非空子树个数结点的非空子树个数8树的度：树中各结点度的最大值树中各结点度的最大值8分支结点(非终端结点) ：度度0的结点的结点8叶子结点(终端结点)：度度=0的结点的结点8孩子：结点子树的根称为该结点的孩子结点子树的根称为该结点的孩子8双亲：孩子的直接前驱结点称为该结点的双亲孩子的直接前驱结点称为该结点的双亲8兄弟：同一个双亲的结点互称为兄弟同一个双亲的结点互称为兄弟8子孙：以某结点为根的各个子树上的所有结点称为该以某结点为根的各个子树上的所有结点称为该结点的子孙结点的子孙8 祖先：从树根到该结点所经过的所有分支结点称为从树根到该结点所经过的
4、所有分支结点称为该结点的祖先该结点的祖先AFEDCBIHGKJ8结点的层次：从树根开始自上而下编号，从树根开始自上而下编号，树根的层次为树根的层次为1，其余结点的层次为其，其余结点的层次为其双亲的层次双亲的层次18树的深度（高度）：结点层次的最大值结点层次的最大值8有序树和无序树：若树中所有结点的孩树中所有结点的孩子都长幼有序，位置不能互换，称为有子都长幼有序，位置不能互换，称为有序树，否则称为无序树序树，否则称为无序树。8森林：m（m0）个树的集合）个树的集合AFEDCBIHGKJTree=(A ( B( E( J ),F ), C, D( G, H ( K ), I ) ) )树的其他表示
5、方式：集合，圈，条树的定义和基本术语树的定义和基本术语 树的定义树的定义树的基本运算：初始化空树初始化空树InitTree(&T)销毁树销毁树DestroyTree(&T)创建树创建树CreateTree(&T, definition)清空树清空树ClearTree(&T)判断空树判断空树TreeEmpty(T)求树的深度求树的深度TreeDepth(T)求双亲求双亲parent(T, cur_e)求长子求长子LeftChild(T, cur_e)求右邻兄弟求右邻兄弟RightSibling(T, cur_e)树的定义和基本术语树的定义和基本术语 树的定义树的定义插入子树插入子树InsertC
6、hild(&T, &p, i, c)删除子树删除子树DeleteChild(&T, &p, i)按层次遍历按层次遍历TraverseTree(T, visite()树的定义和基本术语树的定义和基本术语 树的定义树的定义第六章 树和二叉树目录 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树 6.4 线索二叉树 6.5 树和森林 6.6 哈夫曼树及其应用6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构二叉树二叉树6.2.1 二叉树的定义8二叉树是二叉树是n(n0)个结点的有限集。该集合或者个结点的有限集。该集合或者为空，或者由一个根加
7、上两棵互不相交的、分为空，或者由一个根加上两棵互不相交的、分别称为左子树和右子树的二叉树组成。别称为左子树和右子树的二叉树组成。8这是一个递归的定义这是一个递归的定义在二叉树的定义中又用在二叉树的定义中又用到了二叉树的概念。到了二叉树的概念。根根左子树左子树右子树右子树二叉树二叉树 二叉树的定义二叉树的定义从二叉树的定义得知：1.1.二叉树可以为空，称为空二叉树；二叉树可以为空，称为空二叉树；2.2.非空二叉树一定有两个子树：非空二叉树一定有两个子树： 左子树和右子树；左子树和右子树；3.3.左、右子树有次序关系，不能互换左、右子树有次序关系，不能互换; ;4.4.二叉树可以有二叉树可以有5
8、5种基本形态：种基本形态：5.5.二叉树是结点的度都不超过二叉树是结点的度都不超过2 2的有序树。的有序树。ACIBGFHED二叉树二叉树 二叉树的定义二叉树的定义三个结点的树有三个结点的树有两种两种不同的形态：不同的形态：三个结点的二叉树有三个结点的二叉树有五种五种不同的形态：不同的形态：二叉树二叉树 二叉树的定义二叉树的定义二叉树的基本运算：初始化空二叉树初始化空二叉树InitBiTree(&T)销毁二叉树销毁二叉树DestroyBiTree(&T)创建二叉树创建二叉树CreateBiTree(&T, definition)清空二叉树清空二叉树ClearBiTree(&T)判断空二叉树判断
9、空二叉树BiTreeEmpty(T)求二叉树深度求二叉树深度BiTreeDepth(T)求双亲求双亲parent(T, e)求左孩子求左孩子LeftChild(T, e)求右孩子求右孩子RightChild(T, e)二叉树二叉树 二叉树的定义二叉树的定义求左兄弟求左兄弟LeftSibling(T, e)求右兄弟求右兄弟RightSibling(T, e)插入子树插入子树InsertChild(T, p, LR, c)删除子树删除子树DeleteChild(T, p, LR)先序遍历二叉树先序遍历二叉树PreOrderTraverse(T,visite()中序遍历二叉树中序遍历二叉树InOrd
10、erTraverse(T,visite()后序遍历二叉树后序遍历二叉树PostOrderTraverse(T,visite()按层次遍历按层次遍历levelTraverse(T, visite()二叉树二叉树 二叉树的定义二叉树的定义6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构二叉树二叉树6.2.2 二叉树的性质性质性质1. 在二叉树的第在二叉树的第i层上至多有层上至多有2i-1个结点；个结点；性质性质2. 深度为深度为k的二叉树上至多有的二叉树上至多有2k-1个结点个结点二叉树二叉树 二叉树的性质二叉树的性质性质3. 设二叉树中有n2个度为
11、2个结点，n1个度为1的结点，n0个度为0的结点，则有：n0 = n2+1 n = n0+n1+n2(1)树枝数树枝数 = n00n11n22 = n1+2n2n = 树枝数树枝数+1 = n1+2n2+1(2)由由(1)、(2)可得可得n0 = n2+1二叉树二叉树 二叉树的性质二叉树的性质满二叉树：结点总数 n2k1所有非终端结点的度都等于2且所有树叶都分布在同一个层次上132675489101112131415二叉树二叉树 二叉树的性质二叉树的性质完全二叉树： 将深度为将深度为k k，有，有n n个结点的二叉树自上而下，自个结点的二叉树自上而下，自左向右进行编号，编号与深度为左向右进行编
12、号，编号与深度为k k的满二叉树中前的满二叉树中前n n个结个结点一致。点一致。 前前k1层是满的，第层是满的，第k层可以不满，但第层可以不满，但第k层结点集中在左侧层结点集中在左侧132675489101112132675489101112二叉树二叉树 二叉树的性质二叉树的性质性质4. 具有n个结点的完全二叉树的深度为k log2n +1 或 k= log2(n+1) 证明： 设完全二叉树的深度为k，根据完全二叉树的定义有 2k1-1 n 2k1 或 2k1 n 2k 取对数有 k11, 则则X的双亲的编号的双亲的编号为为 i/2 ;2.若若X有左孩子，则有左孩子，则X左孩子的编号为左孩子的
13、编号为2i；3.若若X有右孩子，则有右孩子，则X右孩子的编号为右孩子的编号为2i1；4.若若i为奇数且为奇数且i1，则，则X的左兄弟为的左兄弟为i1；5.若若i为偶数且为偶数且idata);/访根访根 preorder(bt-lchild); preorder(bt-rchild);若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则,(1)中序遍历左子树中序遍历左子树(2)访问根；访问根；(3)中序遍历右子树中序遍历右子树中序遍历的递归定义：二叉树二叉树 遍历二叉树遍历二叉树 void inorder(BiTree bt) if(!bt) return; inorder(bt-lchil
14、d); visite(bt-data);/访根访根 inorder(bt-rchild);若二叉树为空，则空操作若二叉树为空，则空操作;否则否则,(1)后序遍历左子树后序遍历左子树(2)后序遍历右子树后序遍历右子树(3)访问根；访问根；后序遍历的递归定义：二叉树二叉树 遍历二叉树遍历二叉树 void postorder(BiTree bt) if(!bt) return; postorder(bt-lchild); postorder(bt-rchild); visite(bt-data);/访根访根ACBGEDIFH先序遍历序列：先序遍历序列：中序遍历序列：中序遍历序列：后序遍历序列：后序遍
15、历序列： A B D G E C F H ID G B E A C H IFG D E B I H F C A二叉树的遍历二叉树二叉树 遍历二叉树遍历二叉树void preorder (BiTree bt) if( !bt ) return; visite(bt-data); preorder(bt-lchild); preorder(bt-rchild);void inorder (BiTree bt) if( !bt ) return; inorder(bt-lchild); visite(bt-data); inorder(bt-rchild);void postorder (BiTre
16、e bt) if( !bt ) return; postorder(bt-lchild); postorder(bt-rchild); visite(bt-data); 现将三个遍历算法中的现将三个遍历算法中的visitevisite语句去掉，我们发语句去掉，我们发现这三个算法完全一样。这说明三种遍历的路径是一现这三个算法完全一样。这说明三种遍历的路径是一样的，只是样的，只是访问根的时机不同而已而已。二叉树二叉树 遍历二叉树遍历二叉树void InOrder(BiTree bt, void(*visit)(BiTree) /中序遍历的非递归算法中序遍历的非递归算法 InitStack(S);
17、e=BT,Travel; if(BT) Push(S,e); while(!StackEmpty(S) Pop(S,e); if(e.task=Visit) visit(e.ptr); else if(e.ptr!=NULL) p=e.ptr; e.ptr=p-rchild; e.task=Travel; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); /if/if /while/while/InOrder/InOrderACIBGFHED另一种先序遍历的非递归算法：v
18、oid PreOrder(BiTree bt)if(!bt) return;InitStack(S); push(S, bt); /树根的指针进栈树根的指针进栈while(!EmptyStack(S)pop(S, p);while(p) /沿着左链一路向下沿着左链一路向下 visite(p-data); /访问访问 if(p-rchild)push(S,p-rchild);/右孩子进栈右孩子进栈 p=p-lchild; 二叉树二叉树 遍历二叉树遍历二叉树ACIBGFHED6.3 遍历二叉树6.3.1 先序、中序和后序遍历6.3.2 算术表达式的二叉树表示6.3.3 二叉树的运算举例6.3.4
19、按层次遍历二叉树6.3.5 构造二叉链表二叉树二叉树 遍历二叉树遍历二叉树6.3.2 算术表达式的二叉树表示二目算符二目算符右操作数右操作数左操作数左操作数一目算符一目算符右操作数右操作数二叉树二叉树 算术表达式的二叉树表示算术表达式的二叉树表示-a+b(c-d)-e/fcdb-a-+ef-/先序序列：先序序列：-+-ab-cd/ef后序序列：后序序列：a-bcd-+ef/-中序序列：中序序列：-a+bc-d-e/f波兰式逆波兰式二叉树二叉树 算术表达式的二叉树表示算术表达式的二叉树表示6.3 遍历二叉树6.3.1 先序、中序和后序遍历6.3.2 算术表达式的二叉树表示6.3.3 二叉树的运算
20、举例6.3.4 按层次遍历二叉树6.3.5 创建二叉链表二叉树二叉树 遍历二叉树遍历二叉树举例1. 计算二叉树中的结点数：int Number(BiTree bt) / /二叉树结点数二叉树结点数1+1+左子树结点数左子树结点数+ +右子树结点数右子树结点数 if(!bt) return 0; /空二叉树，没有结点空二叉树，没有结点 else nl=Number(bt-lchild);/计算左子树结点数计算左子树结点数 nr=Number(bt-rchild);/计算右子树结点数计算右子树结点数 return 1+nl+nr; 二叉树二叉树 遍历二叉树遍历二叉树 二叉树运算举例二叉树运算举例举
21、例举例2 2，计算二叉树中叶子的数目，计算二叉树中叶子的数目：int Leafs(BiTree bt) /叶子数左子树叶子数叶子数左子树叶子数+右子树叶子数右子树叶子数 if(!bt) return 0; /空二叉树空二叉树 if(！bt-lchild & ！bt-rchild) return 1; /树叶树叶 LL=Leafs(bt-lchild); /计算左子树的叶子数计算左子树的叶子数 LR=Leafs(bt-rchild); /计算右子树的叶子数计算右子树的叶子数 return LL+LR; 二叉树二叉树 遍历二叉树遍历二叉树 二叉树运算举例二叉树运算举例举例3，计算二叉树的深度：in
22、t Height(BiTree bt) /H=1+Max(左子树深度，右子树深度左子树深度，右子树深度) if(!bt) return 0; hl=Height(bt-lchild); /计算计算bt的左子树深度的左子树深度 hr=Height(bt-rchild); /计算计算bt的右子树深度的右子树深度 return 1+(hlhr ? hl:hr) 二叉树二叉树 遍历二叉树遍历二叉树 二叉树运算举例二叉树运算举例举例4,打印每个结点的层次数：void level(BiTree bt，int lev) / /结点的层次数双亲的层次数结点的层次数双亲的层次数1 1 /lev/lev传递双亲的
23、层次，传递双亲的层次，levlev所对应的实参的初值应为所对应的实参的初值应为0 0 if(!bt )return; lev+; printf(bt-data, lev);/打印结点的值和它的层次数打印结点的值和它的层次数 level(bt-lchild, lev) level(bt-rchild, lev) & 二叉树二叉树 遍历二叉树遍历二叉树 二叉树运算举例二叉树运算举例举例举例5：计算表达式二叉树的值：计算表达式二叉树的值int Calculate (BiTree T) /计算表达式二叉树的值计算表达式二叉树的值 int nl,nr; if(!T-lchild&!T-rchild) r
24、eturn T-data; nl=Calculate(T-lchild); /计算左子树计算左子树 nr=Calculate(T-rchild); /计算右子树计算右子树 switch(T-data) case +: return nl+nr; case -: return nl - nr; case *: return nl * nr; case /: return nl / nr; 二叉树二叉树 遍历二叉树遍历二叉树 二叉树运算举例二叉树运算举例举例举例6：打印树根到每个树叶的路径：打印树根到每个树叶的路径void PrintRoute(BiTree T) /利用栈利用栈S S保存树根到当
25、前结点的路径保存树根到当前结点的路径 if(!T) return; /空二叉树空二叉树 Push(S, T-data); /栈栈S S是全局变量是全局变量 if(!T-lchild&!T-rchild) /是树叶是树叶 printstack(S); /打印自栈底至栈顶底内容打印自栈底至栈顶底内容 else PrintRoute(T-lchild); /遍历左子树遍历左子树 PrintRoute(T-rchild); /遍历右子树遍历右子树 /else/else Pop(S, e);二叉树二叉树 遍历二叉树遍历二叉树 二叉树运算举例二叉树运算举例ACIBGFHED6.3 遍历二叉树6.3.1 先
26、序、中序和后序遍历6.3.2 算术表达式的二叉树表示6.3.3 二叉树的运算举例6.3.4 按层次遍历二叉树6.3.5 创建二叉链表二叉树二叉树 遍历二叉树遍历二叉树 自上而下、自左向右地遍历二叉树时，先被访自上而下、自左向右地遍历二叉树时，先被访问结点的孩子先被访问，故需要借助一个队列来记问结点的孩子先被访问，故需要借助一个队列来记录已访问过的结点的孩子录已访问过的结点的孩子。6.3.4 按层次遍历二叉树二叉树二叉树 遍历二叉树遍历二叉树 按层次遍历二叉树按层次遍历二叉树按层次遍历算法思想：1.1.空树空树, , 结束。结束。2.2.初始化一个空队列初始化一个空队列Q, Q, 树根入队树根入
27、队; ;3.3.队头队头e e元素出队元素出队, , 访问访问e;e;4.4.如果如果e e有左孩子有左孩子, , 则左孩子入队则左孩子入队; ;5.5.如果如果e e有右孩子有右孩子, , 则右孩子入队则右孩子入队; ;6.6.如果队列不空转如果队列不空转3; 3; 否则结束。否则结束。二叉树二叉树 遍历二叉树遍历二叉树 按层次遍历二叉树按层次遍历二叉树void Traverse(BiTree bt) /按层次遍历二叉树算法按层次遍历二叉树算法 if( !bt ) return ; / /空树空树 InitQueue(Q); /初始化空队列初始化空队列Q Q EnQueue(Q, bt);
28、/ /根入队根入队 while( !EmptyQueue(Q) ) DeQueue(Q, p); /队头队头p p出队出队 visite(p-data); / /访问访问p p if(p-lchild) EnQueue(Q，p-lchild); /p/p的左孩子入队的左孩子入队 if(p-rchild) EnQueue(Q,p-rchild); /p/p的右孩子入队的右孩子入队 二叉树二叉树 遍历二叉树遍历二叉树 按层次遍历二叉树按层次遍历二叉树6.3 遍历二叉树6.3.1 先序、中序和后序遍历6.3.2 算术表达式的二叉树表示6.3.3 二叉树的运算举例6.3.4 按层次遍历二叉树6.3.5
29、 创建二叉链表二叉树二叉树 遍历二叉树遍历二叉树6.3.4 创建二叉链表 扩展二叉树的先序序列 扩展二叉树的后序序列 二叉树的先序序列和中序序列 二叉树的后序序列和中序序列 扩展二叉树的按层次遍历序列二叉树二叉树 遍历二叉树遍历二叉树 创建二叉链表创建二叉链表已知扩展二叉树的先序序列, 创建二叉树ACB#D#G#FEABD#G#CE#F#BiTree CreateBiTree( ) scanf(ch); if(ch=#) return NULL; p=new BiTNode; p-data=ch; p-lchild=CreateBiTree( ); p-rchild=CreateBitree(
30、 ); return p;二叉树二叉树 遍历二叉树遍历二叉树 创建二叉链表创建二叉链表6.3.4 构造二叉链表 扩展二叉树的先序序列 扩展二叉树的后序序列 二叉树的先序序列和中序序列 二叉树的后序序列和中序序列 扩展二叉树的按层次遍历序列二叉树二叉树 遍历二叉树遍历二叉树 创建二叉链表创建二叉链表已知扩展二叉树的后序序列, 创建二叉树#G D#B#E#FCA 算法思想： 借助一个栈。从左向右扫描后序序列，当遇到，空指针进栈；当遇到字母，申请一个结点S，弹出两个栈顶，分别作为S的右孩子和左孩子，S进栈；直至序列扫描完序列的结束符二叉树二叉树 遍历二叉树遍历二叉树 创建二叉链表创建二叉链表void
31、 CreateTree(BiTree &bt)/输入扩展二叉树的后序序列，创建二叉树输入扩展二叉树的后序序列，创建二叉树 InitStack(S); scanf(&ch); while(ch !=EndMark) if(ch=#) push(S, NULL); else p=(BiTree)malloc(sizeof(BiNode); p-data=ch; pop(S, p-rchild); pop(S, p-lchild); push(S, p); scanf(&ch); pop(S, bt); /树根留在栈顶6.3.4 构造二叉链表 扩展二叉树的先序序列 扩展二叉树的后序序列 二叉树的先序
32、序列和中序序列 二叉树的后序序列和中序序列 扩展二叉树的按层次遍历序列二叉树二叉树 遍历二叉树遍历二叉树 创建二叉链表创建二叉链表已知二叉树的先序序列为：ABDEGCFH， 中序序列为：DBGEACHF，画出二叉树。先序序列BDEGCFH中序序列DBGECHFAAABDEGDBGECFHCHF由先序序列确定树根；中序序列区分左、右子树二叉树二叉树 遍历二叉树遍历二叉树 创建二叉链表创建二叉链表01234567先序序列 preABDEGCFH01234567中序序列 indDBGEACHFlow2hig2low1hig1m树根： prelow1, indm左子树：prelow1+1.low1+m
33、-low2, indlow2.m-1右子树：prelow1+m-low2+1.hig1, indm+1.hig2二叉树二叉树 遍历二叉树遍历二叉树 创建二叉链表创建二叉链表BiTree Create (char pre , char ind , int low1, int hig1, int low2, int hig2) /根据二叉树的先序序列和中序序列创建二叉链表根据二叉树的先序序列和中序序列创建二叉链表 if (low1hig1) return NULL; p=(BiTree)malloc(sizeof(BiNode); p-data=pre low1; m=low2; while(pr
34、e low1 != indm ) m+; /在中序序列中找根在中序序列中找根 p-lchild=Create(pre, ind, low1+1, low1+m-low2, low2, m-1); p-rchild=Create(pre,ind, low1+m-low2+1, hig1, m+1, hig2); return p;二叉树二叉树 遍历二叉树遍历二叉树 创建二叉链表创建二叉链表6.3.4 构造二叉链表 扩展二叉树的先序序列 扩展二叉树的后序序列 二叉树的先序序列和中序序列 二叉树的后序序列和中序序列 扩展二叉树的按层次遍历序列由后序序列确定树根；中序序列区分左、右子树需要借助一个队列
35、来实现二叉树二叉树 遍历二叉树遍历二叉树 创建二叉链表创建二叉链表练习1、假设在树中，结点x是结点y的双亲时,用(x,y)来表示树边.已知一棵树边的集合(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用树形表示法出此树，并回答下列问题：(1)哪个是根结点?(2)哪些是叶结点?(3)哪个是g的双亲?(4)哪些是g的祖先?(5)哪些是g的孩子?(6)哪些是e的子孙?(7)哪些是e的兄弟?哪些是f的兄弟?(8)结点b和n的层次各是多少?(9)树的深度是多少?(10)以结点c为根的子树的深度是多少
36、?(11) 树的度数是多少?练习2、具有100个结点的完全二叉树的叶子结点数为【】。3、 分别写出下图所示各二叉树的前序、中序和后序序列。练习4、若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。 (1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。 (2)已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。思考题5、试找出分别满足下面条件的所有二叉树：前序序列和中序序列相同； 中序序列和后
37、序序列相同；前序序列和后序序列相同； 前序、中序、后序序列均相同第六章 树和二叉树目录 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 哈夫曼树及其应用 6.4.1 树的存储结构1. 双亲表示法双亲表示法2. 孩子表示法孩子表示法3. 带双亲的孩子链表带双亲的孩子链表4. 孩子兄弟表示法孩子兄弟表示法6.4.2 树、森林与二叉树的关系 1. 树转换成二叉树树转换成二叉树 2. 森林转换成二叉树森林转换成二叉树 3. 二叉树转换成森林二叉树转换成森林 6.4.3 树和森林的遍历6.4 树和森林AFEDCBIHGKJdataparent01A0
38、2B13C14D15E26F27G48H49I410J511K8root=1一、双亲表示法树的存储结构树的存储结构 双亲表示法双亲表示法DEFCBKIHJGAT设树的度为设树的度为K，空指针数，空指针数nK(n1)n(K1)1AFEDCBIHGKJ二、孩子表示法-多叉链表树的存储结构树的存储结构 孩子表示法孩子表示法AFEDCBIHGKJdata01A2B3C4D5E6F7G8H9I10J11K243798651011firstchildroot=1child next二、孩子表示法-孩子链表树的存储结构树的存储结构 孩子表示法孩子表示法 孩子链表孩子链表typedef struct CTNo
39、de /孩子结点孩子结点 int child; struct CTNode *next; CTNode，*Childptr;typedef struct /表头结点表头结点 TElemType data; ChildPtr firstchild; CTBox;typedef struct CTBox nodesmaxsize;int forest5; int n, root,ntree; /结点数和根下标结点数和根下标 CTree;child nextdatafirstchild树的存储结构树的存储结构 孩子表示法孩子表示法 孩子链表孩子链表AFEDCBIHGKJdata01A02B13C14
40、D15E26F27G48H49I410J511K8243798651011firstchildparent三、带双亲的孩子链表树的存储结构树的存储结构 孩子表示法孩子表示法 双亲的带孩子链表双亲的带孩子链表typedef struct CTNode /孩子结点孩子结点 int child; struct CTNode *next; CTNode，*Childptr;typedef struct /表头结点表头结点 TElemType data; ChildPtr firstchild; CTBox;typedef struct CTBox nodesmaxsize;int forest10;
41、int n, ntree; /结点数和树的数目结点数和树的数目 CTree;child nextdatafirstchild树的存储结构树的存储结构 孩子表示法孩子表示法 孩子链表孩子链表firstchilddatanextsibling长子长子数据数据右邻兄弟右邻兄弟AFEDCBIHGKJ AB F C E D I HG J K 四、孩子兄弟链表树的存储结构树的存储结构 孩子兄弟链表孩子兄弟链表6.4.1 树的存储结构1. 双亲表示法双亲表示法2. 孩子表示法孩子表示法3. 带双亲的孩子链表带双亲的孩子链表4. 孩子兄弟表示法孩子兄弟表示法6.4.2 树、森林与二叉树的关系 1. 树转换成二
42、叉树树转换成二叉树 2. 森林转换成二叉树森林转换成二叉树 3. 二叉树转换成森林二叉树转换成森林 6.4.3 树和森林的遍历6.4 树和森林6.4.2 树、森林与二叉树的关系1. 树转换成二叉树 树用孩子兄弟用孩子兄弟链表表示表表示时，就已，就已转化成二叉化成二叉树了。一棵了。一棵树可以唯一地可以唯一地转换成一棵右子成一棵右子树为空的空的二叉二叉树。 树、森林与二叉树的关系树、森林与二叉树的关系 树转换成二叉树树转换成二叉树下面介绍直观的转换方法：1. 1. 把树中所有的兄弟之间用树枝相连；把树中所有的兄弟之间用树枝相连；2. 2. 每个结点仅保留与长子的连线，删除结点与其余孩每个结点仅保留
43、与长子的连线，删除结点与其余孩 子的连线：子的连线： 3. 3. 以树根为圆心，顺时针转以树根为圆心，顺时针转4545度度树、森林与二叉树的关系树、森林与二叉树的关系 树转换成二叉树树转换成二叉树AFEDCBIHGKJ1.把树中所有的兄弟之间用树枝相连；2.每个结点仅保留与长子的连线，删除结点与其余孩子的连线； 3.以树根为圆心，顺时针转45度。度。AKJDCBIHGFE树、森林与二叉树的关系树、森林与二叉树的关系 树转换成二叉树树转换成二叉树2. 森林转换成二叉树 直直观的的转换方法：方法： 1.1.把森林中的每一棵把森林中的每一棵树转换成二叉成二叉树 2.2.将所有二叉将所有二叉树的的树根
44、用根用线相相连 3.3.以第一棵二叉以第一棵二叉树的的树根根为圆心，心，顺时针转4545度度树、森林与二叉树的关系树、森林与二叉树的关系 森林转换成二叉树森林转换成二叉树EFGHIKJLABDCLKJIHEGFCBADLKJIHEGFCBAD树、森林与二叉树的关系树、森林与二叉树的关系 森林转换成二叉树森林转换成二叉树LKJIHEGFCBADEFGHIKJLABDC树、森林与二叉树的关系树、森林与二叉树的关系 森林转换成二叉树森林转换成二叉树森林转换成二叉树的形式定义森林森林F T1, T2, ., Tm 二叉树二叉树B(root, LB,RB) :(1) 若若F为空，则为空，则B为空二叉树为
45、空二叉树.(2) 若若F非空，则非空，则B的根的根root是是T1的根；的根；B的左子树由的左子树由T1的子树森林转换而成；的子树森林转换而成；B的右子树由的右子树由F中除第一棵树以外的剩余树转换而中除第一棵树以外的剩余树转换而成成.树、森林与二叉树的关系树、森林与二叉树的关系 森林转换成二叉树森林转换成二叉树3.二叉树转换成森林 直直观的的转换方法：方法： 1.1.在二叉在二叉树中，中，设B B是是A A的左孩子，的左孩子，则把把B B的右孩子，的右孩子，右孩子的右孩子，右孩子的右孩子，.，都与，都与A A用用线相相连； 2.2.去掉所有双去掉所有双亲到右孩子的到右孩子的连线 树、森林与二叉
46、树的关系树、森林与二叉树的关系 二叉树转换成森林二叉树转换成森林LKJIHEGFCBADFGHIKJLABDC二叉树转换成森林的形式定义 二叉树二叉树B(root,LB, RB) 森林森林F T1, T2, ., Tm (1) 若若B为空，则为空，则F为空为空 (2) 若若B非空，则非空，则F中中T1的根是的根是B的根；的根；T1的根的子树森林由的根的子树森林由B的左子树的左子树LB转换而成；转换而成；F中除第一棵树以外的剩余树由中除第一棵树以外的剩余树由B的右子树的右子树RB转换转换而成。而成。树、森林与二叉树的关系树、森林与二叉树的关系 二叉树换转成森林二叉树换转成森林6.4.1 树的存储
47、结构1. 双亲表示法双亲表示法2. 孩子表示法孩子表示法3. 带双亲的孩子链表带双亲的孩子链表4. 孩子兄弟表示法孩子兄弟表示法6.4.2 树、森林与二叉树的关系 1. 树转换成二叉树树转换成二叉树 2. 森林转换成二叉树森林转换成二叉树 3. 二叉树转换成森林二叉树转换成森林 6.4.3 树和森林的遍历6.4 树和森林6.4.3 树和森林的遍历1. 先序遍历树： 若树不空，则(1)访问根； (2)从左至右先序遍历根的各个子树。2. 后序遍历树： 若树不空，则(1)从左至右后序遍历根的各个子树。 (2)访问根。树和森林树和森林 树和森林的遍历树和森林的遍历AFEDCBIHGKJAKJDCBIH
48、GFE先根序列：ABEJFCDGHKI后根序列：JEFBCGKHIDA先序序列：ABEJFCDGHKI中序序列：JEFBCGKHIDA后序序列：JFEKIHGDCBA树和森林树和森林 树和森林的遍历树和森林的遍历树和森林树和森林 树和森林的遍历树和森林的遍历 先先序遍历树，等价于序遍历树，等价于先先序遍历由这棵树转换序遍历由这棵树转换而成的二叉树；而成的二叉树； 后后序遍历树，等价于序遍历树，等价于中中序遍历由这棵树转换序遍历由这棵树转换而成的二叉树；而成的二叉树；3. 先序遍历森林： 若森林不空，则 访问第一棵树的根结点； 先序遍历第一棵树根结点的子树森林； 先序遍历森林中去掉第一棵树后剩下
49、的树构成的森林4. 中序遍历森林： 若森林不空，则 中序遍历第一棵树根结点的子树森林； 访问第一棵树的根结点； 中序遍历森林中去掉第一棵树后剩下的树构成的森林树和森林树和森林 树和森林的遍历树和森林的遍历EFGHIKJLABDCLKJIHEGFCBAD先序序列：先序序列：ABDCEFGHIJLK后序序列：后序序列：DBCAEGFILJKH先序序列：先序序列：ABDCEFGHIJLK中序序列：中序序列：DBCAEGFILJKH后序序列：后序序列：DCBGLKJIHFEA树和森林树和森林 树和森林的遍历树和森林的遍历第六章 树和二叉树目录 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二
50、叉树和线索二叉树 6.4 树和森林 6.5 哈夫曼树及其应用 6.5 哈夫曼树及其应用 6.5.1 哈夫曼树的定义 6.5.2 哈夫曼树的构造 6.5.3 哈夫曼编码哈夫曼树及其应用哈夫曼树及其应用6.5.1 哈夫曼树的定义路径：从一个结点到另一个结点所经过的分支路径长度L：路径上分支的数目树的路径长度PL：根到每个结点的路径长度之和 n结点个数EFDCBAEFCBADh=3, PL=0+1+1+2+2+2=8h=5, PL=0+1+2 +3+4+4=13哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树的定义哈夫曼树的定义 树的带权路径长度WPL：树中所有叶子叶子带权路径长度之和n树叶个数 哈夫曼树
51、：由权值为 w1,w2,.,wn)的n片叶子构成的所 有二叉树中，WPL值最小的二叉树。 哈夫曼树又被称为最优二叉树 结点的带权路径长度：结点的权值乘结点到根的路径长度wili哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树的定义哈夫曼树的定义CBAD 7 5 2 4ADCBWPL=71+52+23+43=35ABCDWPL=72+52+22+42=36BACDWPL=46CDABWPL=351.哈夫曼树不一定是最矮的树2. 哈夫曼树形态可能不唯一哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树的定义哈夫曼树的定义6.5 哈夫曼树及其应用 6.5.1 哈夫曼树的定义 6.5.2 哈夫曼树的构造 6.5.3
52、 哈夫曼编码哈夫曼树及其应用哈夫曼树及其应用6.4.2 哈夫曼树的构造 1952年，年，Huffman提出了一个构造最优二叉树提出了一个构造最优二叉树的一个精巧算法，被人们称为的一个精巧算法，被人们称为Huffman算法。算法。哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树的构造哈夫曼树的构造Huffman算法思想：1. 将权值为将权值为w w1 1, w, w2 2, ., w, ., wn n的的n n个叶子构成一个具有个叶子构成一个具有n n棵棵树的森林：树的森林：2. 从森林从森林F F中选取根权值最小的两棵树，分别作为左子中选取根权值最小的两棵树，分别作为左子树和右子树，再新添一个结点做
53、为根，合并成一棵新的树和右子树，再新添一个结点做为根，合并成一棵新的二叉树，新二叉树根的权值等于左、右子树根权值之和。二叉树，新二叉树根的权值等于左、右子树根权值之和。3. 重复重复2 2，直到，直到F F中只剩下一棵树为止，这棵树就是所求中只剩下一棵树为止，这棵树就是所求的的HuffmanHuffman树。树。w1w2w3wnF哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树的构造哈夫曼树的构造a6b1f4c5d4e2e2b13哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树的构造哈夫曼树的构造a6f4c5d4d4e2b13e2b137哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树的构造哈夫曼树的构造a6f
54、4c5d4e2b137c5f49哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树的构造哈夫曼树的构造a6a6d4e2b13713c5f49d4e2b137哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树的构造哈夫曼树的构造c5f49a613d4e2b13722a613d4e2b137c5f49哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树的构造哈夫曼树的构造c5f4922a613d4e2b137WPL=(1 + 2 )4 + 43 + (4 + 5 + 6)2=54哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树的构造哈夫曼树的构造8 构造n个叶子的哈夫曼树需要经过n-1次合并，每次合并都要增加一个新结点。所以n个
55、叶子的哈夫曼树上有且仅有2n-1个个结点8 哈夫曼树上不存在度为1的结点。我们把这种不存在度为1的结点的二叉树称为严格二叉树严格二叉树或正则正则二叉树二叉树。 n0=n2+1 n=n0 + n1 + n2 = n0 + n2 = n0 + (n0-1) = 2 * n0 - 1哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树的构造哈夫曼树的构造哈夫曼树的存储结构：weight parent lchildrchild0610-1-1117-1-1259-1-1348-1-1427-1-1549-1-16382577107489116391311181022-1910chars0a1b2c3d4e5fc
56、5f4922a613d4e2b1372n2哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树的构造哈夫曼树的构造huffman树的类型定义：树的类型定义：typedef struct unsigned int weight; int parent,lchild,rchild;HTNode;typedef struct HTNode *Htree; int root;HuffmanTree;哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树的构造哈夫曼树的构造在这种存储结构上设计Huffman算法：weight parent lchildrchild06-1-1-111-1-1-125-1-1-134-1-1-
57、142-1-1-154-1-1-16 -1-1-17-1-1-18-1-1-19-1-1-110-1-1-12n11.初始化2. 进行n1次合并：8在parent-1的结点中选权值最小的两个结点s1和s2；8填写s1和s2的双亲；8填写新结点的权和左、右孩子s1s2哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树的构造哈夫曼树的构造void Create_Huffman ( HuffmanTree &T, int *w, int n) / /构造哈夫曼树，数组构造哈夫曼树，数组w w存放权值，存放权值，n n是叶子数是叶子数 m=n*2-1; HT = T.Htree = new HTNodem;
58、/申请申请huffman数组数组 for(i=0;in;i+) HTi=wi,-1,-1,-1;/初始化初始化 for(i=n;im;i+) HTi=-1,-1,-1,-1; for(i=n;im;i+) select(HT,i-1,s1); /在在T.HTree0.i-1选选parent=-1的最小权值根的最小权值根 HTs1.parent=i; select(HT,i-1,s2); HTs2.parent=i ; HTi.weight = HTs1.weight + HTs2.weight; HTi.lchild=s1; HTi.rchild=s2; H.root=m-1; 6.5 哈夫曼
59、树及其应用 6.5.1 哈夫曼树的定义 6.5.2 哈夫曼树的构造 6.5.3 哈夫曼编码哈夫曼树及其应用哈夫曼树及其应用6.4.3 哈夫曼编码和解码 编码发送 ： 电文 0,1 序列 (比特流)接收： 0, 1序列 电文 解码例如： 电文“abcdedacafcfadcacfdaef” 字符集 a, b, c, d, e, f 字符出现次数 6, 1, 5, 4, 2, 4 哈夫曼树及其应用哈夫曼树及其应用 哈夫曼编码和解码哈夫曼编码和解码等长编码：000001010011100011000010000101010000.不等长编码：010001101101000011001100100.
60、电文“abcdedacafcfadcacfdaef” 字符集 a, b, c, d, e, f 编码方案：编码方案：abcdef串长特点等长编码00000101001110010166串长太大不等长编码010001101137有多义性前缀码1011000111011110056较好前缀码：任何字符的编码都不是其他字符编码的前缀前缀码：101100011101111110110011011.哈夫曼树及其应用哈夫曼树及其应用 哈夫曼编码和解码哈夫曼编码和解码 电文“abcdedacafcfadcacfdaef” 字符集 a, b, c, d, e, f 利用二叉树可以获得前缀码：利用二叉树可以获得
61、前缀码：以字符集中的字符为叶子，构造一棵二叉树; 在左树枝上标0码，右树枝上标1码。从树根到树叶所经历的分支构成了相应叶子字符的前缀码：cfadeb0100111001a: 10b: 1100c: 01d: 111e: 1101 f: 00哈夫曼树及其应用哈夫曼树及其应用 哈夫曼编码和解码哈夫曼编码和解码由于n个叶子能够构造出很多形态各异的二叉树，因而会有多种前缀码方案，取那种呢？当然是使得电文比特流为最短的编码方案。 cfadeb0100111001a: 10b: 1100c: 01d: 111e: 1101 f: 00哈夫曼树及其应用哈夫曼树及其应用 哈夫曼编码和解码哈夫曼编码和解码8显然
62、，如果ci是权，比特流长度就是二叉树的WPL。8哈夫曼树的WPL是最小的，故用哈夫曼树产生前缀码是最优前缀码最优前缀码，又称为哈夫曼编码哈夫曼编码。 n n字符个数字符个数cici字符在电文中重复出现次数字符在电文中重复出现次数lili串长，根到叶子的路径长度串长，根到叶子的路径长度哈夫曼树及其应用哈夫曼树及其应用 哈夫曼编码和解码哈夫曼编码和解码在哈夫曼树上获得前缀码的方法是：在哈夫曼树上获得前缀码的方法是： 先序遍历哈夫曼树先序遍历哈夫曼树, ,用一个栈保存遍历时用一个栈保存遍历时“采集采集”到的到的0 0码和码和1 1码：向左拐时码：向左拐时0 0进栈，向右拐时进栈，向右拐时1 1进栈。
63、遍历到树叶时进栈。遍历到树叶时将栈中保存的编码序列复制到将栈中保存的编码序列复制到HCHC中。回溯时做出栈操作。中。回溯时做出栈操作。cfadeb0100111001哈夫曼树及其应用哈夫曼树及其应用 哈夫曼编码和解码哈夫曼编码和解码f: 00c: 01a: 10b: 1100e: 1101d: 111void HuffmanCoding(HuffmanTree T,HuffmanCode &HC,int n) /先序遍历先序遍历huffman树树, 将每个字符的将每个字符的huffman编码存入编码存入HC /n是是huffman树的叶子结点数树的叶子结点数 InitStack(S);/初始化
64、一个空栈初始化一个空栈S，S中保留遍历时收集的中保留遍历时收集的0码和码和1码码 HC=new (char *)n; / coding(T, HT.root, S, HC); for(i=0;in;i+) printf(“%c: %sn”, charsi,HCi);哈夫曼树及其应用哈夫曼树及其应用 哈夫曼编码和解码哈夫曼编码和解码void Coding(HuffmanTree T, int i, SqStack &S,char *HC)/先序遍历先序遍历huffman树，获取每个字符的树，获取每个字符的huffman编码编码 if(T.Htreei.lchild=-1 & T.Htreei.r
65、child=-1) /i是树叶是树叶push(S, 0); /字符串结束标志字符串结束标志0进栈进栈 HCi=new charStackLength(S) strcpy(HCi, S.base); /复制叶子复制叶子i的的huffman码码 Pop(S, ch); /字符串结束标志字符串结束标志0出栈出栈 else Push(S,0); /向左转前向左转前0进栈进栈 coding(T, T.Htreei.lchild, HC); /遍历左子树遍历左子树 Pop(S, ch); /遍历空左子树时的遍历空左子树时的0出栈出栈Push(S,1); /向右转前向右转前1进栈进栈 coding(T, T
66、.Htreei.rchild, HC); /遍历右子树遍历右子树 Pop(S, ch); /遍历空右子树时的遍历空右子树时的1出栈出栈 pop(S,ch); /一棵子树遍历结束，出栈一棵子树遍历结束，出栈Huffman解码：将比特流还原成电文也是在哈夫曼树上实现的：8从左至右扫描比特流；从左至右扫描比特流；8自树根开始，逢自树根开始，逢0沿左链向下，逢沿左链向下，逢1沿右链向下，直沿右链向下，直到遇到到叶子；到遇到到叶子；8 还原叶子字符；还原叶子字符；8再回到树根；重复上述过程，直至比特流被扫描完。再回到树根；重复上述过程，直至比特流被扫描完。哈夫曼树及其应用哈夫曼树及其应用 哈夫曼编码和解
67、码哈夫曼编码和解码void Decoding(HuffmanTree T, char *bits, char *chars) /Huffman解码，解码，bits是比特流串，是比特流串，chars存放字符集字符存放字符集字符 char *p=bits; int i=T.root; while(*p!=0) if(*p=0)i=T.HTreei.lchild;/逢逢0左拐左拐 else i=T.HTreei.rchild;，/逢逢1右拐右拐 if(T.HTreei.lchild=-1) printf(“%c”, charsi); /打印叶子字符打印叶子字符 i=T.root; /回到树根回到树根
68、 /if p+; /while if(i!=T.root)printf(“Errorn”); 1、假设二叉树包含的结点数据为1，3，7，12。(1)画出两棵高度最大的二叉树；(2)画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。2、对给定的一组权值W（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。练习3、假设用于通信的电文由字符集a,b,c,d,e,f,g,h中的字母构成，这8个字母在电文中出现的概率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。(1)为这8个字母设计哈夫曼编码。(2)若用这三位二进制数(07)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少? 练习
