跳至正文
View Categories

1 min read

1. 二叉树的基本概念 #

二叉树（英语：Binary tree，简写成BT）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构[1]。通常分支被称作“左子树”或“右子树”。二元树的分支具有左右次序，不能随意颠倒。二叉树有5种基本的形态：

前面引入的树的术语也基本适用于二叉树，但二叉树也有很多不同，如：首先二叉树的每个节点至多只能有两个子节点，二叉树可以为空，二叉树一定是有序的，通过它的左右子树的关系体现出来。

2. 二叉树的性质 #

性质1 #

在二叉树的第i层上最多有2^(i-1)个节点（i>=1）。

证明：很简单，用归纳法：当i=1时，2^(i-1)=1显然成立；现在假设第i-1层时命题成立，即i-1层上有最多2^(i-2)个节点。由于二叉树的每个节点的度最多为2，故在第i层上的最大节点数为第i-1层的2倍，即2*2^(i-2)=2^(i-1)。

性质2 #

深度为k的二叉树至多有2^k-1个节点（k>=1）。

证明：在具有相同深度的二叉树中，仅当每一层都含有最大的节点数时，其树中节点数最多。因此利用性质1可得，深度为k的二叉树的节点数至多为：
2^0+2^1+···+2^(k-1)=2^k-1
故命题正确。
特别：一棵深度为k且有2^k-1个节点的二叉树称为满二叉树。如图1为深度为4的满二叉树，这种树的特点是每层上的节点数都是最大节点数。

可以对满二叉树的节点进行连续编号，约定编号从根节点起，自上而下，从左到右，由此引出完全二叉树的定义，深度为k，有n个节点的二叉树，当且仅当每个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时称为完全二叉树。

或者说，在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点，则此二叉树为完全二叉树。

图2就是一棵深度为4的，节点数为12的完全二叉树。

它有如下特征：叶子节点只能在层次最大的两层中出现；对任一节点，若其右分枝下的子孙的最大层次为m则在其左分枝下的子孙的最大层次必为m或m+1。图3中的两个树不是完全二叉树，请大家思考为什么？

性质3 #

对于任意一棵二叉树，如果其叶子节点数为n0，度为2的节点数为n2，则一定满足：n0=n2+1。

证明：因为二叉树中所有的节点的度均不大于2，所以节点总数（记为n）应等于0度的节点数n0、1度的节点数n1、2度的节点数n2之和：
式子1:n=n0+n1+n2
另一方面，1度的节点只有一个孩子，2度的节点有2个孩子，故二叉树中孩子节点总数是：n1+2*n2
树中仅有根节点不是任何节点的孩子，故二叉树中的节点总数又可表示为：
式子2；n=n1+2*n2+1
由式子1和2得到：
n0=n2+1

性质4 #

具有n个节点的完全二叉树的深度为：k=floor(logn)+1。
证明：假设深度为k，根据完全二叉树的定义，前面k-1层一定是满的，所以n>2^(k-1)-1。但n又满足n<=2^k-1，所以，2^(k-1)-1<n<=2^k-1，变换一下为：2^(k-1)-1<=n<2^k-1。以2为底取对数可以得到：k-1<logn<k，所以k=floor(logn)+1。

性质5 #

对于一棵n个节点的完全二叉树，对于任一节点（编号为i）有：

  1. 如果i=1，则节点为根，无父节点；如果i>1，则其父节点的编号为i/2。如果2*i>n，则节点i无左孩子（当然也无右孩子了），左孩子的编号为2*i。
  2. 如果2*i+1>n，则节点i无右孩子，否则，右孩子的编号为2*i+1。

我们只需验证一下即可，如图4所示：

3. 二叉树的存储 #

顺序存储结构 #

二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。
需要注意的是，顺序存储只适用于完全二叉树。对于普通的二叉树，必须先将其转化为完全二叉树，才能存储到顺序表中。满二叉树也是完全二叉树，可以直接用顺序表存储。
一棵普通二叉树转化为完全二叉树的方法很简单，只需要给二叉树额外添加一些结点，就可以把它”拼凑”成完全二叉树。如图 1 所示：

