数据结构学习笔记(十一)神奇的二叉树

1、二叉树的定义
2、二叉树的性质
3、二叉树的顺序存储结构
4、二叉树的链式存储结构

二叉树是一种重要的数据结构，与数组、向量、链表都是一种顺序容器，它们提供了按位置访问数据的手段。但是有一个缺点，它们都是按照位置来确定数据，想要通过值来获取数据，只能通过遍历的方式。而二叉树在很大程度上解决了这个缺点，二叉树是按值来保存元素，也按值来访问元素。

二叉树由一个个节点组成，一个节点最多只能有两个子节点，从根节点开始左右扩散，分左子节点和右子节点，向下一直分支。

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

一、二叉树的定义

二叉树（Binary Tree）是n（n≥0）个结点所构成的集合，它或为空树（n=0）；或为非空树，对于非空树T：

（1）有且仅有一个称之为根的结点；

（2）除根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。

二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点：

（1）二叉树每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）；

（2）二叉树的子树有左右之分，其次序不能任意颠倒。

二、二叉树的性质

1、二叉树中，第 i 层最多有 个结点。

2、如果二叉树的深度为 K，那么此二叉树最多有 -1 个结点。

3、二叉树中，终端结点数（叶子结点数）为 ，度为 2 的结点数为 ，则 =+1。

• 对于一个二叉树来说，除了度为 0 的叶子结点和度为 2 的结点，剩下的就是度为 1 的结点（设为 ），那么总结点 n=++。
• 同时，对于每一个结点来说都是由其父结点分支表示的，假设树中分枝数为 B，那么总结点数 n=B+1。而分枝数是可以通过 和 表示的，即 B=+2*。所以，n 用另外一种方式表示为 n=+2*+1。
• 两种方式得到的 n 组成一个方程组，就可以得出 =+1。

二叉树还可以继续分类，衍生出满二叉树和完全二叉树。

（一）满二叉树：如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。

如上图 2 所示就是一棵满二叉树。满二叉树除了满足普通二叉树的性质，还具有以下性质：

1、满二叉树中第 i 层的节点数为 -1 个。

2、深度为 k 的满二叉树必有 -1 个节点 ，叶子数为 -1。

3、满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。

4、具有 n 个节点的满二叉树的深度为 (n+1)。

（二）完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。

满二叉树的特点是：每一层上的结点数都是最大结点数，即每一层i的结点数都具有最大值 -1。可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左至右。由此可引出完全二叉树的定义。根据上面的图三，很容易判断两者的不同。

（1）叶子结点只可能在层次最大的两层上出现；

（2）对任一结点，若其右分支下的子孙的最大层次为m，则其左分支下的子孙的最大层次必为m或m+1。图4中（c）和（d）不是完全二叉树。

三、二叉树的顺序存储结构

二叉树的顺序存储，虽然树是非线性存储结构，但也可以用顺序表存储。需要注意的是，顺序存储只适用于完全二叉树。对于普通的二叉树，必须先将其转化为完全二叉树，才能存储到顺序表中。满二叉树也是完全二叉树，可以直接用顺序表存储。

所谓顺序存储完全二叉树，就是从树的根结点开始，按照层次将树中的结点逐个存储到数组中。

各个结点在顺序表中的存储状态如下图所示：

上面例子说的完全二叉树，那如果是普通二叉树呢？

图 6 左侧(a)是普通二叉树，右侧(b)是转化后的完全（满）二叉树。解决了二叉树的转化问题，接下来各个结点在顺序表中的存储状态如图 如下：

二叉树的顺序存储结构用 C 语言表示为：

#define NODENUM 7 //二叉树中的结点数量
#define ElemType int //结点值的类型
//自定义 BiTree 类型，表示二叉树
typedef ElemType BiTree[MaxSize];

（1）存储二叉树

void InitBiTree(BiTree T) {
    ElemType node;
    int i = 0;
    printf("按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:");
    while (scanf("%d", &node))
    {
        T[i] = node;
        i++;
    }
}

（2）查找某个结点的双亲结点的值

ElemType Parent(BiTree T, ElemType e) {
    int i;
    if (T[0] == 0) {
        printf("存储的是一棵空树\n");
    }
    else
    {
        if (T[0] == e) {
            printf("当前结点是根节点，没有双亲结点\n");
            return 0;
        }
        for (i = 1; i < NODENUM; i++) {
            if (T[i] == e) {
                //借助各个结点的标号(数组下标+1)，找到双亲结点的存储位置
                return T[(i + 1) / 2 - 1];
            }
        }
        printf("二叉树中没有指定结点\n");
    }
    return -1;
}

