《数据结构5》由会员分享，可在线阅读，更多相关《数据结构5（82页珍藏版）》请在金锄头文库上搜索。
1、第五章 树 5.1 树的概念 5.2 二叉树 5.3 二叉树遍历 5.4 二叉树其他运算 5.5 树的存储结构和运算,树形结构是一种非线性结构，应用十分广泛。 如：行政机构、家谱、磁盘目录等,内蒙古大学,理工学院,计算机学院,生命科学学院,外国语学院,人文学院,数学系,物理系,电子系,计算机系,计算中心,网络中心,汉语系,历史系,哲学系,生物系,环境系,动物中心,生物工程中心,资源所,英语系,日语系,行政机构,磁盘目录,树,根-根结点 分枝-分枝结点 叶-叶结点,树的定义：树是n（n=0）结点的有限集，任意非空树： (1) 有且仅有1个特定的结点称为根（Root）,无前驱;其余结点有且只有一个
2、前驱,可有m(m=0)个后继. (2) 当n1时，其余的结点可分为m个互不相交的子集 T1, T2, , Tm, 每个又都是树，称为根的子树（Sub tree）在树的定义中用了递归的概念.,树是一种层次结构 （hiberarchy）,1,2,3,4,5,5.1树的基本概念,Tree=(D, R) D=Book, C1, C2, C2, S1.1, S1.2, S2.1, S2,2, S2.3, S2.1.1, S2.1.2 R=, , , , , , , , , ,Book,C1,C2,C3,S1.1,S1.2,S2.1,S2.2,S2.3,S2.1.1,S2.1.2,Chapter,Sect
3、ion,Section,树的基本术语（Basic Terminology）： 主要来源于家谱和树； 1、双亲、子女（Parent, Child）：若a,b属于R，则称a是b的双亲，b是a的子女 2、结点度（Degree）：结点的子女数； 3、树的度：最大的结点度； 4、层（Level）：根在第1层，其它任一结点所在的层是其双亲的层+1； 5、叶（Leaf）：度为0的结点； 6、分枝结点（Branch node）(非终端结点)：度不为0的结点； 6、兄弟（Sibling)：具有同一双亲的结点互称兄弟； 7、堂兄弟（Cousin）：在同层的非兄弟结点互称堂兄弟；,8、深度（Depth）：树的最大层
4、数；或称为高； 9、路径（Path）：如果有结点序列n1,n2,n3,nk，并且前1个结点是后1个结点的双亲；它的长度是k-1; 10、祖先、后代（ancestor）：一个结点是它所有子树中的结点的祖先，这些结点是它的后代； 11、有序树（Ordered tree）：每个结点的子女由左到右是有次序的；否则是无序树；,A,B,C,A,C,B,无序,有序,12、森林（Forest）：是m棵互不相交的树的集合；,T1,T2,T3,T4,T5,T6,F=T1,T2,Tm, 其中Ti是树。当m=0时，F是空森林。对树中每个结点而言，其子树的集合为森林。反之，若给森林F =T1,T2,Tm中的每棵树的根结
5、点都赋予同一个双亲结点，则构成一棵树。,5.2 二叉树（Binary Tree） 二叉树是另一种树形结构。 5.2.1 二叉树的定义和基本术语 二叉树：是n（n=0）结点的有限集，任意非空树： (1) 有且仅有1个特定的结点称为根（Root）; (2) 当n1时，其余的结点最多分为2个互不相交的子集 T1, T2, 每个又都是二叉树，分别称为根左子树和右子树 该逻辑结构起名为：Binary_Tree,二叉树的5种基本形态：,1 空,2 只有根,3 右子树空,4 左子树空,5 左、右子树非空,5.2.1 二叉树的定义和基本术语,DATA BinaryTree isData采用任一种方式存储的一棵
6、二叉树。Operationsvoid InitBTree( /按照一定次序遍历一棵二叉树,5.2.1 二叉树的定义和基本术语,bool FindBTree(/清除二叉树中的所有结点 end BinaryTree,5.2.2 二叉树的性质 二叉树的几个重要性质 性质1: 在二叉树的第i层最多有2i-1 个结点(i=1) 用归纳法证明: 证明：i = 1, 只有根结点，显然成立设i = k时成立，最多有2k-1当i= k+1时，最多的结点个数：2k-1 * 2 = 2k-1+1 = 2k = 2( k+1)-1 性质2: 深度为h的二叉树最多有2h 1个结点; 证明：二叉树的结点个数为：1 + 2
7、 + + 2h-1= 2h-1,性质3: 任一二叉树, 若叶结点树是n0 , 度为2的结点树是n2 ,则: n0 = n2 +1 证明：设n1为T中度为1的结点数，n2为T中度为2的结点数，n0为T中度为0的结点数, 则总结点数：n = n0 + n1 + n2另：除根结点外，所有结点都有且仅有一个双亲结点，也就是仅有一个分支进入，若B为分支数，则B = n1 + 2 * n2 = n - 1；n1 + 2 * n2 = n0 + n1 + n2 1;n0 = n2 + 1;,满二叉树(Full Binary Tree): 每一层的结点树都达到了最大的二叉树.深度为k且有2k-1个结点的二叉树
8、。 编号的满二叉树: 从根开始,由上到下, 从左到右地对每个结点编号的满二叉树. 或者说: 根的编号是1, 一个结点,它的左子女的编号是它的编号的2倍, 它的右子女的编号是它的编号的2倍+1.,编号的满二叉树,完全二叉树 (Complete Binary Tree)若设二叉树共有h层。除第 h 层外，其它各层 (1 h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。,完全二叉树 特征： 1。叶子结点只可能在层次最大的两层上出现 2。任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的最大层次为l或l+1.,性质4: 具有n个结点的完全二叉树,其深度是
9、或,证明：设树的深度为k，则：2k-1 1+1 n 2k 12k-1 n 2k 12k-1 1 n 2k 12k-1 n 2kk-1 log2n kk =,性质4: 具有n个结点的完全二叉树,其深度是 或,证明：设树的深度为k，则：2k-1 1+1 n 2k 12k-1 n 2k 12k-1 1 n 2k 12k-1 n+1 2k k=,性质5：编号的完全二叉树，对任一结点i有： （1） 若i=1, 是根。 若i=1，则它的双亲是 （2）若2i=n，则结点i的左子女是2i; 否则无左子女； （3）若2i+11,STi 的双亲是STi/2;若i=1,STi为根结点，无双亲。 （2）若2in /2
10、的结点是叶子。 （3）若2i+1left );cout data;InOrder ( BT-right ); ,前序遍历二叉树算法的框架是： 若二叉树为空，则空操作 否则 访问根结点 (V)； 前序遍历左子树 (L)； 前序遍历右子树 (R)。 遍历结果- + a * b - c d / e f,前序遍历 (Preorder Traversal),-,-,/,+,*,a,b,c,d,e,f,二叉树递归的前序遍历算法void PreOrder ( BTreeNode * BT ) if ( BT != NULL ) cout data;PreOrder ( BT-left );PreOrder ( BT-right ); ,后序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (V)。遍历结果a b c d - * + e f / -,后序遍历 (Postorder Traversal),-,-,/,+,*,a,b,c,d,e,f,二叉树递归的后序遍历算法void PostOrder ( BTreeNode * BT ) if ( BT != NULL ) PostOrder ( BT-left );PostOrder ( BT-right );cout data; ,