图 1 左侧是普通二叉树，右侧是转化后的完全（满）二叉树。解决了二叉树的转化问题，接下来学习如何顺序存储完全（满）二叉树。
所谓顺序存储完全二叉树，就是从树的根结点开始，按照层次将树中的结点逐个存储到数组中。

存储由普通二叉树转化来的完全二叉树也是如此，比如将图 1 中的普通二叉树存储到顺序表中，树中结点的存储状态如图 3 所示：

几个重要点:
1. i的左孩子——2i
2.  i的右孩子——2i+1
3. i的父节点——i/2向下取整
若完全二叉树中共有n个结点，则:
1. 判断i是否有左孩子——2i<=n
2. 判断i是否有右孩子——2i+1<=n
3. 判断i是否是叶子/分支结点——i>n/2向下取整
二叉树的顺序存储结构用 C 语言表示为：

#define MaxSize 100
struct TreeNode{
    ElemType value;  // 结点中的数据元素
    bool isEmpty;  // 结点是否为空
};
//定义一个长度为MaxSize的数组t，按照从上至下、从左至右的顺序依次存储完全二叉树的各个结点。
TreeNode t[MaxSize];

// 初始化时所有结点标记为空
for(int i=0;i<MaxSize;i++){
    t[i].isEmpty=true;
}

链式存储结构 #

介绍了二叉树的顺序存储结构，通过学习你会发现，其实二叉树并不适合用顺序表存储，因为并不是每个二叉树都是完全二叉树，普通二叉树使用顺序表存储或多或多会存在内存浪费的情况。

接下来我们学习二叉树的链式存储结构。

二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。二叉树的每个结点最多有两个孩子，因此，每个结点除了存储自身的数据外，还应设置两个指针分别指向左、右孩子结点。结点结构如下图所示：

所谓二叉树的链式存储，其实就是用链表存储二叉树，具体的存储方案是：从树的根节点开始，将各个节点及其左右孩子使用链表存储。

如图5所示，左边是一个普通的二叉树，右边为它的链式存储结构。
二叉树的链式存储结构用 C 语言表示为：

// 定义一棵空树
BiTNode root = NULL;
// 插入根结点
root = (BiTree)malloc(sizeof(BiTNode));
root->data={1};
root->lchild=NULL;
root->rchild=NULL;
// 插入新结点
BiTNode *p=(BiTNode *)malloc(sizeof(BiTNode));
p->data={2};
p->lchild=NULL;
p->rchild=NULL;
root->lchild=p;  // 作为根结点的左孩子

4. 二叉树的建立与删除 #

建立一棵二叉树 #

定义二叉树的节点：

#include<iostream>
#include<cstdlib>
#include<cstdio>
typedef struct node;
typedef node *tree;
struct node{
    char data;
    tree lchild, rchild;
};

采用递归的方式建立一棵二叉树：

void pre_crt(tree &bt){
    char ch;
    ch = getchar(); //bt 为指向根节点的指针，'¥'表示为空
    if(ch != '¥'){
        bt = new node;  //建立根节点
        bt -> data = ch;
        pre_crt(bt -> lchild);  //建立左子树
        pre_crt(bt -> rchild);  //建立右子树
    }
    else bt = NULL;  //是一棵空树
}

值得注意的是，这种建立树的方式，需要按照前序遍历的顺序输入，并且在遇到左子树或者右子树为空时，需要输入’¥’字符来终止递归，如要产生下面的一棵二叉树，则输入的顺序为：F, B, A,¥,¥, D, C, ¥,¥,E,¥,¥,G,¥,I, H,¥,¥,¥.

删除一棵二叉树 #

删除一棵二叉树相对简单，也是采用递归的算法，代码如下：

void dis(tree &bt){
    if(bt)
    dis(bt -> lchild);   //删除左子树
    dis(bt -> rchild);   //删除右子树
    delete bt;           //释放当前节点
}
您的感觉是什么