树结构的定义和基本操作

《树结构的定义和基本操作》由会员分享，可在线阅读，更多相关《树结构的定义和基本操作（85页珍藏版）》请在金锄头文库上搜索。

1、第6章 树6.1 树结构的定义和基本操作 6.2 二叉树 6.3 遍历二叉树 6.4 树和森林 6.5 树的应用 习题前面谈的基本上是线性表结构，线性表, 栈、队列、串、一维数组，即使二维数组(矩 阵结构、十字类别)也不过只是线性表的组合 ，即：除首元素和尾元素以外，每一个元素 有唯一的前驱和后续元素。树形结构是一种重要的非线性结构，讨 论的是层次和分支关系，即：除了有一个根 元素没有前驱以外，每一个元素都有唯一的 前驱元素；另外，每一个元素有零个或多个 后继元素。例如，人类社会的族谱和各种社 会组织机构都可以用树来形象表示。树在计 算机领域中也得到广泛应用。 6.1 树结构的定义和基本操作6

2、.1.1 树的定义递归定义：树(tree)是n(n0)个结点的有限集。在任意一棵树中：(1)有且只有一个特定的称为根(root)的结点。(2)当n1时，其余结点可分为m(m0)个互不相交的 有限集T1，T2，Tm，其中每一个集合本身又是一 棵树，称为子树(subtree)。图6.1所示，在图中的树有13个结点，A是树根，其 余结点构成三个互不相交的子集：T1=B，E，F，K， L，T2=C，G，T3=D，H，I，J，M；T1，T2和T3 都是根A的子树，且它们本身也是一棵树。如在T1中， B是该子树根，其余结点又构成两个互不相交子集， T11=E，K，L和T12=F，T11和T12都是根B的子

3、树 ，且它们本身也是一棵树。 图6.1 树的示例 上面是树的一个递归定义，树除了该递归定义外，还 有其它定义。如图6.2所示为图6.1中树的各种表示.从图6.1的示例可以看出 ，树有两个特点： (1) 树的根结点没有 前驱结点，其余结点有 且只有一个前驱结点。(2) 树结点可以有零 个或多个后继结点。树结构描述的是层 次和分支关系。图6.2 树的其它三种表示方法 图6.2(a)是以嵌套集合的形式表示(任何两个集合，或不相交， 或一个包含另一个)；图6.2(b)是以广义表的形式表示，根作为 子树森林组成的表的名字写在表的左边；图6.2(c)用的是凹入 表示法。 6.1.2 树的常用术语结点：是包

4、含一个数据元素和若干指向其子树的分支(即关系).结点的度：结点拥有的子树数。叶子：度为0的结点。分支结点：度不为0的结点。树的度：树内各结点的度的最大值，图6.1所示树是一 个3叉树.孩子结点(child)：结点的后继，结点子树的根结点。 双亲结点(parent)：孩子结点的前驱。s是f的孩子,则f是s的双亲.兄弟结点(sibling)：同一个双亲的孩子之间互称为兄弟。祖先结点：从根到该结点的所经过分支上的所有结点,图6.1树中L结点的祖先结点是A，B，F。子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙. 图6.1树中D的子孙结点为H，I，J，M. 结点的层次：根是第1层，依次为第2

5、层。 树的深度：树中结点的最大层次，图6.1所示的树深度为4.有序树：树中结点的各子树看成从左至右是有次序的,例如, 人类社会的族谱就是一个有序树。无序树：树中结点的各子树没有次序的，孩子结点的顺序可以调整。森林：m(m0)棵互不相交的树的集合。森林和树之间的联系是：一棵树取掉根，其子树构成一个森林；同样，一个森林增加一个根结点成为树.6.1.3 树的基本操作(1)initiate(T)：T树的初始化，包括建树。(2)root(T)：求T树的根。(3)parent(T,x)：求T树中x结点的双亲结点。(4)child(T,x,i)：求T树中x结点的第i个孩子结点。(5)right_siblin

