数据结构之二叉树

概要

参考《大话数据结构》，把常用的基本数据结构梳理一下。

本节介绍二叉树。

定义

  二叉树（Binary Tree）是 \(n\) （\(n \geqslant 0\)）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

二叉树的特点：

• 每个结点最多有两棵子树，所以二叉树中不存在度大于 \(2\) 的结点。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

  所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

  在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

  对一棵具有 \(n\) 个结点的二叉树按层序编号，如果编号为 \(i\) （\(1 \leqslant i \leqslant n\)）的结点与同样深度的满二叉树中编号为 \(i\) 的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。如图：

注意：首先满二叉树一定是一棵完全二叉树，但完全二叉树又不一定是满的，其次按层序编号相同的结点是一一对应的。从这里得出一些完全二叉树的特点：

• 叶子结点只能出现在最下两层
• 最下层的叶子一定集中在左部连续位置
• 倒数二层，若有叶子结点，一定都在右部连续位置
• 如果结点度为 \(1\)，则该结点只有左孩子，即不存在只有右子树的情况
• 同样结点数的二叉树，完全二叉树的深度最小

二叉树的性质

  性质 1： 在二叉树的第 \(i\) 层上至多有 \(2^{i-1}\) 个结点（\(i \geqslant 1\)）。

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

  性质 3： 对任何一棵二叉树 \(T\)，如果其终端结点数为 \(n_0\)，度为 \(2\) 的结点数为 \(n_2\)，则 \(n_0 = n_2 +1\).

说白了就是叶子结点数比度为 \(2\) 的结点数多一个。我们设 \(n_1\) 为度是 \(1\) 的结点数。则树 \(T\) 的结点总数 \(n=n_0+n_1+n_2\). 我们换个角度数一数树的连接线数，度为 \(1\) 的分支线为 \(1\) 条，度为 \(2\) 的分支线为 \(2\) 条，即共 \(n_1+2n_2\) 条，又显然树的连接树为结点总数减去 \(1\)，即 \(n-1 = n_1+ 2n_2\)，即 \(n_0 = n_2 +1\).

  性质 4： 具有 \(n\) 个结点的完全二叉树的深度为 \(floor(\log_2n)+1\)（\(floor(x)\) 表示不超过 \(x\) 的最大整数）。

  性质 5： 如果对一棵有 \(n\) 个结点的完全二叉树（其深度为 \(floor(\log_2n)+1\)）的结点按层序编号（从第一层到 \(floor(\log_2n)+1\) 层，每层从左到右），对任一结点 \(i\)（\(1 \leqslant i \leqslant n\)）有：

1. 如果 \(i=1\)，则结点 \(i\) 是二叉树的根，无双亲；如果 \(i>1\)，则其双亲是结点 \(floor(i/2)\).
2. 如果 \(2i>n\)，则结点 \(i\) 无左孩子（结点 \(i\) 为叶子结点）；否则其左孩子是结点 \(2i\).
3. 如果 \(2i+1>n\)，则结点 \(i\) 无右孩子，否则其右孩子是结点 \(2i+1\).

可以与上图结点理解。

二叉树的存储结构

二叉树的顺序存储结构

二叉树的顺序存储结构是用一维数组存储二叉树的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系。比如下面一棵完全二叉树：

将这棵二叉树存入到数组中，相应的下标对应其同样的位置，如下图：

对于一般的二叉树，尽管层序编号不能反映逻辑关系，但是可以将其按完全二叉树编号，只不过，把不存在的结点设置为空就行了。但是像极端的情况比如深度为 \(k\) 的右斜树，它只有 \(k\) 个结点，却需要分配 \(2^k-1\) 个存储单元空间，造成了极大的空间浪费，所以顺序存储结构一般只用于完全二叉树。

二叉链表

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。如图：

其中 data 是数据域， lchild 和 rchild 都是指针域，分别存放指向左孩子和右孩子的指针。二叉链表的结点结构定义代码如下：

typedef int TElemType; // TElemType 类型根据实际情况而定，这里假设为 int

struct BiTNode
{
    TElemType data;
    BiTNode *lchild, *rchild;
};

如果有需要，还可以再增加一个指向双亲的指针域，那样就称之为三叉链表。

遍历二叉树

  二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

二叉树的遍历方式很多，如果我们限制了从左到右的习惯方式，那么主要分为四种：

1. 前序遍历。规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如图，遍历顺序为：ABDGHCEIF.
   

   

2. 中序遍历。规则是若二叉树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树。如图，遍历顺序为：GDHBAEICF.
   

   

3. 后序遍历。规则是若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。如图，遍历顺序为：GHDBIEFCA.
   

   

4. 层序遍历。规则是若二叉树为空，则空操作返回，否则从树的第一层，也就是从根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。如图，遍历顺序为：ABCDEFGHI.
   

   

二叉树树的建立与遍历代码实现

如果我们要在内存中建立一个如下左图这样的二叉树，为了能让每个结点确认是否有左右孩子，我们对它进行扩展，就右图的样子，也就是将二叉树中每个结点的空指针引出一个虚结点，其值为一个特定值，比如“#”。我们称这种处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树。比如右图的遍历序列就为 AB#D##C##.

有了这样的准备就可以着手建立二叉树了。创建二叉树同遍历方法一样，也有不同的创建方法。现在我们用前序实现二叉树的建议。代码如下：

#include<iostream>
#include<cstdio>  //getchar()

using namespace std;

typedef char TElemType; // TElwmType 类型根据实际情况而定，这里假设为 int

struct BiTNode
{
    TElemType data;
    BiTNode *lchild, *rchild;
};

void CreateBiTree(BiTNode* (&T))  //这里传入的是指针的引用,因为牵扯到修改指针的值
{
    //读入字符串 ch, 前序构造树
    //cout<<"请输入创建一棵二叉树的结点数据"<<endl;
    TElemType ch = getchar();
    //cin>>ch;
    if (ch == '#') //其中getchar（）为逐个读入标准库函数
        T = NULL;
    else
    {
        T = new BiTNode;//产生新的子树
        T->data = ch;
        CreateBiTree(T->lchild);//递归创建左子树
        CreateBiTree(T->rchild);//递归创建右子树
    }
}

void PreOrderTraverse(BiTNode* T)
{
    //前序遍历
    if(T)  //结点不为空时执行
    {
        cout<< T->data;
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
    else
        cout<<"";
}

void InOrderTraverse(BiTNode* T)
{
    //中序遍历
    if(T)  //结点不为空时执行
    {
        InOrderTraverse(T->lchild);
        cout<< T->data;
        InOrderTraverse(T->rchild);
    }
    else
        cout<<"";
}

void PostOrderTraverse(BiTNode* T)
{
    //后序遍历
    if(T)  //结点不为空时执行
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        cout<< T->data;
    }
    else
        cout<<"";
}
int main()
{
    //const char* ch = "AB#D##C##";
    BiTNode *T;

    cout<<"创建树结构，请输入字符，‘#’ 代表空："<<endl;
    CreateBiTree(T);  //输入 AB#D##C##
    cout<<"创建完毕"<<endl;
    cout<<T->data<<endl;
    cout<<"前序遍历结果："<<endl;
    PreOrderTraverse(T);//输出 ABDC
    cout<<endl;

    cout<<"中序遍历结果："<<endl;
    InOrderTraverse(T); //输出 BDAC
    cout<<endl;

    cout<<"后序遍历结果："<<endl;
    PostOrderTraverse(T);//输出 DBCA
    cout<<endl;

    return ;
}

上边主要的疑惑是指针的引用，暂时先参考二叉树建立，指针问题. 遇到修改指针的得注意了。