数据结构什锦（四）——树：二叉树

这次我们来聊聊树，重点讨论了二叉树的性质。

---

什么是树

树是一种类似于链表的数据结构。但是不同于链表、栈、队列等线性结构，树是我们接触到的第一个非线性数据结构。它的每个节点指向的是一批节点，而不是单个节点，也就是一对多的关系。树结构可以用来表示图范畴中具有层次特性的结构。

在树的ADT中，元素之间的次序不再被强调。如果需要表示有序的信息，考虑采用链表等线性储存结构。

相关术语

• 树的根/root，指没有双亲的节点。一棵树中至多有一个根节点。
• 边/edge，表示的是从双亲到孩子的链接。
• 叶子节点/leaf，没有孩子的节点。
• 兄弟节点/sibling，相同双亲的孩子节点称为兄弟sibling。
• 祖先节点/ancestor，如果存在一条从根节点到节点p的一条路径，且节点q在这条路径上，那么q是p的一个祖先，节点p是q的一个子孙/descendant。
• 层/level，在指定深度的所有节点的集合称为树的层。根节点所在的层是第1层。（但是《数据结构与算法 经典问题解析》上认为根节点所在层是第0层）
• 节点的深度/depth，是指根节点到该节点的路径长度。
• 节点的高度/height，指该节点到最深节点的路径长度。
• 树的深度，所有节点深度的最大值。
• 树的高度，所有节点高度的最大值。树的高度和深度相等，但节点不一定。
• 节点的度，节点拥有子树的个数称为节点的度。
• 树的度，树中各节点度的最大值。一般我们将树的度为m的树称为m次树或者m叉树。
• 节点的大小/size，是指包括该节点在内的以及它子孙节点的个数。
• 斜树/skew tree，如果一棵树除了叶子节点外每一个节点都只有一个孩子节点，就称这棵树为斜树。如果全部是左孩子节点就是左斜树/left skew tree，如果全部是右孩子节点就是右斜树/right skew tree。
• 森林，几棵不相关的树的集合称为森林。

树的性质

1. 树中所有的节点数等于所有节点的度数加一。
2. 定义总节点数为n，n_i为度数为i的节点，则n=n₀+n₁+n₂+…+n_m。m为树的度。
3. 度为m的树中第i层上至多有m^i-1个节点（i≥1）。比如度为3的树第二层至多有3个节点。
4. 高度为h的m次数至多有m^h-1/m-1个节点（就是等比数列求和公式）Sn=a1(1-q^n)/(1-q)（q≠1)。

二叉树

如果树的度为2，我们就成称这棵树为二叉树。空树也是一棵合法的二叉树，我们将二叉树看做是由两棵互不相交的子树构成，分别称为左子树和右子树。

特殊的二叉树

严格二叉树/strict binary tree

一棵树中每个节点要么有两个孩子要么没有孩子，就是严格二叉树。

满二叉树/full binary free

如果一棵树中每个非叶子节点都刚好有两个孩子且所有叶子节点都处于同一层，就是满二叉树，同时也满足严格二叉树的定义。

完全二叉树/complete binary tree

我们先假设一棵树的高度为h，然后从根节点开始依次对节点进行编号（令根节点编号为1）。那么我们可以得到一个从1到n的完全序列（n为树的节点数）。在编号遇到空指针时，我们也应该给空指针进行编号（也就是没有孩子节点的节点）。

如果一棵二叉树的所有叶子节点的高度是h或h-1，并且得到的节点编号序列中没有遗漏任何一个数（即保证编号是一个完全序列），那么这棵二叉树是一个完全二叉树。其特点是叶子节点只可能在最下层和次下层出现，且最下层的叶子节点集中在树的左部。

二叉树的性质

假设二叉树的高度为h，定义根节点的高度为0。

可以推断出以下性质：

