武汉软件工程职业学院《数据结构讲义》第12讲树和2叉树

1、第十二讲树和二叉树1. 掌握树、二叉树的基本概念和术语，2 .掌握二叉树的性质。3. 理解二叉树的存储结构4. 熟悉建立二叉树的二叉链表的算法。? 教学重点：二叉树的定义、二叉树的性质? 教学难点：二叉树的性质? 授课内容4.1 树的定义和基本术语前面讨论线性结构的表示及其应用实例。然而，线性结构在许多实际应用中不能明确、方便地表示数据元素之间的复杂关系。树型结构是一种应用十分广泛的非线性结构，其中以二叉树最为常用，它是以分支定义的层次结构。树型结构在客观世界中广泛存在，如家族的家谱、各种社会组织机构，一般都可以用树来形象地表示。在计算机领域中，编译系统中源 程序的语法结构、数据库系统中信息的

2、组织形式也用到树形结构。本章重点讨论二叉树的存储结构、各种操作及其应用实例。4.1.1 树的定义1.定义树(tree )是由n ( n>0)个结点组成的有限集合T且满足以下条件。1) 有且仅有一个特定的结点被称为该树的根( Root )。2) 除根结点之外的其余结点可分为m(m >0)个互不相交的集合 T1, T2，. ，Tm且其中每个集合又是一棵树，并称之为根的子树(Subtree )。这是一个递归的定义，即在定义中又用到了树的概念，这也反映了树的固有特性。图4-1-1是两棵树的示例。(a)是只有一个根结点 A的树。(b)是一棵由11个结点组 成的树T，其中A是根结点，其余结点分