6、g(T,x)：求T树中x结点的右兄弟。(6)Insert_child(y,i,x)：将根为x的子树置为y结点的第i个孩子(7)del_child(x,i)：删除x结点的第i个孩子(整个子树)。(8)traverse(T)：遍历T树。按某个次序依次访问树中每一个 结点，并使每个结点都被访问且只被访问一次。(9)clear(T)置空T树。以上操作的具体实现，依赖于采用的存储结构。6.2 二叉树 6.2.1 定义及其操作二叉树是另一种树形结构，它的特点是每一个结点至 多只有两棵子树，并且，子树有左、右之分，其次序不能 颠倒。递归定义：二叉树是n(n0)个结点有限集，当n1时， 有而且仅有一个结点为根

7、结点，其余结点构成为2个互不相 交的子集T1，T2，其中每一个子集又是一棵二叉树，分别 称作为根结点的左子树和右子树。注意：二叉树不是度为2的树，在度为2的树中，当一 个结点的度为1时，其子树是不考虑序的；而在二叉树中， 当一个结点的度为1时，其子树要考虑序，即：是作为双亲 的左子树还是作为双亲右子树。另外，树不允许为空树， 但二叉树允许为空。由二叉树的递归定义可知，二叉树有五种基本形态， 如图6.3所示。(a)空树 (b)仅有根 (c)右子树空 (c)左、右子树均在 d)左子树空 图6.3 二叉树的五种形态 由二叉树的递归定义可知，二叉树有五种基本形态，如图 6.3所示。与树的基本操作类似，

8、二叉树有下面一些基本操作：(l)lch(T,x)：求T树中x结点的左孩子。(2)rch(T,x)：求T树中x结点的右孩子。(3)lsibling(T,x)：求T树中x结点的左兄弟。(4)rsibling(T,x)：求T树中x结点的右兄弟。 其他操作与树相同。 6.2.2 二叉树的性质二叉树具有下列重要性质。性质1：在二叉树的第i层上至多有2i-1个结点(i1)。当i=1时，只有一个根结点，2i-1=20=1，由于二叉树的 每一个结点的度最多为2，因此，当i2时，第i层上的结点 数，最多为上一层的2倍，所以，第2层最多有21=21个结 点，第3层最多有221=22个，依次类推，第i层最多有22i

9、- 2=2i-1个。性质2：深度为k的二叉树至多有2k -1个结点(k1)。由性质1可见，深度为k的二叉树的最大结点数为：(第i层上的最大结点数)=2i-1=2k-1性质3：对任何一棵二叉树T，如果其叶子结点数为n0，度 为2的结点数为n2，则n0=n2+1。在二叉树中，度为1的结点为n1，这样树的结点数n=n0+n1+n2另外，除根结点外每个结点都有唯一的双亲结点指向该结点 ，所以度为1的结点指向一个后续，而度为2的结点指向两个 后续，因此，二叉树结点数n=n1+2*n2+1。因为 n=n0+n1+n2=n1+2*n2+1可得 n0=n2+1下面介绍两种特殊的二叉树。满二叉树：一棵深度为k的

10、二叉树，若其有2k-1个结点 ，则称为满二叉树。在满二叉树中只有度为0和度为2 的结点，并且在每一层上的结点数都是该层所能取结 点的最大值。如图6.4(a)所示为一个深度为4的满二叉树 。(a) 满二叉树 完全二叉树：一个深度为k的二叉树，其结点数nn ，则该结点不存在左孩子。(3)若2i+1n，则i的右孩子是标号为2i+1的结点；若 2i+1n，则该结点不存在右孩子。6.2.3 二叉树的存储结构(1)顺序存储结构满二叉树或完全二叉树顺序存储方式: 即用一个数组按 结点的标号顺序依次存放二叉树中的数据元素。图6.4(b) 是一棵完全二叉树，可以用一维数组bt12作为它的存储 结构，将二叉树中标

