信息学数据结构趣谈树

1、数据结构趣谈树树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用。一、树的概述树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。（一）树的定义树是由一个或多个结点组成的有限集合，其中：必有一个特定的称为根(ROOT)的结点；剩下的结点被分成=0 个互不相交的集合 T1、T2、Tn，而且，这些集合的每一个又都是树。树 T1、T2、Tn 被称作根的(Subtree)。树中每

2、个分叉点称为结点，起始结点称为树根，任意两个结点间的连接关系称为树枝，结点下面不再有分枝称为树叶。结点的前趋结点称为该结点的“双亲”，结点的后趋结点称为该结点的“”或“孩子”，同一结点的“”之间互称“兄弟”。（二）树的表示树中每个结点的内容分两部分表示：结点的性质；结点的指针域。结点的性质：描述结点的必要数据。结点的指针域：指向结点的每一个孩子。指针域采用多重链表，又分为不定长度结点的多重链表与固定长度结点的多重链表。不定长度结点的多重链表表示树时，每个结点的指针域个数等于该结点的孩子的个数，其形式如下：每个指针域指向一个孩子，这样虽然不浪费空间，但由于结点长度不等，将给分配造成，给各种运算带

3、来极大不便。固定长度结点的多重链表表示树时，树中每个结点的指针域个数都相等于树中结点的最大度数，也就是说，不论结点的孩子多少，其长度均取最大长度。这样长度划一，处理问题简单方便，但对空间浪费很大。一种称之为二叉树为了寻求一种恰当的树的的树型结构。表示方法，DHILD1CHILD2CHILDn二、二叉树二叉树是一种十分重要的树型结构。它的特点是，树中的每个结点最多只有两棵，即树中任何结点的度数不大于。二叉树的有左右之分，而且，的左右次序是重要的，即使在只有一棵的情况下，也应分清是树还是右。（一）定义二叉树是结点的有限集合，这个集合或是空的，或是由一个根结点和两棵互不相交的称之为树和右的二叉树组成

4、。图 2 列出了二叉树的五种基本形态。图 2(a)为空二叉树；(b)只有一个结点的二叉树；(c)只有树的二叉树；(d)只有右的二叉树；(e)左右完全的二叉树。（二）满二叉树一棵深度为 K 的满二叉树，是有 2K-1 个结点的深度为 K 的二叉树。2K-1个结点是二叉树所能具有的最大结点个数。图 3 所示为一棵深度为的满二叉树。图 3图 4（三）完全二叉树对满二叉树，从第一层的结点(即根)开始，由下而上，由右，按顺序结点，便得到满二叉树的一个顺序表示。据此，完全二叉树定义如下：一棵具有个结点，深度为 K 的二叉树，当且仅当所有结点对应于深度为 K 的满二叉树中由至的那些结点时，该二叉树便是完全二

5、叉树。图 4 是一棵完全二叉树。（四）二叉树的二叉树一般采重链表作为其结构，表中每个结点都有三个域：数据域 DATA、左指针域 LCHILD 和右指针域 RCHILD。其中指针域 LCHILD 和RCHILD 分别指向其左孩子和右孩子。如图 5 所示。图 5二叉树结点的结构形式三、二叉树的遍历遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被一次，而且只被一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。设 L、D、R 分别表示遍历树、根结点和遍历右， 则对一棵二叉树的遍历有三种情况：DLR

6、（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。（一）先根次序遍历的递归定义若二叉树为空，则返回；否则，依次执行以下操作：根结点；按先根次序遍历树；按先根次序遍历右；返回。例：图 6 为表示表达式 （）/的二叉树。图 6根结点，得到字符。继而先序遍历此树时，首先树，按递归定义，先结点的的根结点，得到字符。类推结点的树，此时只有叶子。得到叶子后，叶子父结点的右，得到右的根结点字符。再字符父结点的右结点的树，得到叶子字符后，得到右根结点字符，。先序遍历完整棵树，得到序列为：这就是表达式的前缀表示或称波兰表示。/ （二）中根次序遍历的递归定义若二叉树为空，则返回；否则，作如下操作：按中根次序遍历树；根结点；按中根次序遍历右返回。；中序遍历图 6 二叉树时，引入栈，先将根结点字符入栈，按定义访问根结点的树，遇到的根结点字符入栈，结点的树，到达叶子字符，则字符为第一个的结点。接着，将栈顶字符出栈，根结点字符。继而其右，方法同上，根结点入栈，。这样，中序遍历完整棵树后，得到的序列为： / 这就是表达式的中缀表示。（三）后根次序遍历的递归定义若二叉树为空，则返回；否则，作如下操作：按后根次序遍历树；按后根次序遍历右；根结点；返回。对图 6 二叉树，后序遍历后得到