数据结构 二叉树

如题所述

先介绍一下树：
1.树的定义
树是一种常见的非线性的数据结构。树的递归定义如下：
树是n(n>0)个结点的有限集，这个集合满足以下条件：
⑴有且仅有一个结点没有前件（父亲结点），该结点称为树的根；
⑵除根外，其余的每个结点都有且仅有一个前件；
⑶除根外，每一个结点都通过唯一的路径连到根上。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后件（儿子结点）；
2、结点的分类
在树中，一个结点包含一个元素以及所有指向其子树的分支。结点一般分成三类
⑴根结点：没有前件的结点。在树中有且仅有一个根结点。
⑵分支结点：除根结点外，有后件的结点称为分支结点。分支结点亦是其子树的根；
⑶叶结点：没有后件的结点称为树叶。由树的定义可知，树叶本身也是其父结点的子树。
根结点到每一个分支结点或叶结点的路径是唯一的。
3、有关度的定义
⑴结点的度：一个结点的子树数目称为该结点的度。显
然，所有树叶的度为0。
⑵树的度：所有结点中最大的度称为该树的度。4、树的深度（高度）
树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的后件在第二层，其余各层依次类推。即若某个结点在第k层，则该结点的后件均处在第k+1层。图（b）中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。
5、有序树和无序树
按照树中同层结点是否保持有序性，可将树分为有序树和无序树。如果树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树；如果同层结点的次序任意，这样的树称为无序树。
 6、树的表示方法
树的表示方法一般有两种：
  ⑴自然界的树形表示法：用结点和边表示树，例如上图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。
 ⑵括号表示法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可写成如下形式
（r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））
7、树的存储结构一般有两种
⑴静态的记录数组。所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n(n为树的度)的数组，分别存储该结点的每一个儿子的下标
⑵动态的多重链表。由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n 为树的度)个指针域共n+1个域组成

下面是有关二叉树的内容：
二叉树的概念
二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个后件，且其子树有左右之分（次序不能任意颠倒）。
1、二叉树的递归定义和基本形态
二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：
⑴有一个特定的结点称为根；
⑵余下的结点分为互不相交的子集L和R，其中R是根的左子树；L是根的右子树；L和R又是二叉树；
由上述定义可以看出，二叉树和树是两个不同的概念
⑴树的每一个结点可以有任意多个后件，而二叉树中每个结点的后件不能超过2；
⑵树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后件为左儿子，右后件为右儿子。
2、二叉树的两个特殊形态
⑴满二叉树： 如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。可以验证具有n个叶结点的满二叉树共有2n-1个结点。
⑵完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树
3、二叉树的三个主要性质
性质1：在二叉树的第i（≥1）层上，最多有2i-1个 结点
证明：我们采用数学归纳法证明：当i=1时只有一个根结点，即2i-1=20=1，结论成立。假设第k(i=k)层上最多有2k-1个结点，考虑i=k+1。由归纳假设，在二叉树第k层上最多有2k-1个结点，而每一个结点最多有两个子结点，因此在第k+1层上最多有2．2k-1=2(k+1)-1=2i，结论成立。综上所述，性质1成立。
性质2：在深度为k(k≥1)的二叉树中最多有2k-1个 结点。
证明：由性质1，在二叉树第i层上最多有2i-1个结点，显然，第1层¨第k层的最多结点数为 个结点。证毕。
性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。
证明：设n0为二叉树的叶结点数；n1为二叉树中度为1的结点数；n2为二叉树中度为2的结点数，显然n=n0+n1+n2 （1）
由于二叉树中除了根结点外，其余每个结点都有且仅有一个前件。设 b为二叉树的前件个数，n=b+1（2）
所有这些前件同时又为度为1和度为2的结点的后件。因此又有b=n1+2n2 (3)
我们将（3）代入（2）得出n=n1+2n2+1 (4)
比较（1）和（4），得出n0=n2+1,即叶子数比度为2的结点数多1
4、普通有序树转换成二叉树
普通树为有序树T，将其转化成二叉树T’的规则如下：
⑴T中的结点与T’中的结点一一对应，即T中每个结点的序号和值在T’中保持不变；
⑵T中某结点v的第一个儿子结点为v1，则在T’中v1为对应结点v的左儿子结点；
⑶T中结点v的儿子序列，在T’中被依次链接成一条开始于v1的右链；
由上述转化规则可以看出，一棵有序树转化成二叉树的根结点是没有右子树的，并且除保留每个结点的最左分支外，其余分支应去掉，然后从最左的儿子开始沿右儿子方向依次链接该结点的全部儿子。
5、二叉树的存储结构
将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括
⑴一个数据域（data）；
⑵三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。
满二叉树和完全二叉树一般采用顺序存储结构
对于一般的二叉树，通常采用链式分配，即用二重链表表示一般的二叉树。这种链式分配即可以采用静态数据结构（数组），又可以采用动态数据结构（指针）。如果二叉树的存储需求量超过64Kb，则采用后者。由于二叉树中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域：
⑴值域： data
⑵左指针域： lch
⑶右指针域： rch
这种链表也称为二叉链表。二叉链表头指针bt指向二叉树的根结点
6、二叉树的遍历
二叉树遍历的定义：按照一定的规律不重复地访问(或取出结点中的信息，或对结点作其它的处理)二叉树中的每一个结点。
二叉树遍历的顺序：如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!=6）组合：LDR、 LRD、 DLR、 DRL、RDL、 RLD。若再限定先左后右的次序，则只剩下三种组合：LDR（中序遍历）、LRD（后序遍历）、DLR（前序遍历）。
前序遍历的规则如下：
若二叉树为空，则退出。否则
⑴访问处理根结点；
⑵前序遍历左子树；
⑶前序遍历右子树；
特点：由左而右逐条访问由根出发的树支 （回溯法的基础）
中序遍历的规则：
若二叉树为空，则退出；否则
⑴中序遍历左子树；
⑵访问处理根结点；
⑶中序遍历右子树；
后序遍历的规则如下：
若二叉树为空，则退出；否则
⑴后序遍历左子树；
⑵后序遍历右子树；
⑶访问处理根结点；
特点：可统计任一个结点为根的子树的情况（例如子树的权和，最优策略的选择（博弈数））

温馨提示：内容为网友见解，仅供参考

当前网址：https://11.t2y.org/zz/48ssvs.html