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

第四章 树第十二讲 树和二叉树1掌握树、二叉树的基本概念和术语，。2掌握二叉树的性质。3. 理解二叉树的存储结构4. 熟悉建立二叉树的二叉链表的算法。 教学重点： 二叉树的定义、二叉树的性质 教学难点： 二叉树的性质 授课内容4.1 树的定义和基本术语前面讨论线性结构的表示及其应用实例。然而，线性结构在许多实际应用中不能明确、方便地表示数据元素之间的复杂关系。树型结构是一种应用十分广泛的非线性结构，其中以二叉树最为常用，它是以分支定义的层次结构。树型结构在客观世界中广泛存在，如家族的家谱、各种社会组织机构，一般都可以用树来形象地表示。在计算机领域中，编译系统中源程序的语法结构、数据库系统中信息的组织形式也用到树形结构。本章重点讨论二叉树的存储结构、各种操作及其应用实例。4.1.1 树的定义1. 定义树（tree）是由n（n0）个结点组成的有限集合T且满足以下条件。1）有且仅有一个特定的结点被称为该树的根（Root）。2）除根结点之外的其余结点可分为m（m 0）个互不相交的集合T1，T2，.，Tm，且其中每个集合又是一棵树，并称之为根的子树（Subtree）。这是一个递归的定义，即在定义中又用到了树的概念，这也反映了树的固有特性。图4-1-1是两棵树的示例。（a）是只有一个根结点A的树。（b）是一棵由11个结点组成的树T，其中A是根结点，其余结点分为三个互不相交的子集：T1=B，E，F，G，K，T2C，H，T3D，I，J。T1，T2，T3也都是树，且是根A的子树，这三棵子树的根结点分别为B、C、D，每棵子树还可以继续划分。K B DATT1 T2 C T3 D T3 AE F G H I J（a）（b）图 4-1-1 树的示例【例4.1】树结构和非树结构的举例AAAACDCBDCBBCBFEDEGFEDFGGFEIH(a) 一棵树结构 (b)一个非树结构 (c)一个非树结构 (d)一个非树结构 图4-1-1（b）所示的树，还可以用图4-1-2所示的方法表示。ABFGKIDJCH（a）集合包含关系文氏图法法法(A(B(E,F,G(K),C(H),D(I,J)（b）广义表法) （b）广义表法（c）凹入法ABCDEFGKHIJ树的基本术语树的结点 树的结点包含一个数据元素及若干个指向其子树的分支。结点的度和树的度 结点的度是结点的子树的个数。树的度是树中结点度的最大值。例如图411（b）中，结点A和B的度为3，结点D的度为2；而树T的度为3。叶子和分支结点 度为零的结点称为叶子或终端结点。度不为零的结点称为分支结点或非终端结点。图411（b）中，结点E、F、H、K、I、J是叶子结点，结点B、C、D、G是分支结点。孩子、双亲及兄弟结点 某结点的各子树的根称为该结点的孩子，而该结点称为孩子的双亲。具有相同双亲的结点互称为兄弟。图411（b）中，A是结点B、C、D的双亲，B、C、D均是结点A的孩子，B、C、D互为兄弟。此外，一棵树上除根结点以外的其他结点称为根的子孙，而根结点是其子孙的祖先。结点的层次和树的深度 结点的层次值从根算起，根的层次值为1，其余结点的层次值为双亲结点层次值加1；树中结点的最大层次值称为树的深度或高度。图411（b）中，结点A、B、E、K的层次值分别为1、2、3、4。树T的深度为4。此外，双亲在同一层的结点互称为堂兄弟，如G和H互为堂兄弟。4.2 二叉树4.2.1 二叉树的定义二叉树是N（N0）个结点的有限集合。它或为空树（N0），或由一个根结点和两个分别称为左子树和右子树的互不相交的子树构成。这个定义是递归的。图4-2-1中展现五种基本形态不同的二叉树。应特别注意，二叉树种左子树和右子树是严格区分的，图4-2-1（c）与（d）是两棵不同的二叉树。 图 4-2-1 二叉树的五种基本形态(a)空二叉树(b)仅有根结点(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左右子树均非空的二叉树二叉树的重要性质性质1 二叉树i（i1）层上至多有2i1个结点。有图422（a）可知，根结点在第1层上，这层结点数最多为1个，即20个；显然第2层上最多有2个结点，即21个；假设第i1层结点最多有2i2个，且每个结点最多有两个孩子，那么第i层上结点最多有22i22i1个。性质2 深度为k（k1）的二叉树至多有2 k1个结点。根据性质1，显然深度为k的二叉树的结点总数至多为： 性质3 在任意二叉树中，若叶子结点（即度为零的结点）个数为n0，度为1的结点数为n1，度为2的结点个数为n2，那么有：n0n21。设n代表二叉树结点总数，那么 nn0n1n2 （4.2.1） 由于有n个结点的二叉树总分支数为n1条，于是得 n10n01n12n2 （4.2.2）将式（4.2.1）代入式（4.2.2）,得 n0n21在研究后面的性质之前，先介绍两种特殊形态的二叉树：满二叉树和完全二叉树。一棵深度为k并且含有2k1个结点的二叉树称为满二叉树，这种数的特点是每层上的结点数都是最大结点数，如图422（a）所示。对满二叉树的结点可以从根结点开始自上向下，自左向右顺序编号，图422（a）中每个结点斜上角的数字即是该结点的编号。深度为k，含有n个结点的二叉树，当且仅当其每个结点的编号与相应满二叉树结点顺序编号从1到n相对应时，则称此二叉树为完全二叉树，如图422（b）所示。而图422（c）则不是完全二叉树。4 5 6 7 E F DAB C D E F G12 3AB CD E F 12 34 5 6AB C12 34 5 6（a）满二叉树 （b）完全二叉树 （c）非完全二叉树 图422 满二叉树和完全二叉树性质4 具有n个结点的完全二叉树，其深度为1（其中表示不大于x的最大整数）。性质5 若对有n个结点的完全二叉树进行顺序编号（1in），那么，对于编号为i（i1）的结点，有： 当i1时，该结点为根，它无双亲结点； 当i1时，该结点的双亲结点编号为； 若2in，则有编号为2i的左孩子，否则没有左孩子； 若2i1n，则有编号为2i1的右孩子，否则没有右孩子；对照图422（a）或图422（b）,读者可看到右性质5所描述的结点与编号的对应关系。 4.2.3 二叉树的存储结构二叉树可以采用顺序存储结构或链式存储结构。1. 顺序存储结构用一组连续的存储单元存放二叉树中的元素，这对于满二叉树和完全二叉树是非常合适的。假设将图4-2-2（a）所示的满二叉树存放在一维数组bt中，可以发现结点的编号恰好与数组元素的下表相对应（见图4-2-3）。根据二叉树性质5，结点在一维数组中的相对位置隐含着结点之间的关系。因此在数组bt中可以方便地由某结点bti的下标i找到它们的双亲结点bti/2，或左、右孩子结点2i、bt2i+1.2. 链式存储结构在二叉树链式存储结构中最常用的是二叉链表和三叉链表。二叉链表的每个结点有一个数据域和两个指针域，一个指针指向左孩子，另一个指向右孩子。结点结构描述为：typedef struct btnodeELEMTP data;struct btnode *lchild,*rchlid;BTNode; 例如图4-2-4（a）中的二叉树T，它的二叉链表如图4-2-4（b）所示，其中bt是一个*BTNode类型的变量，并且指向根结点，通常对于二叉链表的操作都是从它开始的。在实际操作中，如经常需要寻找结点的双亲，便可以采用三叉链表的形式。三叉链表的结点比二叉链表结点多一个指向双亲的指针域。其结点结构描述为：typedef struct btnode _ p ELEMTP data; struct btnode * parent, *lchild, *rchild; BTNode_p;三叉链表如图4-2-4（c）所示。图 4-2-4 二叉树的链表存储结构 D E D EB CAF（a）二叉树T （b）二叉链表 （c）三叉链表B CAbt F B CAbt F D E 4.2.4 二叉树的存储结构建立二叉链表的方法不止一种。这里介绍的方法的原理是利用二叉树的性质5。对于一棵任意的二叉树，先按满二叉树对其结点进行编号，如图4-2-5(a)所示。虽然此二叉树并非满二叉树，结点的编号并不连续，但结点编号之间的关系是满足二叉树的性质5的。E DB CAF12 35 7 14（a）i 1 2 3 5 7 14ch A B C E D F（b）图425 二叉树及数据表算法实现时，需设置一个辅助向量p，用于存放指向结点的指针，如pi中存放编号为i的结点的指针（该结点的地址）。图4-2-5（a）的原是数据序列如图4-2-5（b）所示，按此表一一输入数对（结点编号i和数据ch）。每输入一对数（i，ch），便产生一个新的结点s，同时将该结点的指针保存在pi中。当i1时，所产生的结点为根结点。当i1时，由性质5可知：其双亲结点的编号ji/2。如果i为偶数，则它是双亲的左孩子，就让pj-lchilds；如果i为奇数，则它是双亲的右孩子，就让pj-rchilds。这样就将每个结点与其双亲结点相连，从而建立起了二叉链表。算法见算法4.1。算法4.1 #define MAXNUM 20 BtNode *pMAXNUM+1;BtNode *Creat_Bt (void) printf(n enter i, ch :); scanf(