树（tree）

树

目录

树

树型结构：

树的概念：

树的表示：

树结构的基本术语

二叉树的概念

二叉树的性质

二叉树的存储结构

三种二叉树的递归遍历算法

简单总结

---

树型结构：

        树型结构是以分支关系定义的层次结构，它是一种重要的非线性结构。
        树型结构在客观世界中广泛存在，例如人类的家庭族谱以及各种社会组织机构都可以用树形结构来表示，又如在计算机文件管理和信息组织方面也用到树形结构。

树的概念：

树（ tree ）是由一个或多个结点组成的有限集合T。
其中：
（1）一个特定的结点称为该树的根（root）结点 ;
（2）结点之外的其余结点可分为m（m ≥ 0）个互不相交的有限集合 T1 ,T2 ,......,Tm ，且其中每一个集合本身又是一棵树，称之为根的子树（subtree）。
注意：
树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。
注意：
（1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。
（2）树中所有结点可以有零个或多个后继结点。

在图 6.1 中是一棵由 11 个结点组成树 T 。其中 A 是根结点，其余结点分为三个互不相交的子集：T1 ={B,E,F}，T2 ={C,G}，T3 ={D,H,I,J,K}。T1 ,T2 ,T3 都是树根Ａ的子树，这三棵子树的根结点分别是B,C,D 。每棵子树本身也是一棵树，可继续划分。例如子树T3以D为根结点，它的其余结点又可分为三个互相交的子集T31 ={H}，T32 ={I,K}，T33 ={J}，而其中T31，T33可都认为是仅有一个根结点的子树。

树的表示：

树形图表示（树结构的主要表示方法）
树的树形图表示中：结点用圆圈表示，结点的名字写在圆圈旁边（有时亦可写在圆圈内）。

用该定义来分析上图所示的树：
图中的树由结点的有限集T={A，B，C，D，E，F，C，H，I，J}所构成，其中A是根结点，T中其余结点可分成三个互不相交的子集：
T1={B，E，F，I，J}， T2={C}， T3={D，G，H}。
T1、T2和T3是根A的三棵子树，且本身又都是一棵树。例如T1，其根为B，其余结点可分为两个互不相交的的子集T11={E}和T12={F，I，J}，它们都是B的子树。显然T11是只含一个根结点E的树，而T12的根F又有两棵互不相交的子树{I}和{J}，其本身又都是只含一个根结点的树。

树结构的基本术语

• 结点的度(Degree)：树中的一个结点拥有的子树数目。如：A结点的度为3
• 树的度：是指该树中结点的最大度数。如树T的度为3。
• 叶子结点(Leaf)或终端结点：度为零的结点。如：E I J C G H都是叶子结点
• 分支结点或非终端结点：度不为零的结点。如：A B F D都是分支结点
• 孩子结点或儿子：树中某个结点的子树之根。如A的孩子结点为B、C、D
• 双亲结点或父亲：孩子结点的上层结点。如B的双亲结点为A，J的父亲为F
• 兄弟结点(Sibling)：同一个双亲的孩子。如B C D为兄弟结点，E F为兄弟结点
• 结点的层数(Level)：从根起算，根的层数为1，它的孩子的层数为2……若某结点在第i层，它的孩子结点就在第i+1层。如A的层数为1、BCD的层数为2、IJ的层数为4
• 树的高度(Height)或深度(Depth)：树中结点的最大层数。如树T的高度为4
• 有序树(OrderedTree)：将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，二叉树就是有序树。

二叉树的概念

        二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。
        二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
这个定义是递归的。由于左、右子树也是二叉树， 因此子树也可为空树。图 6.3 中展现了五种不同基本形态的二叉树。

其中 (a) 为空树， (b) 为仅有一个结点的二叉树， (c) 是仅有左子树而右子树为空的二叉树， (d) 是仅有右子树而左子树为空的二叉树， (e) 是左、右子树均非空的二叉树。这里应特别注意的是，二叉树的左子树和右子树是严格区分并且不能随意颠倒的，图 6.3(c) 与图 6.3(d) 就是两棵不同的二叉树。

二叉树的性质

二叉树具有以下重要性质：