• 满二叉树的节点个数n为2^h+1-1。这是因为高度为h的满二叉树共有h+1层。而每一层均充满节点，因此n=2⁰+2¹+2²+…+2^h=2^h+1-1。
• 完全二叉树的节点个数介于最小值2^h和最大值2^h+1-1之间。
• 满二叉树的叶子节点个数为2^h。
• 具有n个节点的完全二叉树中有n+1个空链接（被浪费掉的指针）。

二叉树的结构

为了简单起见，我们假设二叉树所携带的数据类型为整形。一种表达二叉树的方法是，每个节点包括一个数据域与两个指针域，分别指向左孩子和右孩子。

struct BinaryTreeNode{
    int data;
    struct BinaryTreeNode *left;
    struct BinaryTreeNode *right;
}

二叉树的操作

主要操作

• 将一个元素插入到二叉树中
• 在二叉树中删除一个元素
• 在二叉树中搜索某个元素
• 遍历二叉树

辅助操作

• 求二叉树的大小
• 求二叉树的高度
• 求拥有节点数最多的层次
• 求给定的一对节点或更多节点的最早共同祖先/Least Common Ancestor，LCA

二叉树的应用

• 在编译器中用的表达树/expression tree
• 在数据压缩算法中的赫夫曼编码数/Huffman coding tree
• 二叉搜索树/Binary Search Tree，BST。可以实现在很多元素中以平均情况下O(log_n)的时间开销进行排序。
• 优先队列/Priority Queue，PQ。利用PQ可实现在很多元素中最坏情况下以对数时间开销去找出和删除其中的最小值/最大值。

二叉树的遍历

在链表等线性数据结构中，我们可以比较容易的实现对每一个元素的访问，但是在树结构中，访问元素存在着多种顺序。

树的遍历与树的搜索很像，因为后者的实现也依赖于前者遍历访问树的每一个元素。但是遍历是以特定的顺序在树中移动，此外，在树的遍历中所有节点都会被访问到；而在树的搜索中，搜索过程将在找到目标节点后终止。

可能的遍历方案

树的遍历从根节点开始，在每一个节点都有三个操作步骤，分别用三个字母表示就是：L（遍历左子树）、R（遍历右子树）、D（访问当前节点）。二叉树的遍历很容易用基于这种表示的递归方式来描述，在这种定义下有六种方法：LRD、LDR、DLR、DRL、RDL、RLD。

其实相对于节点来说，先搜索左边还是右边无关紧要，所以将搜索方法精简为三种：

• 先序（DLR）遍历
• 中序（LDR）遍历
• 后序（LRD）遍历
• 层次遍历，灵感来自于图的广度优先搜索算法（BFS），是另外一种遍历方式。

以下图为例开启后续的讨论。

先序遍历

先序遍历分为三步：

• 访问根节点
• 遍历左子树
• 遍历右子树

如此得到的节点访问顺序是：1,2,4,5,3,6,7。

用递归来实现先序遍历很简单。

void PreOrder(struct BinaryTreeNode*root){
    if(root){
        printf("%d",root->data);
        PreOrder(root->left);
        PreOrder(root->right);
    }
}

如果不采用递归结构，也可以实现。因为在访问该节点元素之后还要遍历其左右子树，我们需要保存其左右子树的信息之后再去遍历其他树。我们采用栈结构来实现这一点，因为栈结构的LIFO结构特性使得在逆序中可以得到返回的右子树信息。在访问其左子树前，现将该节点压入栈中，然后访问完左子树之后将节点从栈中弹出继续遍历其右子树。重复上述过程直到栈为空。

代码实现如下。

PreOrderNonRecursive(struct BinaryTreeNode*root) {
    struct Stack*S=CreateStack();
    while (1){
        while (root){
            //处理当前节点
            printf("%d",root->data);
            Push(&S,root);
            //如果左子树存在，就将其压入栈
            root=root->left;
        }
        if(IsEmptyStack(S)){
            break;
        }
        //表示当前节点，左子树处理完毕，下面开始处理右子树
        root= Pop(&S);
    }
    DeleteStack(&S);
}

