您好、欢迎来到现金彩票网!
当前位置:秒速快3 > 树图资料库 >

数据结构(C++描述)_树

发布时间:2019-07-17 07:32 来源:未知 编辑:admin

  数据结构(C++描述)_树_数学_自然科学_专业资料。第6章 树 数据结构(C++描述) 目录 6.1 树的基本概念 6.2 二叉树 6.3遍历二叉树 6.4线.1.1 树

  第6章 树 数据结构(C++描述) 目录 6.1 树的基本概念 6.2 二叉树 6.3遍历二叉树 6.4线.1.1 树的定义 1.树的定义 树是由n(n≥0)个结点组成的有限集合。若n=0,称为空 树;若n0,则: (1)有一个特定的称为根(root)的结点。它只有直接 后继,但没有直接前驱; (2)除根结点以外的其它结点可以划分为m(m≥0)个 互 不 相 交 的 有 限 集 合 T0 , T1 , … , Tm-1 , 每 个 集 合 Ti (i=0,1,…,m-1)又是一棵树,称为根的子树,每棵子树 的根结点有且仅有一个直接前驱,但可以有0个或多个直 接后继。 由此可知,树的定义是一个递归的定义,即树的定义中 又用到了树的概念。 树的结构参见图6-1。 B E F A C D GH I ? A J KL M (a)空树 (b)仅含有根结点的树 (c) 含有多个结点的树 图 6-1 树的示意图 在图6-1(c)中,树的根结点为A,该树还可以分为三个 互不相交子集T0,T1,T2,具体请参见图6-2,其中 T0={B,E,F,J,K,L},T1={C,G},T2={D,H, I,M},其中的T0,T1,T2都是树,称为图6-1(C) 中树的子树,而T0,T1,T2又可以分解成若干棵不相 交子树。如T0可以分解成T00,T01两个不相交子集, T00={E,J,K,L},T01={F},而T00又可以分为三个 不相交子集T000,T001,T002,其中,T000={J}, T001={K},T002={L}。 B C D E F J KL (a) T0 子树 G H I M (b)T1 子树 (c)T2 子树 图 6-2 图 6-1(C)的树的三个子树 2.树的逻辑结构描述 一棵树的逻辑结构可以用二元组描述为: tree =(k,R) k={ki∣1≤i≤n;n≥0,ki?elemtype} R={r} 其中,n为树中结点个数,若 n=0,则为一棵空树, n 0时称为一棵非空树,而关系 r 应满足下列条件: (1)有且仅有一个结点没有前驱,称该结点为树根; (2)除根结点以外,其余每个结点有且仅有一个直接前 驱; (3)树中每个结点可以有多个直接后继(孩子结点)。 例如,对图6-1(c )的树结构,可以二元组表示为: K={A,B,C,D,E,F,G,H,I,J,K,L,M} R={r} r={(A,B) , (A,C) , (A,D) , (B,E) , (B,F) , (C,G) , (D,H),(D,I),(E,J),(E,K),(E,L),(H,M)} 3.树的基本运算 树的基本运算可以定义如下几种: (1) inittree(&T) 初始化树T。 (2) root(T) 求树T的根结点。 (3) parent(T,x) 求树T中,值为x的结点的双亲。 (4) child(T,x,i) 求树T中,值为x的结点的第i个孩子。 (5) addchild(y,i,x) 把值为x的结点作为值为y的结点的第i个孩子插入到树 中。 (6) delchild(x,i) 删除值为x的结点的第i个孩子。 (7) traverse(T) 遍历或访问树T。 6.1.2 基本术语 1.结点 指树中的一个数据元素,一般用一个字母表示。 2.度 一个结点包含子树的数目,称为该结点的度。 3.树叶(叶子) 度为0的结点,称为叶子结点或树叶,也叫终端结 点。 4.孩子结点 若结点X有子树,则子树的根结点为X的孩子结点,也 称为孩子,儿子,子女等。如图6-1(c)中A的孩子为 B,C,D。 5.双亲结点 若结点X有子女Y,则X为Y的双亲结点。 6.祖先结点 从根结点到该结点所经过分枝上的所有结点为该结点的 祖先,如图6-1(c)中M的祖先有A,D ,H 。 7.子孙结点 某一结点的子女及子女的子女都为该结点子孙。 8.兄弟结点 具有同一个双亲的结点,称为兄弟结点。 9.分枝结点 除叶子结点外的所有结点,为分枝结点,也叫非终端 结点。 10.层数 根结点的层数为1,其它结点的层数为从根结点到该 结点所经过的分支数目再加1。 11. 树的高度(深度) 树中结点所处的最大层数称为树的高度,如空树的 高度为0,只有一个根结点的树高度为1。 12.树的度 树中结点度的最大值称为树的度。 13. 有序树 若一棵树中所有子树从左到右的排序是有顺序的,不 能颠倒次序。称该树为有序树。 14. 无序树 若一棵树中所有子树的次序无关紧要,则称为无序树。 15.森林(树林) 若干棵互不相交的树组成的集合为森林。一棵树可以 看成是一个特殊的森林。 6.1.3 树的表示 1.树形结构表示法 具体参 见图6-1 。 B E F A C D GH I ? A J KL M (a)空树 (b)仅含有根结点的树 (c) 含有多个结点的树 图 6-1 树的示意图 2. 凹入法表示法 具体参见图6-3 。 A B E J K L F C G D H M I 图 6-3 图 6-1(c)的树的凹入法表示 3. 嵌套集合表示法 具体参 见图6-4 。 A C BJ E K G F L I D HM 图 6-4 图 6-1(c)的树的集合表示 4.广义表表示法 对图6-1(c)的树结构,广义表表示法可表示为: (A(B(E(J,K,L),F),C(G),D(H (M),I))) 6.1.4 树的性质 性质1 树中的结点数等于所有结点的度加1。 证明:根据树的定义,在一棵树中,除根结点以外,每 个结点有且仅有一个直接前驱,也就是说,每个结点与 指向它的一个分支一一对应,所以,除根结点以外的结 点数等于所有结点的分支数(即度数),而根结点无直 接前驱,因此,树中的结点数等于所有结点的度数加1。 性质 2 度为k的树中第i层上最多有ki-1个结点(i≥1)。 下面用数学归纳法证明: 对于i=1,显然成立,假设对于i-1层,上述条件成立, 即第i-1层最多有ki-2个结点, 对于第i层,结点数最多为第i-1层结点数的k倍(因为 度为k),故第i层的结点数为ki-2*k= ki-1。 性质3 深度为h的 k叉树最多有 k h ?1 k ?1 个结点。 证明:由性质2可知,若每一层的结点数最多,则整 h 个 k 叉 树 结 点 数 最 多 , 共 有 ? k i?1 =k0+k1+…+kh- 1= k h ?1 。i ?1 当一k ?棵1K叉树上的结点数达到 树。 k h ?1 k ?1 时,称为满K叉 性质4 具有n个结点的k叉树的最小深度为?logk(n(k1)+1)?。 (请注意,?x? 表示取不小于x的最小整数,或叫做对x上 取整。) 证明:设具有n个结点的k叉树的深度为h,即在该树的前 面h-1层都是满的,即每一层的结点数等于ki-1个(1≤i≤h-1), 第h层(即最后一层)的结点数可能满,也可能不满,这 时,该树具有最小的深度。由性质3知道,结点数n应满 k hk??11?足1n下≤ 面条k,kh?件?通11:过转换为:kh-1n(k-1)+1≤kh,再取以k为底的 对数后,可以得到: h-1logk(n(k-1)+1)≤h , 即 有 : logk(n(k-1)+1)≤hlogk(n(k1)+1)+1,而h只能取整数,所以,该k叉树的最小深度为 h=?logk(n(k-1)+1)? 。 6.2 二叉树 6.2.1 二叉树的定义 1.二叉树的定义 和树结构定义类似,二叉树的定义也可以递归形式给 出: 二 叉 树 是 n ( n≥0 ) 个 结 点 的 有 限 集 , 它 或 者 是 空 集 (n=0),或者由一个根结点及两棵不相交的左子树和 右子树组成。 二叉树的特点是每个结点最多有两个孩子,或者说, 在二叉树中,不存在度大于2的结点,并且二叉树是有 序树(树为无序树),其子树的顺序不能颠倒,因此, 二叉树有五种不同的形态,参见图6-5 。 ? L R (a) (b) (c) (d) 图 6-5 二叉树的五种不同的形态 L R (e) 2.二叉树的基本运算 (1)inittree(&T) 二叉树的初始化。 (2)root(T) 求二叉树的根结点。 (3)parent(T,x) 求二叉树T中值为x的结点的双亲。 (4)lchild(T,x) 求二叉树T中值为x的结点的左孩子。 (5) rchild(T,x) 求二叉树T中值为x的结点的右孩子。 (6) lbrother(T,x) 求二叉树T中值为x的结点的左兄弟。 (7) rbrother(T,x) 求二叉树T中值为x的结点的右兄弟。 (8) traverse(T) 遍历二叉树T。 (9) createtree(&T) 建立一棵二叉树T。 (10) addlchild(&T,x,y) 在二叉树T中,将值为y的结点作为值为x的结点的左 孩子插入。 (11) addrchild(&T,x,y) 在二叉树T中,将值为y的结点作为值为x的结点的 右孩子插入。 (12) dellchild(&T,x) 在二叉树T中,删除值为x 的结点的左孩子。 (13) delrchild(&t,x) 在二叉树T中,删除值为x 的结点的右孩子。 6.2.2 二叉树的性质 性质1 若二叉树的层数从1开始,则二叉树的第k层结点 数,最多为2k-1个(k0)。 可以用数学归纳法证明之。 性质2 深度(高度)为k的二叉树最大结点数为2k-1 (k0)。 证明: 深度为k的二叉树,若要求结点数最多,则必 须每一层的结点数都为最多,由性质1可知,最大结 点数应为每一层最大结点数之和。既为 20+21+…+2k1=2k-1。 性质3 对任意一棵二叉树,如果叶子结点个数为n0, 度为2的结点个数为n2,则有n0=n2+1。 证明:设二叉树中度为1的结点个数为n1,根据二叉树 的定义可知,该二叉树的结点数n=n0+n1+n2。又因为 在二叉树中,度为0的结点没有孩子,度为1的结点有1 个孩子,度为2的结点有2个结孩子,故该二叉树的孩 子结点数为 n0*0+n1*1+n2*2 ,而一棵二叉树中,除根 结点外所有都为孩子 结点,故该二叉树的结点数应为 孩子结点数加1即:n=n0*0+n1*1+n2*2+1因此,有 n=n0+n1+n2=n0*0+n2*1+n2*2+1,最后得到n0=n2+1。 为继续给出二叉树的其它性质,先定义两种特殊的二叉 树。 满二叉树 深度为k具有2-k-1个结点的二叉树,称为满 二叉树。 从上面满二叉树定义可知,必须是二叉树的每一层上 的结点数都达到最大,否则就不是满二叉树。 完全二叉树 如果一棵具有n个结点的深度为k的二叉树, 它的每一个结点都与深度为k的满二叉树中编号为1~ n 的结点一一对应,则称这棵二叉树为完全二叉树。 从完全二叉树定义可知,结点的排列顺序遵循从上到下、 从左到右的规律。所谓从上到下,表示本层结点数达到 最大后,才能放入下一层。从左到右,表示同一层结点 必须按从左到右排列,若左边空一个位置时不能将结点 放入右边。 从满二叉树及完全二叉树定义还可以知道,满二叉树 一定是一棵完全二叉树,反之完全二叉树不一定是一 棵满二叉树。满二叉树的叶子结点全部在最底层,而 完全二叉树的叶子结点可以分布在最下面两层。深度 为4的满二叉树和完全二叉树如图6-6所示。 A B C A B C D E F G D EF G HI J KL M N O H (a)满二叉树 (b)完全二叉树 图 6-6 满二叉树和完全二叉树示意图 性质4 具有n个结点的完全二叉树高度为?log2(n)?+1 或 ?log2(n+1)? 。 (注意?x?表示取不大于x的最大整数,也叫做对x下 取整,?x?表示取不小于x的最小整数,也叫做对x上 取整。) 证明:设该完全二叉树高度为k,则该二叉树的前面k-1 层为满二叉树,共有2k-1-1个结点,而该二叉具有k层, 第k层至少至少有1个结点,最多有2k-1个结点。因此有下 面的不等式成立:-----(2k-1 –1) +1 ≤n ≤(2k-1-1)+2k-1, 即有 2k-1≤n≤2k-1。由式子后半部分可知, n≤2k-1…① 由式 子前半部分可知 2k-1≤n…② 由①有 n+1≤2k ,同时取对数得: log2(n+1)≤k 故 k≥log2(n+1),即 k=?log2(n+1)?。即得到第二个结论。 由②有2k-1≤n,同时取对数得:k≤log2n+1即 k=?log2 n?+1, 即第一个结论成立,证毕。 性质5如果将一棵有n个结点的完全二叉树从上到下, 从左到右对结点编号1,2,…,n,然后按此编号将 该二叉树中各结点顺序地存放于一个一维数组中, 并简称编号为j的结点为 j(1≤j≤n),则有如下结论成立: (1)若 j=1,则结点j为根结点,无双亲,否则j的双 亲为 ?j/2?; (2)若2j≤n,则结点j的左子女为2j ,否则无左子女。 即满足2jn的结点为叶子结点; (3)若2j+1≤n,则结点j的右子女为2j+1,否则无右 子女; (4)若结点j序号为奇数且不等于1,则它的左兄弟为 j-1; (5)若结点j序号为偶数且不等于n,它的右兄弟为 j+1; (6) 结点j所在层数(层次)为?log2j?+1; 6.2.3 二叉树的存贮结构 1.顺序存贮结构 将一棵二叉树按完全二叉树顺序存放到一个一维数组 中,若该二叉树为非完全二叉树,则必须将相应位置 空出来,使存放的结果符合完全二叉树形状。如图6-7 给出了顺序存贮形式。 A B C D EF G 01 2 34 5 6 A B C D 012 34 56 789 A B C D E FG AB C D ... (a)完全二叉树的存储形式 (b)非完全二叉树的存储形式 图 6-7 二叉树的顺序存储形式 对于一棵二叉树,若采用顺序存贮时,当它为完全二叉 树时,比较方便,若为非完全二叉树,将会浪费大量存贮 存贮单元。最坏的非完全二叉树是全部只有右分支,设 高度为K,则需占用2K-1个存贮单元,而实际只有k个元 素,实际只需k个存储单元。因此,对于非完全二叉树, 宜采用下面的链式存储结构。 2.二叉链表存贮结构 (1)二叉链表表示 将一个结点分成三部分,一部分存放结点本身信息,另外 两部分为指针,分别存放左、右孩子的地址。 二叉链表中一个结点可描述为: 1child data rchild 对于图6-7所示二叉树,用二叉链表形式描述见图6-8。 root A root A^ B C ^B ^ D^ ^ E^ ^ F^ ^ G^ C^ ^ D^ (a)完全二叉树的链表 (b)非完全二叉树的二叉链表 图 6-8 二叉树的二叉链表表示法 对于一棵二叉树,若采用二叉链表存贮时,当二叉树为 非完全二叉树时,比较方便,若为完全二叉树时,将会占 用较多存贮单元(存放地址的指针)。若一棵二叉树有n 个结点,采用二叉链表作存贮结构时,共有2n个指针域, 其中只有n-1个指针指向左右孩子,其余n+1个指针为空, 没有发挥作用,被白白浪费掉了,(当然后面介绍的线)二叉链表的数据类型 二叉链表的数据类型描述如下: struct bitree { elemtype data ; //结点数据类型 bitree *lchild, *rchild;} //定义左、右孩子为指针型 (3)二叉链表的建立 为了后面遍历二叉树方便,先介绍建立二叉链表的算 法(假设elemtype 为char型)。 假设二叉链表的数据类型描述如刚才所述,为建立二叉 链表,用一个一维表数组来模拟队列,存放输入的结点, 但是,输入结点时,必须按完全二叉树形式,才能使结 点间满足性质5,若为非完全二叉树,则必须给定一些 假想结点(虚结点),使之符合完全二叉树形式。为此, 我们在输入结点值时,存在的结点则输入它对应的字符, 不存在的结点(虚结点),输入逗号,最后以一个特殊符 号 “#”作为输入的结束,表示建二叉链表已完成。建成 的二叉链表可以由根指针root唯一确定。 算法描述如下: #includeiostream.h typedef char elemtype; struct bitree { elemtype data; bitree *lchild,*rchild;}; bitree *create() { bitree *q[100]; //定义q数组作为队列存放二叉链表中 结点,100为最大容量 bitree *s; //二叉链表中的结点 bitree *root ; //二叉链表的根指针 int front=1,rear=0; //定义队列的头、尾指针 char ch; //结点的data域值 root=NULL; cinch; while(ch!=#) //输入值为#号,算法结束 { s=NULL; if(ch!=,) 否则为虚结点 //输入数据不为逗号,表示不为虚结点, { s=new bitree; s-data=ch; s-lchild=NULL; s-rchild=NULL; } rear++; q[rear]=s; //新结点或虚结点进队 if(rear==1) root=s; else { if((s!=NULL)&&(q[front]!=NULL)) { if(rear%2==0) q[front]-lchild=s; //rear为偶数,s为双亲左孩子 else q[front]-rchild=s;} 数,s为双亲右孩子 //rear为奇 if(rear%2==1) front++; } //出队 cinch;} return root; } 例如,对图6-9所示的二叉树,建立的二叉链表如 图6-10所示。 A B C A B C D (a)非完全二叉树 D (b)增加虚结点后假想为完全二叉树 图 6-9 一棵非完全二叉树假想为完全二叉树 (a)非完全二叉树 (b)增加虚结点后假想 root A^ ^B ^ C^ ^ D^ 图 6-10 用上述算法建成的二叉链表 对图6-9(a)所示的二叉树,要用算法建成图6-10所 示的二叉树链表,从键盘输入的数据应为: AB,,C,,,,D#↙ 其中#为输入结束,↙为回车符。 6.3遍历二叉树 所谓遍历二叉树,就是遵从某种次序,访问二叉树中 的所有结点,使得每个结点仅被访问一次。 这里提到的“访问”是指对结点施行某种操作,操作 可以是输出结点信息,修改结点的数据值等,但要求 这种访问不破坏它原来的数据结构。在本书中,我们 规定访问是输出结点信息data,且以二叉链表作为二 叉树的存贮结构。 由于二叉树是一种非线性结构,每个结点可能有一 个以上的直接后继,因此,必须规定遍历的规则,并 按此规则遍历二叉树,最后得到二叉树所有结点的一 个线性序列。 令L,R,D分别代表二叉树的左子树、右子树、根结点, 则遍历二叉树有6种规则:DLR、DRL、LDR、LRD、 RDL、RKD。若规定二叉树中必须先左后右(左右顺 序不能颠倒),则只有DLR、LDR、LRD三种遍历规 则。DLR称为前根遍历(或前序遍历、先序遍历、先 根遍历),LDR称为中根遍历(或中序遍历),LRD称 为后根遍历(或后序遍历)。 6.3.1前根遍历 所谓前根遍历,就是根结点最先遍历,其次左子树, 最后右子树。 1.递归遍历 前根遍历二叉树的递归遍历算法描述为: 若二叉树为空,则算法结束;否则 (1)输出根结点; (2)前根遍历左子树; (3)前根遍历右子树; 算法如下: void preorder(bitree *root) { bitree *p; p=root; if(p!=NULL) {coutp-data“ ”; preorder(p-lchild); preorder (p-rchild);} } 2.非递归遍历 利用一个一维数组作为栈,来存储二叉链表中结点, 算法思想为: 从二叉树根结点开始,沿左子树一直走到末端(左孩子 为空)为止,在走的过程中,访问所遇结点,并依次把 所遇结点进栈,当左子树为空时,从栈顶退出某结点, 并将指针指向该结点的右孩子。如此重复,直到栈为 空或指针为空止。 算法如下: void preorder1(bitree *root) { bitree *p,*s[100]; int top=0; //top为栈顶指针 p=root; while((p!=NULL)(top0)) { while(p!=NULL) {coutp-data ; s[++top]=p; p=p-lchild; } p=s[top--]; p=p-rchild; }} 6.3.2中根遍历 所谓中根遍历,就是根在中间,先左子树,然后根结 点,最后右子树。 1.递归遍历 中根遍历二叉树的递归遍历算法描述为: 若二叉树为空,则算法结束;否则 ⑴中根遍历左子树; ⑵输出根结点; ⑶中根遍历右子树。 算法如下: void inorder(biteee *root) { bitree *p; p=root; if (p!=NULL) { inorder(p-lchild); coutp-data“ ”; inorder(p-rchild); } } 2.非递归遍历 同样利用一个一维数组作栈,来存贮二叉链表中结点, 算法思想为: 从二叉树根结点开始,沿左子树一直走到末端(左孩子为 空)为止,在走的过程中,把依次遇到的结点进栈,待左 子树为空时,从栈中退出结点并访问,然后再转向它的右 子树。如此重复,直到栈空或指针为空止。 算法如下: void inorder1( bitree *root) { bitree *p,*s[100]; //s为一个栈,top为栈顶指针 int top=0; p=root; while((p!=NULL)(top0)) { while(p!=NULL) {s[++top]=p;p=p-lchild;} {p=s[top--]; coutp-data ; p=p-rchild; } }} 6.3.3 后根遍历 所谓后根遍历,就是根在最后,即先左子树,然后右 子树,最后根结点。 1.递归遍历 后根遍历二叉树的递归遍历算法描述为: 若二叉树为空,则算法结束;否则 (1)后根遍历左子树: (2)后根遍历历子树; (3)访问根结点。 算法如下: void postorder( bitree *root) { bitree *p; p=root; if (p!=NULL) { postorder (p-lchild); postorder (p-rchild); coutp-data“ ”; } } 2.非递归遍历 利用栈来实现二叉树的后序遍历要比前序和中序遍历复 杂得多,在后序遍历中,当搜索指针指向某一个结点时, 不能马上进行访问,而先要遍历左子树,所以此结点应 先进栈保存,当遍历完它的左子树后,再次回到该结点, 还不能访问它,还需先遍历其右子树,所以该 结点还必 须再次进栈,只有等它的右子树遍历完后,再次退栈时, 才能访问该结点。为了区分同一结点的两次进栈,引入 一个栈次数的标志,一个元素第一次进栈标志为0,第 二次进标志为1,并将标志存入另一个栈中,当从标志 栈中退出的元素为1时,访问结点。 后序遍历二叉树的非递归算法如下: void postorder1( bitree *root) { bitree *p,*s1[100]; //s1栈存放树中结点 int s2[100],top=0,b; //s2栈存放进栈标志 p=root; do { while(p!=NULL) {s1[top]=p;s2[top++]=0; //第一次进栈标志为0 p=p-lchild;} if(top0) {b=s2[--top]; p=s1[top]; if(b==0) {s1[top]=p;s2[top++]=1; //第二次进栈标志为0 p=p-rchild;} else {coutp-data ; p=NULL; } } }while(top0); } 例如,可以利用上面介绍的遍历算法,写出如图6-11 所示二叉树的三种遍历序列为: 先序遍历序列:ABDGCEFH 中序遍历序列: BGDAECFH 后序遍历序列: GDBEHFCA A B C DEF G H 图 6-11 一棵二叉树 另外,在编译原理中,有用二叉 树来表示一个算术表 达式的情形。在一棵二叉树中,若用操作数代表树叶, 运算符代表非叶子结点,则这样的树可以代表一个算 术表达式。若按前序、中序、后序对该二叉树进行遍 历,则得到的遍历序列分别称为前缀表达式(或称波兰 式)、中缀表达式、后缀表达式(递波兰式)。具体参见 图6-12。 图 6-12 所 对 应 的 前 缀 表 达 式:-*abc。 图 6-12 所 对 应 的 中 缀 表 达 式:a*b-c。 图6-12所对应的后缀 表达式:ab*c-。 - * c a b 图 6-12 表达式 a*b-c 代表的二叉树 二叉树所对应的遍历序列可以通过递归算法得到,也 可以通过非递归算法得到。但有时要求直接写出序列, 故我们可以用图6-13所示得到图6-12的遍历序列。从二 叉树的三种递归遍历算法可以知道,三种遍历算法不 同之处在于访问根结点和遍历左、右子树的顺序不同, 若递归算法中去掉与递归无关的语句——访问根结点, 则三个遍历算法完全相同。于是对于二叉树的遍历, 可以看成是从根结点出发,往左子树走,若左子树为 空,返回,再进入右子树,右子树访问完后,再返回 根结点。这样一来每个结点都被访问三次,若将按顺 序第一次访问的结点排列起来,则得到该二叉树的先 序序列,第二次访问的结点排列起来,则得到该二叉 树的中序序列,第三次访问的结点排列起来,则得到 该二叉树的后序序列。对于图6-13中, 第一次访问到 的结点用△表示,第二次访问到的结点用○表示,第三次 访问的结点用□表示,按虚线顺序将所有△排列,则得到 先序序列为-*abc,将所有○排列起来则得到中序序列为 a*b-c,将所有□排列起来则得到后序序列ab*c-。 1 2 * ^c ^ ^ a^ ^b ^ 6.3.4遍历算法应用举例 例6-5 由二叉树的前序序列和中序序列建立该二叉树 分析:若二叉树的任意两个结点的值都不相同,则二 叉树的前序序列和中序序列能唯一确定一棵二叉树。 另外,由前序序列和中序序列的定义可知,前序序列 中第一个结点必为根结点,而在中序序列中,根结点 刚好是左、右子树的分界点,因此,可按如下方法建 立二叉树: 1.用前序序列的第一个结点作为根结点; 2.在中序序列中查找根结点的位置,并以此为界将 中序序列划分为左、右两个序列(左、右子树); 3.根据左、右子树的中序序列中的结点个数,将前序 序列去掉根结点后的序列划分为左、右两个序列,它 们分别是左、右子树的前序序列; 4.对左、右子树的前序序列和中序序列递归地实施同 样方法,直到所得左、右子树为空。 假设前序序列为ABDGHCEFI,中序序列为GDHBAECIF, 则得到的二叉树如下页所示 1。A为根结点 A BDGH CEFI GDHB A ECIF A BD CE GH FI 2. B为左子树的根结点 B DGH GDH B 3. D为左子树的左子树的根 结点 A B CE DH G FI B D A CE FI G H 4。C为右子树的根结点 C E FI E C IF B D A C E FI G H 5。F为右子树的右 子树的根结点 A B C D E F G H I 例6-6 按层次遍历一棵二叉树 对于一棵二叉树,若规定遍历顺序为从上到下(上层遍历 完才进入下层),从左到右(同一层从左到右进行,这样 的遍历称为按层次遍历:例6-5的树的层次遍历序列为: ABCDEFGHI。下面用一个一维数组来模拟队列,实现 二叉树的层次遍历。 Void lorder (bitree * t) { bitree *q[maxsize],*p; // maxsize为最大容量 int f,r; // f,r类似于头尾指针 q[1]=t; f=r=1; while (f=r) { p=q[f]; f++; //出队 cout p-data; if(p -lchild!=NULL) { r++; q[r]=p-1child; } //入队 if (p-rchild!=NULL) { r++; q[r]=p-rchild;} //入队 }} 6.4线 线索的概念 通过前面介绍的二叉树可知,遍历二叉树实际上就是将 树中所有结点排成一个线性序列(即非线性结构线性化), 在这样的线性序列中,很容易求得某个结点在某种遍历 下的直接前驱和后继。然而,有时我们希望不进行遍历 就能快速找到某个结点在某种遍历下的直接前驱和后继, 这样,就应该把每个结点的直接前驱和直接后继记录下 来。为了做到这一点,可以在原来的二叉链表结点中, 再增加两个指针域,一个指向前驱,一个指向后继,但 这样做将会浪费大量存贮单元,存贮空间的利用率相当 低(一个结点中有4个指针,1个指左孩子,1个指右孩子, 1个指前驱,1个指后继),而原来的左、右孩子域有许多 空指针又没有利用起来。为了不浪费存存贮空间,我们 利用原有的孩子指针为空时来存放直接前驱和后继,这 样的指针称为“线索”,加线索的过程称为线索化,加 了线索的二叉树,称为线索二叉树,对应的二叉链表称 为线索二叉链表。 在线索二叉树中,由于有了线索,无需遍历二叉树就 可以得到任一结点在某种遍历下的直接前驱和后继。 但是,我们怎样来区分孩子指针域中存放的是左、右 孩子信息还是直接前驱或直接后继信息呢?为此,在二 叉链表结点中,还必须增加两个标志域ltag、rtag。 ltag和rtag定义如下: 0 lchild域指向结点的左孩子 ltag= 1 接前驱 lchild域指向结点在某种遍历下的直 0 rchild域指向结点的右孩子 rtag= 1 rchild域指向结点在某种遍历下的直接后继 这样,二叉链表中每个结点还是有5个域,但其中只 有2个指针,较原来的4个指针要方便。增加线索后的 二叉链表结点结构可描述如下: lchild ltag data rtag rchild 2.线索的分类 另外,根据遍历的不同要求,线索二叉树可以分为: (1)前序前驱线索二叉树(只需画出前驱) (2)前序后继线索二叉树(只需画出后继) (3)前序线索二叉树(前驱和后继都要标出) (4)中序前驱线索二叉树(只需画出前驱) (5)中序后继线索二叉树(只需画出中序后继) (6)中序线索二叉树(中序前驱和后继都要标出) (7)后序前驱线索二叉树(只需画出后序前驱) (8)后序后继线索二叉树(中需画出后序后驱) (9)后序线索二叉树(后前驱和后继都要标出) 6.4.2线.结点数据类型描述 struct Hbitree { elemtype data; int ltag ,rtag; //左、右标志域 Hbitree *lchild, *rchild; } ; 2.线索的画法 在二叉树或二叉链表中,若左孩子为空,则画出它 的直接前驱,右孩子为空时,则画出它的直接后继, 左右孩子不为空时,不需画前驱和后继。这样就得 到了线索二叉树或线索二叉链表。 A BC D (a) 二叉树 A B C D NULL (b)前序线 ^ (c)前序线 前序线索示意图 前序序列为:ABCD NULL A NULL root 0A 0 B C D (a)中序二叉树 图 6-16 中序序列为:BADC ^ 1B 1 0C 1 ^ 1D 1 (b) 中序线索二叉链表 中序线索示意图 NULL A B C D root 0A 0 ^ 1B 1 0C 1 1D 1 (a)后序线索二叉树 (b)后序线 后序线索示意图 后序序列为:BDCA 6.4.3 线索的算法实现 在此,仅介绍中序线索二叉树的算法实现,设为P为 当前结点,pre为p的前驱结点,算法描述如下: void inth (Hbitree *p) //将P所指二叉树中序线索化,调用该函数之前,pre为 Null,而树中所有结点的ltag和rtag都为0。 { if (p!=NULL) { inth (p-lchild); 左子树线索化 if (p-lchild==NULLl) p-ltag=1; if (p-rchild==NULL) p-rtag; if (pre!=NULL) { if(pre-rtag==1) pre-rchild=p; if (p-ltag=1) p-lchild=pre; } pre=p; inth (p-rchild); //右子树线 线.线)查找指定结点在中序线索二叉树中的的直接后继 若所找结点右标志rtag=1,则右孩子域指向中序后继, 否则,中序后继应为遍历右子树时的第一个访问结点, 即右子树中最左下的结点(参见图 6-19)。从图6-19 中可知,x的后继为xk 。 P P X X0 0 x1 X1 0 x2 X2 1 xk XK 图 6-19 求中序后继示意图 (2)查找指定结点在中序线索二叉树中的的直接前 驱 若所找结点左标志ltag=1,则左孩子域指向中序前驱, 否则,中序前驱应为遍历左子树时的最后一个访问结 点,即左子树中最右下的结点(参见图 6-20)。从图 6-20中可知,x的前驱为xk 。 P X P 0X X1 X2 x1 0 x2 0 xk xk 1 图 6-20 求中序前驱示意图 (3) 查找指定点在前序线索二叉树中的直接后继 前序后继的查找比较方便,若P无左孩子,右链为 后继,否则左孩子为后继。 (4) 查找指定结点在后序线索二叉树中的直接前驱 后序前驱的查找也比较方便,若左孩子为空,左链指 前驱,否则,若右子树为空,左孩子指前驱,否则右 孩子为前驱。 求后序后继和前序前驱都比较麻烦,在此不再作进一步 介绍。 2.线索二叉树上的遍历 遍历某种次序的线索二叉树,只要从该次序下的开始 结点出发,反复找到结点在该次序下的后继,直到后 继为空。这对于中序线索和前序线索二叉树很方便, 但对于后序线索二叉树较麻烦(因求后序后继较麻烦)。 故后序线索对于遍历没有什么意义。 (1)前序遍历线索二叉树算法 void preorder2 (Hbitree *t) Hbitree *p; { p=t; //找到开始结点 while (p!=NULL) { cout p-data; p=preordernext(p); //调查函数找前序后继 }} (2)中序遍历线索二叉树算法 void inorder2 (Hbitree *t) { Hbitree *p;p=t; if (p!=NULL) { while (p-ltag==0) p=p-lchild; //找开始结点 while (p!=NULL) { cout p-data; p= inordernext(p); //调用函数找中序后继 }}} 从上面算法可知,线索二叉树上的遍历较一般二叉树 要方便得多。但是这种方便是以增加线索为代价的, 增加线索本身要花费大量时间。所以二叉树是以二链 表表示,还是以线索二叉链表示,可根据具体问题而 定。 3.线索二叉树的扦入和删除 线索二树上的查找、遍历都较一般二叉树方便,但线 索二叉树也存在其缺点,就扦入和删除运算而言,线 索二叉树比一般二叉树的时间花费大,因为除修改指 针外,还要修改相应线索。 线索二叉树的扦入和删除较麻烦,因此本书不再介绍 算法 6.5树和森林 6.5.1 树的存储结构 1.双亲表示 它是以一组连续的存储单元来存放树中的结点,每个结 点有两个域:一个是data域,存放结点信息,另一个是 parent域,用来存放双亲的位置(指针)。 该结构的具体描述见图6-21。 A BC E FG D H (a)树的结构 a[0] a[1] a[7] a[maxsine-1] data A B C D E F G H … parent -1 0 0 0 1 2 2 3 … (b)树的双亲表示法 图 6-21 树的双亲表示示意图 2.孩子表示法 将一个结点所有孩子链接成一个单链表形,而树中有 若干个结点,故有若干个单链表,每个单链表有一个 表头结点,所有表头结点用一个数组来描述,具体描 述参见图6-22 a[1] A a[2] B a[3] C D E^ F^ G^ a[7] H^ … … 1 2 3^ 4^ 5 6^ 7^ a[maxsize-1] 图 6-22 树的孩子表示法(图 6-21(a)中树)示意图 3.双亲孩子表示法 将第1、2两种方法结合起来,则得到双亲孩子表示法, 具体参见图6-23。 A -1 B0 C0 D0 E1 ^ F2 ^ G2 ^ H3 ^ 1 2 3^ 4^ 5 6^ 7^ 图 6-23 树的双亲孩子表示法示意图 4 。孩子兄弟表示法 类似于二叉链表,但第一根链指向第一个孩子,第二 根链指向下一个兄弟。将图6-21(a)的树用孩子兄弟表 示法表示,见图6-24。 A^ B ^ ^E ^ C ^F D^ ^G ^ ^H ^ 图 6-24 树的孩子兄弟表示法示意图 6.5.2 树、森林和二叉树的转换 1.树转换成二叉树 可以分为三步: (1) 连线 指相邻兄弟之间连线) 抹线 指抹掉双亲与除左孩子外其它孩子之间的连线) 旋转 只需将树作适当的旋转。 具体实现过程见图6-25。 A B C A 连线抹线 D 旋转 B C D E F G E F G 图 6-25 树转换成二叉树示意图 A B C E D F G 2.森林转换成二叉树 (1) 将森林中每一棵树分别转换成二叉树 这在刚才的树转换成二叉树中已经介绍过。 (2)合并 使第n棵树接入到第n-1棵的右边并成为它的右子树,第 n1 棵二叉树接入到第n-2 棵的右边并成为它的右子树,…, 第2棵二叉树接入到第1棵的右边并成为它的右子树,直到 最后剩下一棵二叉树为止。 A E B CD F A B C D E F 合并 G H I A A A G H I A B E CF D G H I 图 6-26 森林转换成二叉树示意图 3.二叉树还原成树或森林 (1) 右链断开 将二叉树的根结点的右链及右链的右链等全部断开,得到 若干棵无右子树的二叉树。 具体操作见图6-27(b)。 (2) 二叉树还原成树 将(1)中得到的每一棵二叉树都还原成树(与树转换 成二叉树的步骤刚好相反)。 具体操作步骤见图6-27(c)。 A B F E C G H I D J K (a)一个森林得到的二叉树 A F H B J G C E A F B G E C H I J K D (b)断开根的右链得到 4 棵无右子树的二叉树 I A F H I J K K B C D G D (c) 四棵二叉树还原成四棵树 E (d) 二叉树还原成森林 图 6-27 二叉树还原成森林过程 6.5.3 树和森林的遍历 在树和森林中,一个结点可能有两棵以上的子树,所 以不宜讨论它们的中序遍历, 即树和森林只有先序遍 历和后序遍历。 1.先序遍历 (1)树的先序遍历 若树非空,则先访问根结点,然后依次先序遍历各子树。 (2)森林的先序遍历 若森林非空,则先访问森林中第一棵树的根结点,再先 序遍历第一棵树各子树,接着先序遍历第二棵树、第三 棵树、…、直到最后一棵树。 2.后序遍历 (1)树的后序遍历 若树非空,则依次后序遍历各子树,最后访问根结点。 (2)森林的后序遍历 按顺序后序遍历森林中的每一棵树。 另外,请注意,树和森林的先序遍历等价于它转换成的 二叉树的先序遍历,树和森林的后序遍历等价于它转换 成的二叉树的中序遍历。 6.6 哈夫曼树 6.6.1基本术语 1.路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或子孙结 点之间的通路,称为路径。通路中分支的数目称为路径 长度。 若规定根结点的层数为1,则从根结点到第L层结点的路 径长度为L-1。 2.结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值,则这个数 值称为该结点的权。 结点的带权路径长度为:从根结点到该结点之间的路径 长度与该结点的权的乘积。 3.树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长 度之和,记为wpl= n ? wi l,i 其中n 为叶子结点数目,wi 为第i 个叶子结点的权i?1值,li 为第i 个叶子结点的路径 长度。 6.6.2 哈夫曼树构造 1.哈夫曼树的定义 在一棵二叉树中,若带权路径长度达到最小,称这 样的二叉树为最优二叉树,也称为哈夫曼树 (Huffman tree)。 例如,给定叶子结点的权分别为1,3,5,7,则可以得到如 图6-28所示的不同二叉树。 从图6-28可知,图6-28 (b)的长度最短,图6-28 (c)为较差 情形,当然读者还可以自已构造出具有不同的wpl情形来。 7 5 5 3 1 35 7 (a) wpl=32 1 3 (b) wpl=29 1 7 (c) wpl=35 图 6-28 具有不同带 权路径长度的二叉树 2.哈夫曼树的构造 假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1,w2,…,wn,则哈夫曼树的构造规则为: (1) 将w1,w2,…,wn看成是有n 棵树的森林(每棵树仅有一 个结点); (2) 在森林中选出两个根结点的权值最小的树合并,作 为一棵新树的左、右子树,且新树的根结点权值为其左、 右子树根结点权值之和; (3)从森林中删除选取的两棵树,并将新树加入森林; (4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树 即为我们所求得的哈夫曼树。 下面给出哈夫曼树的构造过程,假设给定的叶子结点的 权分别为1,5,7,3,则构造哈夫曼树过程如图6-29所示。 从图6-29可知,n 个权值构造哈夫曼树需n-1次合并,每 次合并,森林中的树数目减1,最后森林中只剩下一棵树, 即为我们求得的哈夫曼树。 1 5 7 3 (a) 初如森林 5 7 4 1 3 (b) 一次合并后的森林 7 9 4 5 16 7 9 1 3 4 5 1 3 (c) 二次合并后的森林 (d) 三合并后的森林 图 6-29 哈夫曼树的构造过程 6.6.3哈夫曼树的应用 1.哈夫曼编码 通信中,可以采用0,1的不同排列来表示不同的字符,称 为二进制编码。而哈夫曼树在数据编码中的应用,是数据 的最小冗余编码问题,它是数据压缩学的基础。若每个字 符出现的频率相同,则可以采用等长的二进制编码,若频 率不同,则可以采用不等长的二进编码,频率较大的采用 位数较少的编码,频率较小的字符采用位数较多的编码, 这样可以使字符的整体编码长度最小,这就是最小冗余编 码的问题。 而哈夫曼编码就是一种不等长的二进制编 码,且哈夫曼树是一种最优二叉树,它的编码也是一种最 优编码,在哈夫曼树中,规定往左编码为0,往右编码为1, 则得到叶子结点编码为从根结点到叶子结点中所有路径中 0和1的顺序排列。 例如,给定权{1,5,7,3},得到的哈夫曼树及编码见 图6-32 (假定权值就代表该字符名字)。 16 7 9 4 5 1 3 1 的编码为:100 5 的编码为:11 7 的编码为:0 3 的编码为:101 (a)哈夫曼树 (b)哈夫曼编码 图 6-32 构造哈夫曼树及哈夫曼编码 2.哈夫曼译码 在通信中,若将字符用哈夫曼编码形式发送出去,对 方接收到编码后,将编码还原成字符的过程,称为哈 夫曼译码。

http://moserfarmshomes.com/shutuziliaoku/589.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有