数据结构6树8+2

《数据结构6树8+2》由会员分享，可在线阅读，更多相关《数据结构6树8+2（111页珍藏版）》请在金锄头文库上搜索。

1、1定义说明了： 树是一种递归的数据结构树中包含树。 结构特点：结点间有明显层次关系。一. 树的定义树是n(n0)个结点的有限集，n=0 空树； 在一棵非空树中： (1)有且只有一个特定的结点根结点(root)； (2)当n1,其余结点可分为m个互不相交的子集T1,T2, ,Tm，它们又是树 根结点的子树(Sub Tree)。例如：学校的行政关系、书的层次结构、 人类的家族血缘关系、操作系统的目录、 结构程序模块等。2A是根T1 = B,E,FT2 = C,G,I,JT3 = D,H在树中，每个结 点被定义为它的 每个子树的根结 点的前驱。二. 树的表示(1) 结点连线 隐含：上方结点是下方结点

2、的前驱。ADCBHGFEJI3(2) 二元组表示如下面的树可表示为：K=C，G，I，JR=，JIGC4(3) 集合图表示法每棵树对应一个圆形，圆内包含根结点和子树。ADCBHGFEJII JAE B D HF C G 5(4) 凹入表示法ABEFCGIJDH每棵树的根对应着一个条形，子树的根对应 着一个较短的条形。ADCBHGFEJI6(5) 广义表表示每棵树的根作为由子树构成的表的名字而放在表 的左边。 ADCBHGFEJIA ( B (E，F)，C (G(I，J) )，D (H) )7(1)树的结点：包含一个数据 元素及若干指向其子树的分支 (2)结点的度(degree)：结点拥有的子树数

3、。 (3)根结点：无前驱。 (4)叶子(终端结点)：度为零的结点。无后继。(5)分支结点(非终端结点)度不为零的结点。除根结 点外，分支结点也称内部结点(1个前驱,多个后继)(6)树的度：树内各结点的 度的最大值。三.基本术语ADCBHGFEJI8(7)孩子：结点的子树的 根称为该结点的孩子。 相应地，该结点称为孩 子的双亲。(8)兄弟：同一双亲的孩 子之间互为兄弟。(9)祖先：结点的祖先是 从根到该结点所经分支 上的所有结点。(10)子孙：以某结点为 根的子树中的任一结点 都称为该结点的子孙。ADCBHGFEJI9(11)结点的层次：根为第一 层，根的孩子为第二层。(12)树的深度(高度)：