11、号为i的结点的数据元素存放在分量 bti-1中，如图6.5(a)所示。存储位置暗藏了树中的关系， 树的关系是通过完全二叉树的性质实现，例如bt5的双亲 结点标号是k=trunc(i+1)/2=3，双亲结点所对应的数组分 量btk-1=bt2。1 2 3 4 5 6 7 8 9 10 11 12 下 标0 1 2 3 4 5 6 7 8 9 10 11 (a)完全二叉树 非完全二叉树，也必须按完全二叉树的形式存储，如 图6.5(b)所示，图中“0”表示该结点不存在。对于畸形 二叉树(树中大量存在度为1和度为0的结点)，采用顺 序存储方式，空间浪费较大。 1 2 3 4 5 0 0 0 0 6 下

12、 标0 1 2 3 4 5 6 7 8 9 (b)非完全二叉树 (2)链式结构由于二叉树是一种非线性结构，一般情况下采 用链式存储结构。不同的结点结构，可以构成不同的 链式结构，常用的有以下两种。(a)标准存储(也称为“二叉链表”)。每一个结点有三个域，即：数据域、左指针、右指 针。用C语言描述如下：struct bitnode int data;struct node *lch,*rch; typedef struct bitnode BiTNode;(b)带逆存储(也称为“三叉链表”)。在二叉链表中，便于找到一个结点的左右孩子， 但要找一个结点的双亲不方便，必须从树根开始遍历整 个二叉树，

13、所以，在结点中增加一个指向双亲结点的指 针域。结点的结构如下：struct tritnode int data;struct node *lch,*rch,*parent;typedef struct tritnode TriTnode; 图6.6是一个二叉树的两种链式存储结构图示。从图中 可知，二叉树的链式存储结构和逻辑结构是一致的。(a)二叉树逻辑结构 (b)二叉链表 (c)二叉链表 图6.6 二叉树的链式存储结构 6.3 遍历二叉树 一个遍历二叉树的问题，即：按一定规律访问二叉树 上的每个结点，且每个结点只能访问一次。这里“访问”的 含义很广，可以是对结点作各种处理。在线性结构中，因为除

14、尾结点外，每一个结点都有唯 一后续，所以只要从首结点开始，每次取后继结点就可以 遍历线性结构中每一个结点。而二叉树是一种非线性结构 ，每一个结点可能有两个后续，因此需要寻找一种规律， 将层次形的二叉树序列转化为一个线性序列。 由递归定义可知，二叉树是由三个基本单元组成，即 ：根结点、左子树和右子树。因此，若能依次遍历这三部 分，便是遍历了整个二叉树。若以(，T，R分别表示遍历 左子树、访问根和遍历右子树，则可有六种遍历方案： TLR，LTR，LRT，TRL，RTL，RLT。通常限定先遍 历左子树，后遍历右子树。所以，二叉树的遍历主要指前 三种。6.3.1 二叉树遍历的递归算法 (1)前序遍历(

15、TLR)递归算法前序遍历(也可以称为前序遍历)二叉树的操作定义为：若二叉树为空，则空操作(不作任何操作)；否则(1)访问根结点。(2)前序访问左子树。(3)前序访问右子树。 算法6.1 前序遍历二叉树的递归算法。void prev(BiTNode *root) if(root!=NULL) printf(“%d,“,root-data);/* 访问根结点 */prev(root-lch);prev(root-rch);(2)中序遍历(LTR)递归算法 中序遍历二叉树的操作定义为：若二叉树为空，则空操作(不作任何操作)；否则，(1)中序访问左子树。(2)访问根结点。(3)中序访问右子树。 由中序遍历的定义，可得到中序遍历二叉树的递归算法如下： 算法6.2 中序遍历二叉树的递归算法。void mid(BiTNode *root) if(root!=NULL) mid(root-lch);printf(“%d,“,root-data);/* 访问根结点 */mid(root-rch);(3)后序遍历(LRT)递归算法 后序遍历二叉树的操作定义为：若二叉树为空，则空操作(不作任何操作)；否则，(1)后序访问左子树；(2)后序访问右子树；(3)访问根结点； 由后序遍历的定义，可得到后序遍历二叉树的递归算法如下。算法6.3 后序遍历二叉树的递归算法