树——二叉树基础

1. 前言 

    二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

 

2. 二叉树的定义

    二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

    二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。
    二叉树的五种基本形态如下图所示。

图 二叉树的五种基本形态

3. 二叉树的基本操作

(1)InitBiTree(&T);

    操作结果:构造空二叉树T。

(2)DestroyBiTree(&T);

    初始条件:二叉树T存在。

    操作结果：销毁二叉树T。

(3)CreateBiTree(&T,definition);

    初始条件:definition给出二叉树T的定义。

    操作结果：按definition构造二叉树。

(4)ClearBiTree(&T);

    初始条件:二叉树T存在。

    操作结果：将二叉树T清为空树。

(5)BiTreeEmpty(T);

    初始条件:二叉树T存在。

    操作结果：若T为空二叉树，则返回TRUE，否则返回FALSE。

(6)BiTreeDepth(T);

    初始条件:二叉树T存在。

    操作结果：返回二叉树T的深度。

(7)Root(T);

    初始条件:二叉树T存在。

    操作结果：返回二叉树T的根。

(8)Value(T,e);

    初始条件:二叉树T存在，e是T中某个结点。

    操作结果：返回e的值。

(9)Assign(T,&e,value);

    初始条件:二叉树T存在，e是T中某个结点。

    操作结果：结点e赋值为value。

(10)Parent(T,e);

    初始条件:二叉树T存在，e是T中某个结点。

    操作结果：若e是T的非根结点，则返回它的双亲，否则返回"空"。

(11)LeftChild(T,e);

    初始条件:二叉树T存在，e是T中某个结点。

    操作结果：返回e的左子女。若e无左子女，则返回"空"。

(12)RightChild(T,e);

    初始条件:二叉树T存在，e是T中某个结点。

    操作结果：返回e的右子女。若e无右子女，则返回"空"。

(13)InsertChild(T,p,LR,c);

    初始条件:二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。

    操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。P所指结点的原有左或右子树则成为c的右子树。

(14)DeleteChild(T,p,LR);

    初始条件:二叉树T存在，p指向T中某个结点，LR为0或1。

    操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。

(15)PreOrderTraverse(T,Visit());

    初始条件:二叉树T存在，Visit是对结点操作的应用函数。

    操作结果：先序遍历T，对每个结点调用函数Visit一次且仅一次。一旦Visit()失败，则操作失败。

(16)InOrderTraverse(T,Visit());

    初始条件:二叉树T存在，Visit是对结点操作的应用函数。

    操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦Visit()失败，则操作失败。

(17)PostOrderTraverse(T,Visit());

    初始条件:二叉树T存在，Visit是对结点操作的应用函数。

    操作结果：后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦Visit()失败，则操作失败。

 

4. 几种特殊的二叉树

（1）满二叉树(FullBinaryTree)

    一棵高度为k，并且含有2^k-1个结点的二叉树为满二叉树。因此，在满二叉树中，每一层结点都达到了最大个数。除最低层结点的度为0外，其他各层结点的度都为2。

    满二叉树的特点：

• 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
• 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。   

（2）完全二叉树(Complete BinaryTree)

    若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

完全二叉树的特点：

• 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
• 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
• 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。

图 特殊形态的二叉树

5. 二叉树的性质

性质1：二叉树第i层上的结点数目最多为2^i-1(i≥1)。

性质2：深度为k的二叉树至多有2^k-1个结点(k≥1)。

性质3：在任意-棵二叉树中，若终端结点的个数为n₀，度为2的结点数为n₂，则n_o=n₂+1。

性质4：具有n个结点的完全二叉树的深度为：

6. 二叉树的存储表示与实现

二叉树的存储结构有两种：顺序存储表示和链式存储表示。

（1）顺序存储表示

    按照顺序存储结构的定义，用一组地址连续的存储单元以此自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中，空缺表示不存在此结点。由此可见，这种顺序存储结构比较适用于完全二叉树，而不太适用于非完全二叉树。因为，在最坏的情况下，一个深度为k且只有k个节点的单支树（树中不存在度为2的结点）却需要长度为2k-1的一维数组。如下图所示：

图 完全二叉树的顺序存储表示

图 一般二叉树的顺序存储

    二叉树的顺序存储表示：

#define MAX_TREE_SIZE 100
//二叉树的最大结点数  
typedef ElemType SqBiTree[MAX_TREE_SIZE]
//0号单元存储根结点
SqBiTree bt; 

    二叉树顺序存储的优缺点:

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

（2）链式存储表示

二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lchild和rchild，分别指向该结点的左孩子和右孩子。结点的结构为：

图 二叉树链式存储结构

    其中，data表示值域，用于存储对应的数据元素，lchild和rchild分别表示左指针域和右指针域，分别用于存储左子女结点和右子女结点（即左、右子树的根结点）的存储位置（即指针）。

    对应C语言结点类型定义如下：

typedef char DataType； //用户可根据具体应用定义DataType的实际类型 
    typedef struct node{
          DataType data； 
          Struct node *lchild，*rchild； //左右孩子指针
      }BinTNode； //结点类型
    typedef BinTNode *BinTree；//BinTree为指向BinTNode类型结点的指针类型

 

    在一棵二叉树中，所有类型为BinTNode的结点，再加上一个指向开始结点(即根结点)的BinTree型头指针(即根指针)root，就构成了二叉树的链式存储结构，并将其称为二叉链表。

    下面左图所示二叉树的二叉链表如下面中图所示：

图 二叉树链式存储结构示意图

注意：
    ① 一个二叉链表由根指针root惟一确定。若二叉树为空，则root=NULL；若结点的某个孩子不存在，则相应的指针为空。
    ② 具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。

    经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针parent，形成一个带双亲指针的二叉链表。【例】上面右图是上面左图所示的二叉树的带双亲指针的二叉链表。