3、为三个互不相交的子集：T仁B，E，F，G K，T2=C，H，T3= D，I，J。T1, T2, T3也都是树，且是根 A的子树，这三棵子树的根结点 分别为B、C D,每棵子树还可以继续划分。A(a)【例4.1】树结构和非树结构的举例GCBO (DIII'EF -G(b) 个非树结构(c)一个非树结构(d) 一个非树结构图4-1-1( b)所示的树，还可以用图4-1-2所示的方法表示。(a)集合包含关系文氏图法法法ABG KC H DJ '(A(B(E,F,G(K),C(H),D(I,J)(c)凹入法(b)广义表法树的基本术语树的结点树的结点包含一个数据元素及若干个指向其子树的分

4、支。结点的度和树的度结点的度是结点的子树的个数。树的度是树中结点度的最大值。例如图4 1 1 (b)中，结点A和B的度为3,结点D的度为2;而树T的度为3。叶子和分支结点度为零的结点称为叶子或终端结点。度不为零的结点称为分支结点或非终端结点。图 4 1 1 (b)中，结点E、F、H K、I、J是叶子结点，结点 B、C D G 是分支结点。孩子、双亲及兄弟结点某结点的各子树的根称为该结点的孩子，而该结点称为孩子的双亲。具有相同双亲的结点互称为兄弟。图4 1 1 (b)中，A是结点B C、D的双亲，B C、D均是结点A的孩子，B C D互为兄弟。此外，一棵树上除根结点以外的其他结点 称为根的子孙，

5、而根结点是其子孙的祖先。结点的层次和树的深度结点的层次值从根算起，根的层次值为1，其余结点的层次值为双亲结点层次值加 1;树中结点的最大层次值称为树的深度或高度。图4 1 1 (b)中，结点A、B E、K的层次值分别为1、2、3、4。树T的深度为4。此外，双亲在同一层的结 点互称为堂兄弟，如 G和H互为堂兄弟。4.2 二叉树4.2.1 二叉树的定义二叉树是N (NA 0)个结点的有限集合。它或为空树(Nh 0),或由一个根结点和两个分别称为左子树和右子树的互不相交的子树构成。这个定义是递归的。图4-2-1中展现五种基本形态不同的二叉树。 应特别注意，二叉树种左子树和右子树是严格区分的，图4-2

6、-1 ( c)与(d)是两棵不同的二叉树。(d)左子树为(e)左右子树均非空的二叉树空的二叉树空二叉树(b)仅有(c )右子树为根结点空的二叉树图4-2-1二叉树的五种基本形二叉树的重要性质性质1 二叉树i (i > 1)层上至多有2i 1个结点。有图4 2 2 (a)可知，根结 点在第1层上，这层结点数最多为1个，即20个；显然第2层上最多有2个结点，即21第四章树亂据结拘个；假设第i 1层结点最多有2i 2个，且每个结点最多有两个孩子，那么第 i层 上结点最多有 2 x 2i 2 = 2i 1个。性质2 深度为k ( k> 1 )的二叉树至多有 2 k 1个结点。根据性质1，显

7、然深度为k的二叉树的结点总数至多为：k(位于第i层上的结点的最多数)2i 12k 1性质3在任意二叉树中，若叶子结点(即度为零的结点)个数为n0,度为1的结点数为n 1,度为2的结点个数为n2,那么有：n0= n2 + 1。设n代表二叉树结点总数，那么n= n0+ n1 + n2()由于有n个结点的二叉树总分支数为n- 1条，于是得n 1 = 0 x n0+ 1 x n1 + 2 x n2 ()将式()代入式(),得n0= n2 + 1在研究后面的性质之前，先介绍两种特殊形态的二叉树：满二叉树和完全二叉树。一棵深度为k并且含有2k 1个结点的二叉树称为满二叉树，这种数的特点是每层上的结点数都是

8、最大结点数，如图4 2 2 (a)所示。对满二叉树的结点可以从根结点开始自上向下，自左向右顺序编号，图4 2 2 ( a)中每个结点斜上角的数字即是该结点的编号。深度为k，含有n个结点的二叉树，当且仅当其每个结点的编号与相应满二叉树结点顺序编 号从1到n相对应时，则称此二叉树为完全二叉树，如图4 2 2 (b)所示。而图4 2 2(c)则不是完全二叉树。(a)满二叉树(b)完全二叉树(c)非完全二叉树图4 2 2满二叉树和完全二叉树性质4 具有n个结点的完全二叉树， 其深度为+ 1(其中表示不大于 x的最大整数) 性质5 若对有n个结点的完全二叉树进行顺序编号( K i <n),那么，对

9、于编号为 i (i > 1)的结点，有:当i = 1时，该结点为根，它无双亲结点；当i > 1时，该结点的双亲结点编号为；若2i v n,则有编号为2i的左孩子，否则没有左孩子；霰祸结狗第四章树若2i + 1 v n,则有编号为2i + 1的右孩子，否则没有右孩子； 对照图4 2 2 (a)或图4 2 2 ( b),读者可看到右性质 5所描述的结点与编号的对 应关系。423二叉树的存储结构二叉树可以采用顺序存储结构或链式存储结构。1顺序存储结构用一组连续的存储单元存放二叉树中的元素，这对于满二叉树和完全二叉树是非常合适的。假设将图4-2-2 (a)所示的满二叉树存放在一维数组bt中

10、，可以发现结点的编号恰好与数组元素的下表相对应(见图 4-2-3 )。根据二叉树性质5,结点在一维数组中的相对位置隐含着结点之间的关系。因此在数组bt中可以方便地由某结点bti的下标i找到它们的双亲结点bti/2，或左、右孩子结点2i 、bt2i+1.2. 链式存储结构在二叉树链式存储结构中最常用的是二叉链表和三叉链表。二叉链表的每个结点有一个数据域和两个指针域，一个指针指向左孩子，另一个指向右孩子。结点结构描述为：typedef struct btno deELEMTP data;struct btnode *lchild,*rchlid;BTNode;例如图4-2-4 (a)中的二叉树 T

11、,它的二叉链表如图 4-2-4 (b)所示，其中bt是一 个*BTNode类型的变量，并且指向根结点，通常对于二叉链表的操作都是从它开始的。在实际操作中，如经常需要寻找结点的双亲，便可以采用三叉链表的形式。三叉链表的结点比二叉链表结点多一个指向双亲的指针域。其结点结构描述为：typedef struct btnode _ p ELEMTP data;struct btnode * pare nt, *lchild, *rchild; BTNode_p;三叉链表如图4-2-4 ( c)所示。(a)二叉树T(b)二叉链表(c)三叉链表图4-2-4二叉树的链表存储结构424 二叉树的存储结构建立二叉

12、链表的方法不止一种。这里介绍的方法的原理是利用二叉树的性质5。对于棵任意的二叉树，先按满二叉树对其结点进行编号，如图4-2-5(a)所示。虽然此二叉树并i1235714chABCEDF非满二叉树，结点的编号并不连续，但结点编号之间的关系是满足二叉树的性质5的。(b)图4 2 5二叉树及数据表算法实现时，需设置一个辅助向量p,用于存放指向结点的指针，如pi中存放编号为i的结点的指针(该结点的地址)。图4-2-5 (a)的原是数据序列如图4-2-5 ( b)所示，按此表一一输入数对(结点编号i和数据ch)。每输入一对数(i , ch),便产生一个新的结点s,同时将该结点的指针保存在pi中。当i = 1时，所产生的结点为根结点。当i>1时，由性质5可知：其双亲结点的编号j = i/2。如果i为偶数，则它是双亲的左孩子，就让pj->lchild = s;如果i为奇数，则它是双亲的右孩子，就让pj->rchild = s。这样就将每个结点与其双亲结点相连，从而建立起了二叉链表。算法见算法4.1。算法4.1#defi ne MAXNUM 20】uno宀 兰。03二03- P% P% : =ueos X = - II。二9U S: 汪 u_d宀 p