• 性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。
• 性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。
• 性质3 在任意一棵二叉树中，若叶子结点（即度为0的结点）的个数为n0，度为1的结点数为n1，度为2的结点数为n2，则no=n2+1。
  证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和：
  n=no+n1+n2
  由于有n个结点的二叉树总边数为n-1条，于是得：
  n-1=0n0+1n1+2*n2
  满二叉树和完全二叉树是二叉树的两种特殊情形。
  1、满二叉树(FullBinaryTree)
  一棵深度为k且有2k-1个结点的二又树称为满二叉树。
  满二叉树的特点：
  （1）每一层上的结点数都达到最大值。即如果高度确定，它是具有最多结点数的二叉树。
  （2）满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。
  　　【例】图6.4(a)是一个深度为3的满二叉树。

2、完全二叉树(Complete BinaryTree)
        若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。 完全二叉树的特点：
（1）满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
（2）在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
（3）在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。

二叉树的存储结构

二叉树的存储结构有多种，最常用的有两种：是顺序存储结构和链表存储结构。

• 顺序存储结构
  二叉树可以存放在一维数组之中，这是一种简单的顺序存储结构。请看如下语句：
  const int MAXSIZE 20：#define MAXSIZE 20
  typedef char DATATYPE;
  char BT[20];
  其中 BT 就是一维数组（向量），用它来存储一棵二叉树，每个数组元素存储树的一个结点的数据信息。假设让 BT[0] 闲置，让 BT[1] 存放根结点信息。假设按照自上而下、自左至右的顺序将图 6.4(a) 的满二叉树存入一维数组 bt ，可以发现图 6.4(a) 中结的编号恰好与数组元素的下标号相对应，详见 6.5 图。在BT数组中可以方便地由某结点BT[i]的下标i ，找到它的双亲结点BT[i/2] 或者它的左、右孩子结点 BT[2i]、BT[2i+1] 。例如 BT[2] 结点值为 B ，它的双亲结点是 bt[1] 值为 A ，左孩子结点是 bt[4] 值为 D ，右孩子结点是 bt[5] 值为 E 。

优点和缺点
　　① 对完全二叉树而言，顺序存储结构既简单又节省存储空间。
　　② 一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。如：最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点的存储空间。
　　③ 在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。

• 链式存储结构
  　　二叉树的链式存储结构主要是通过二叉链表来存储的。二叉链表的每个结点有一个数据域和两个指针域，一个指针指向左孩子，另一个指针指向右孩子。结点结构描述：

typedef int DATATYPE
typedef struct tagBTNODE
{
DATATYPE data; /* 数据域 */
struct tagBTNODE lchild; / 左指针域 */
struct tagBTNODE rchild; / 左指针域 */
}BTNODE;

对于如图 6.6(a) 中的二叉树T ，它的二叉链表存储结构如图6.6(b) 。 二叉树的遍历

所谓二叉树的遍历是指按某条搜索路径访问树中的每一个结点，使得每一个结点均被访问一次并且仅被访问一次。
从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后回到根结点。

三种二叉树的递归遍历算法

N(Node)、L(Left subtree)和R(Right subtree)
（1）先根遍历（NLR）：根左右
如果二叉树为空，则空操作。否则依次执行以下三个操作：
1>. 访问跟结点
2>. 先根遍历左子树
3>. 先根遍历右子树
算法实现如下：
void PreOrder(BTNODE *root)
{
if(root != NULL)
{
printf(“%d “, root ->data);
PreOrder(root ->lchild);
PreOrder(root ->rchild);
}
}
遍历结果如下：
A B D C E F
（2）中根遍历（LNR）：左根右
如果二叉树为空，则空操作。否则依次执行以下三个操作：
1>. 中根遍历左子树
2>. 访问根节点
3>. 中根遍历右子树
算法实现如下：
void InOrder(BTNODE *root)
{
if(root != NULL)
{
InOrder(root ->lchild);
printf(“%d “, root ->data);
InOrder(root ->rchild);
}
}
遍历结果如下：
D B A E C F
（3） 后根遍历（LRN）：左右根
如果二叉树为空，则空操作。否则依次执行以下三个操作：
1>. 后跟遍历左子树
2>. 后根遍历右子树
3>. 访问根节点
算法实现如下：
void PostOrder(BTNODE *root)
{
if(root != NULL)
{
PostOrder(root ->lchild);
PostOrder(root ->rchild);
printf(“%d “, root ->data);
}
}
遍历结果如下：
D B E F C A

简单总结

1、

2、

3、