中序遍历

在中序遍历中，根节点是在左右子树遍历之间进行访问的。中序遍历定义如下：

• 遍历左子树
• 访问根节点
• 遍历右子树

如此操作得到的访问顺序是：4,2,5,1,6,3,7。

递归实现如下：

void InOrder(struct BinaryTreeNode*root){
    if(root){
        InOrder(root->left);
        printf("%d",root->data);
        InOrder(root->right);
    }
}//和前面的思路基本一样

中序遍历的非递归算法和先序遍历的实现非常相似，唯一的区别就是访问元素的时间发生在了元素出栈时，这时意味着元素的左子树已经处理完毕，实现代码如下。

InOrderNonRecursive(struct BinaryTreeNode*root) {
    struct Stack*S=CreateStack();
    while (1){
        while (root){
            Push(&S,root);
            //访问左子树，并继续将左子树的根压入栈中
            root=root->left;
        }
        if(IsEmptyStack(S)){
            break;
        }
        root= Pop(&S);
        printf("%d",root->data);//出栈后，处理当前节点
        //表示左子树，当前节点均处理完毕，现在开始处理右子树。
    }
    DeleteStack(&S);
}

后序遍历

后续遍历定义如下：

• 遍历左子树
• 遍历右子树
• 访问根节点

得到的访问序列为：4,5,2,6,7,3,1。

递归实现思路一样，代码如下。

void PostOrder(struct BinaryTreeNode*root){
    if(root){
        InOrder(root->left);
        InOrder(root->right);
        printf("%d",root->data);
    }
}//和前面的思路基本一样

后序遍历采用非递归实现则比较复杂，因为每个节点会被访问两次：在遍历左节点时我们会访问该节点，遍历右节点时会访问该节点。当第二次访问结束时，我们才能处理该节点，那么问题来了，当我们返回到该节点时我们要怎么判断是通过遍历完左子树访问的还是遍历完右子树访问到的呢？

我们不妨定义一个previous节点和一个current节点，前者用来储存上一个访问的节点，后者则假设是当前的栈顶节点。

当previous节点是current的parent节点时，我们判断current节点是否存在左子树。如果存在，则继续遍历左子树（即将current的左孩子压入栈）；如果不存在，则判断是否存在右子树；如果不存在右孩子（即为叶子节点），弹出该节点进行处理。

当previous节点是current的左孩子节点时，说明我们是从处理完左子树返回的该节点。检查该节点是否有右孩子：如果有，则继续遍历右孩子（将右孩子压入栈），否则弹出该数据。

当previous节点是current的右孩子节点时，说明我们是从处理完右子树返回的该节点，此时可以直接弹出该元素进行处理。

代码实现如下。

void PostOrderNonRecursive(struct BinaryTreeNode*root){
    if(!root)
        return;
    struct Stack *S=CreateStack();
    Push(&S,root);
    struct BinaryTreeNode*previous=NULL;
    while (!IsEmptyStack(S)){
        struct BinaryTreeNode *current=Pop(&S);
        if(!previous||previous->left==current||previous->right==current){
            //如果当前节点为根节点或者previous节点为当前节点的父母节点。
            if(current->left)
                Push(&S,root->left);
            else if(current->right)
                Push(&S,root->right);
        } else if(current->left==previous){
            //如果是从左节点返回的
            if(current->right)//判断是否存在右孩子
                Push(&S,current->right);
            else{//如果是右节点，直接处理并弹出栈
                printf("%d",root->data);
                Pop(&S);
            }
        }
        previous=current;
    }
}

层次遍历

层次遍历定义如下：

• 访问根节点
• 在遍历l层节点的同时，将l+1层的节点依次插入列中。
• 访问下一层的所有节点
• 重复上述过程直到所有层上的节点均被访问为止。

对上图给出的例树进行层次遍历，得到的节点访问序列为：1,2,3,4,5,6,7。

代码实现如下。