4、树中结点的最大层次。(13)有序树及无序树：如：是两棵不同的有序树。ACBABCADCBHGFEJI10任何一棵非空树是一个二元组Tree = (root，F ) 其中：root 被称为根结点，F 被称为子树森林(14) 森林：是 m(m0)棵互不相交的树的集合ArootBEFKLCGDHIJMF11四. 树的基本操作(1) 初始化空树: INITIATE( (2) 求根结点: ROOT(T) ；或：ROOT(x)； (3) PARENT(T, x); 求当前结点的双亲结点 (4) CHILD(T, x, i ); 求树T中结点x的第i个孩子 (5) Right_sibling(T, x);

5、求结点x的右兄弟 (6) CRT_TREE(以结点x为根，以F为子树森林构造树T。设：Tree T12(7) INS_TREE(将以x为根的子树作为结点y的第i棵子树插入到 树T中。(8) DEL_CHILD(将树T中结点x的第i棵子树删除。(9) 树的遍历: TRAVERSE(T);按某个次序依次访问树中各个结点，并使每个 结点只被访问一次。(10)清除树结构: CLEAR(由于树和二叉树可以相互转换，先讨论二叉树13二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树EF特点：每个结点至多只有两棵子树，子树有左 右之分，

6、其次序不能任意颠倒。14二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子 树均不 为空树15(1) 一棵度为2的树与一棵二叉树是否有区别？(2) 有三个结点的二叉树与有三个结点的树的形 态是否相同？三个结点的树：三个结点的二叉树问题：问题：16特殊的二叉树特殊的二叉树：(2) 完全二叉树：除最后一层外, 其余各层都是满 的;最后一层或者 是满的，或者是 右边缺少连续的 若干结点。(1)满二叉树：二叉树中每一层的 结点数都达到最大13102765498111514121313102765498111217理想平衡树：在一棵二叉树中，若除 最后一层外，其余层都是满

7、的，则称此树 是理想平衡树。满二叉树和完全二叉树是理想平衡树。 但理想平衡树不一定是完全二叉树。1310276549811121318性质1在二叉树的第i层上至多有2i-1个结点(i1)。用归纳法证明：(1)i=1时, 2i-1=1，即只有一个根结点。(2)设j=i-1时命题成立，证明j=i时命题也成立。设：第i-1层上至多有2i-2个结点，在第i层上的结点数最多为：考虑：m叉树的第i层至多有 个结点。 mi-1(因为二叉树中每个结点的度至多为2)2i-2*2= 2i-119深度为k的二叉树至多有2k-1个结点，(k1)。性质2= ( 1 + 2 + 22 + + 2k-1) = 2k-1(第

8、i层上的最多结点数目)2i-1=考虑：深度为k的m叉树，最多有 个结点 。20对任何一棵二叉树T，如果其叶子结点数目为n0 ，度为2的结点数目为n2，则有n0=n2+1。性质313102765498111213证明： 设度为1的结点个数为n1, 总结点数为n，则有n = n0 + n1 + n2 设分支数为B， 从下向上看，知： B = n - 1 从上向下看，这些分支数是由度为1和度为2的结 点发出的， 因此： B = n1 + 2n2n0 + n1 + n2 = n1 + 2n2 + 1 所以： n0 = n2 + 121性质4具有n个结点的完全二叉树的深度为：k = log2n + 1。

9、 2k-1-1 1, 则其双亲 parent(i)是结点i/2 (2)如果2in，则结点i 为叶子，否则其左孩子 Lchild(i)是结点2i。(3)如果2i+1n, 则结点i无右孩子，否则其右孩 子是结点2i+1。性质513102765498111223证明(2),(3):对于i=1，左孩子编号是2， 右孩子编号是3。对于i1，可分两种情况讨论：设第i号结点的 左孩子编号为2i；右孩子编号为2i+1；第一种情况：第i号结点和第i+1号在同一层。第二种情况：第i号结点和第i+1号不在同一层则编号为i的结点必为第j层的最后一个结点，那 么编号为i+1的结点则为第j+1层的第一个结点。24对于完全

10、二叉树，可用一维数组来存储。 A B C D E F G H I J0 1 2 3 4 5 6 7 8 9 10 AGCBDHJEIF例如: char btree11；25对于一般二叉树，则必须将其“完全化”之 后来存储。AFCBDHGE存储顺序：A B C D E # F # # G H0 1 2 3 4 5 6 7 8 9 10 1126char btr12ABCF ED11ABCF ED1248 9105637FE#DC#BA11109876543210 #优点：直接利用元素在数组中的位置(下标)表 示其逻辑关系。缺点：若不是完全二叉树,则会浪费空间。因此，顺序存储适合于(接近)完全二叉

11、树。27lchild data rchild结点的结构在含有n个结点的二叉链表中有多少空指针域？ 性质在含有n个结点的二叉链表中有n+1个空指针域。AHDBCGFEIT二叉链表AB D C E H F G I 28rootADEBCF三叉链表parent lchild data rchild结点结构:29二叉链表类型定义：typedef struct BiTNodeDataType data；struct BiTNode *lchild；struct BiTNode *rchild； BiTNode，*BiTree；BiTree bt；三叉链表的定义：BiTNode中加一个parent成员；3

12、0静态二叉链表：则结点类型可定义为：typedef struct BiNodeDataType data；int lchild；int rchild； StaticBiNode；typedef StaticBiNode StaticBiListM；31Data A B D C E N F G I .lchild 2 4 5 0 7 0 0 0 0 .rchild 3 0 6 0 8 9 0 0 0 .1 2 3 4 5 6 7 8 9 FAHDBCGFEI12345678932根结点(D)非空二叉树 左子树(L)右子树(R)共有六种访问次序：DLR, LDR, LRD, DRL, RDL, R

13、LD若限定先访问左子树，后访问右子树，则只有： DLR(先序遍历), LDR(中序遍历), LRD (后序遍历)。 33（1）DLR 先序遍历（先根遍历）if（树不空）访问根结点; 先序遍历左子树; 先序遍历右子树;（2）LDR 中序遍历（中根遍历）if（树不空）中序遍历左子树;访问根结点;中序遍历右子树;（3）LRD 后序遍历（后根遍历）if（树不空）后序遍历左子树; 后序遍历右子树;访问根结点；34递归算法：(1) 先序遍历void preorder(BiTree bt)if(bt) printf(btdata)；preorder(btlchild)；preorder(btrchild)；

14、 / preorder35(2) 中序遍历void inorder(BiTree bt)if (bt) inorder(btlchild)；printf(btdata)；inorder(btrchild)； / inorder36(3) 后序遍历void postorder(BiTree bt)if(bt) postorder(btlchild)；postorder(btrchild)；printf(btdata)； / postorder 37先序遍历：D L RADBCD L RA D L RD L RBDCD L RABDC38先序序列：- + A * B C D / E F中序序列：A + B * C D E / F后序序列：A B C D - * + E F / -层次遍历：- + / A * E F B C D- +/A*EF B-CD39mid(a lch)mid(*lch)；printf(a)； mid(a rch)；mid(-lch)； pr