（3）查找某个结点的左孩子结点的值

ElemType LeftChild(BiTree T, ElemType e) {
    int i;
    if (T[0] == 0) {
        printf("存储的是一棵空树\n");
    }
    else
    {
        for (i = 1; i < NODENUM; i++) {
            if (T[i] == e) {
                //借助各个结点的标号(数组下标+1)，找到左孩子结点的存储位置
                if (((i + 1) * 2 < NODENUM) && (T[(i + 1) * 2 - 1] != 0)) {
                    return T[(i + 1) * 2 - 1];
                }
                else
                {
                    printf("当前结点没有左孩子\n");
                    return 0;
                }
            }
        }
        printf("二叉树中没有指定结点\n");
    }
    return -1;
}

（4）查找某个结点的右孩子结点的值

ElemType RightChild(BiTree T, ElemType e) {
    int i;
    if (T[0] == 0) {
        printf("存储的是一棵空树\n");
    }
    else
    {
        for (i = 1; i < NODENUM; i++) {
            if (T[i] == e) {
                //借助各个结点的标号(数组下标+1)，找到左孩子结点的存储位置
                if (((i + 1) * 2 + 1 < NODENUM) && (T[(i + 1) * 2] != 0)) {
                    return T[(i + 1) * 2];
                }
                else
                {
                    printf("当前结点没有右孩子\n");
                    return 0;
                }
            }
        }
        printf("二叉树中没有指定结点\n");
    }
    return -1;
}

顺序查找某个结点的双亲结点和孩子结点，用到了完全二叉树具有的性质：将树中节点按照层次并从左到右依次标号 1、2、3、...（程序中用数组下标+1 表示），若节点 i 有左右孩子，则其左孩子节点的标号为 2*i，右孩子节点的标号为 2*i+1。

虽然二叉树是非线性存储结构，但也可以存储到顺序表中。但顺序表只能存储完全二叉树，普通的二叉树必须先转化为完全二叉树之后才能用顺序表存储。实际场景中，并非每个二叉树都是完全二叉树，用顺序表存储普通二叉树或多或少存在空间浪费的情况。

四、二叉树的链式存储结构

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

所谓二叉树的链式存储，其实就是用链表存储二叉树，具体的存储方案是：从树的根节点开始，将各个节点及其左右孩子使用链表存储。例如图 1 是一棵普通的二叉树，如果选择用链表存储，各个结点的存储状态如下图所示：

由图 6可知，采用链式存储二叉树时，树中的结点由 3 部分构成（如图 3 所示）：

（1）指向左孩子节点的指针（Lchild）；

（2）节点存储的数据（data）；

（3）指向右孩子节点的指针（Rchild）；

C 语言表示节点结构的代码为：

typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;

（1）存储二叉树

void CreateBiTree(BiTree* T) {
    *T = (BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data = 1;
    (*T)->lchild = (BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data = 2;
    (*T)->rchild = (BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->data = 3;
    (*T)->rchild->lchild = NULL;
    (*T)->rchild->rchild = NULL;
    (*T)->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->lchild->data = 4;
    (*T)->lchild->rchild = NULL;
    (*T)->lchild->lchild->lchild = NULL;
    (*T)->lchild->lchild->rchild = NULL;
}

(2)后序遍历二叉树，释放树占用的内存

void DestroyBiTree(BiTree T) {
    if (T) {
        DestroyBiTree(T->lchild);//销毁左孩子
        DestroyBiTree(T->rchild);//销毁右孩子
        free(T);//释放结点占用的内存
    }
}

我们运行一下案例：

int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("根节点的左孩子结点为：%d\n", Tree->lchild->data);
    printf("根节点的右孩子结点为：%d\n", Tree->rchild->data);
    DestroyBiTree(Tree);
    return 0;
}

程序输出结果：

根节点的左孩子结点为：2
根节点的右孩子结点为：3

设计不同的结点结构可构成不同形式的链式存储结构，例如，在某些实际场景中，可能会做 "查找某节点的父节点" 的操作，这时可以在节点结构中再添加一个指针域，用于各个节点指向其父亲节点：

在不同的存储结构中，实现二叉树的操作方法也不同，如找结点x的双亲PARENT(T, e)，在三叉链表中很容易实现，而在二叉链表中则需从根指针出发巡查。由此，在具体应用中采用什么存储结构，除根据二叉树的形态之外还应考虑需进行何种操作。

【参考文献】数据结构(C语言版）、大话数据结构、算法导论、算法设计与分析基础。