void LevelOrder(struct BinaryTreeNode*root){
    struct BinaryTreeNode*temp;
    struct Queue*Q=CreatQueue();
    if(!root)
        return;
    EnQueue(Q,root);
    while (!IsEmptyQueue(Q)){
        temp= DeQueue(Q);//弹出一个节点
        printf("%d",root->data);//处理节点
        //存入下一层节点
        if(temp->left)
            EnQueue(Q,temp->left);
        if(temp->right)
            EnQueue(Q,temp->right)
    }
    DeleteQueue(Q);
}

二叉树的问题集

由于版面限制（懒），就不给出非递归算法的实现了（逃）。

查找二叉树中的最大元素

一个简单的思路是分别遍历其左右子树找出两个最大值，然后再比较这两者和根节点，取三者的最大值。借助递归可以很容易的实现算法。

代码实现如下。

int FindMax(struct BinaryTreeNode*root){
    int root_val,left,right,max=INT_MIN;
    if(root){
        root_val=root->data;
        left= FindMax(root->left);
        right= FindMax(root->right);
        if(left>right)
            max=left;
        else max=right;
        if(root_val>max)
            max=root_val;
    }
    return max;
}

搜索二叉树中特定的元素

给定一棵二叉树，判断节点的值是否为检索值，是则返回1，否则一直向下递归检索直到找到为止。

代码实现如下。

int FindInBinaryTreeUsingRecursion(struct BinaryTreeNode*root,int data){
    int temp;
    if(root==NULL)//如果此时根为空就返回0
        return 0;
    else{
        if(root->data==data)//判断是否找到元素
            return 1;
       else {
           //返回左子树根的值，一直向下检索
            temp = FindInBinaryTreeUsingRecursion(root->left, data);
            if (temp != 0)
                return temp;
            //左子树检索完毕则返回右子树的检索值
            else return (FindInBinaryTreeUsingRecursion(root->right, data));
        }
       }
    }
    return 0;
}

在二叉树中插入元素

利用层次遍历将节点插入一个无左孩子或右孩子的指针域中。

代码实现如下。

void InsertInBinaryTree(struct BinaryTreeNode*root,int data){
    struct Queue*Q;//层次遍历储存队列
    struct BinaryTreeNode*temp;//临时节点
    struct BinaryTreeNode*newNode;//待插入节点
    newNode=(struct BinaryTreeNode*) malloc(sizeof (struct BinaryTreeNode));
    newNode->left=newNode->right=NULL;//初始化待插入节点
    newNode->data=data;
    if(newNode==NULL){//如果新节点申请错误
        printf("Memory Error\n");
        return;
    }
    if(!root){//如果树不存在，直接把根节点变成新节点。
        root=newNode;
        return;
    }
    //正式开始准备遍历插入
    Q=CreatQueue();
    EnQueue(Q,root);//将根节点置入队列
    while (!IsEmptyQueue(Q)){
        temp= DeQueue(Q);
        if(temp->left)
            EnQueue(Q,temp->left);//依次遍历节点的所有子树
        else{
            //如果节点左子树不存在，说明可插入
            temp->left=newNode;
            DeQueue(Q);
            return;
        }
        if(temp->right)
            EnQueue(Q,temp->right);
        else{
            temp->right=newNode;
            DeQueue(Q);
            return;
        }
        //结合队列先进先出的性质，元素会依次添加到树中
    }
    DeleteQueue(Q);
}

删除二叉树

要删除一棵二叉树，在删除它的双亲节点前必须要删干净它的孩子节点，所以采用后续遍历法遍历每一个节点后对它进行删除操作。

实现代码如下。

void DeleteBinaryTree(struct BinaryTreeNode*root){
    if(root==NULL)
        return;
    DeleteBinaryTree(root->left);
    DeleteBinaryTree(root->right);
    free(root);
}

---

完结！当然也许后续可能会填坑二叉树的其他算法~O(∩_∩)O。