@[toc]

上篇文章介绍了树和二叉树的定义以及遍历方式。
本篇文章将讲解二叉树的算法实现。

二叉树的遍历算法

先序遍历算法

先序遍历的实现方式在前面已经说过了，比如下面的一棵二叉树：
在这里插入图片描述
我们需要先访问根结点A，然后以先序遍历的方式遍历左子树，左子树同样是一棵二叉树，以同样的方式访问根结点B，然后先序遍历B的左子树，会发现，这是一个递归的过程，所以我们可以通过递归实现。
先序遍历算法实现如下：

void PreOrderTraverse(BiTree t){
   
   
    //判断当前结点是否为空
    if(t == NULL){
   
   
        return;
    }
    //输出根结点
    printf("%c\t",t->data);
    //先序遍历左子树
    PreOrderTraverse(t->lchild);
    //先序遍历右子树
    PreOrderTraverse(t->rchild);
}

代码实现非常简单，但是需要一定的时间理解：
我们首先传入二叉树的根结点，根结点不为空，所以输出A，此时调用自身，将左孩子传入，此时将先序遍历左子树。
传入结点B依然不为空，此时输出B，然后又调用自身，将结点B的左孩子传入，此时将先序遍历结点B的左子树。
传入结点D依然不为空，此时输出D，然后又调用自身，将结点D的左孩子传入，此时左孩子为空，所以函数返回，返回后就执行先序遍历右子树，传入的右孩子仍然为空，此时继续返回，先序遍历结点B的右孩子。
以此类推，注意理解。

我们来测试一下，因为刚刚接触遍历算法，所以这里，我们通过一个比较笨的方式实现二叉树，然后调用先序遍历函数：

int main(){
   
   
    //创建根结点
    BiTree root = (BiTree) malloc(sizeof(BiNode));
    root->data = 'A';

    //创建根结点的左孩子
    root->lchild  = (BiTree) malloc(sizeof(BiNode));
    root->lchild->data = 'B';

    //创建根结点的右孩子
    root->rchild  = (BiTree) malloc(sizeof(BiNode));
    root->rchild->data = 'C';

    //创建根结点的左孩子的左孩子
    root->lchild->lchild  = (BiTree) malloc(sizeof(BiNode));
    root->lchild->lchild->data = 'D';

    //创建根结点的左孩子的右孩子
    root->lchild->rchild  = (BiTree) malloc(sizeof(BiNode));
    root->lchild->rchild->data = 'E';

    //根结点的右孩子无左右孩子
    root->rchild->lchild = NULL;
    root->rchild->rchild = NULL;

    //根结点的左孩子的左孩子无左右孩子
    root->lchild->lchild->lchild = NULL;
    root->lchild->lchild->rchild = NULL;

    //根结点的左孩子右孩子无左右孩子
    root->lchild->rchild->lchild = NULL;
    root->lchild->rchild->rchild = NULL;

    //先序遍历
    PreOrderTraverse(root);
    return 0;
}

运行结果：

A B D E C

中序遍历算法

中序遍历和后序遍历的算法就不用分析了，过程是一样的，只不过是操作根结点的顺序变了。
中序遍历算法实现如下：

void InOrderTraverse(BiTree t){
   
   
    //判断当前结点是否为空
    if(t == NULL){
   
   
        return;
    }
    //先序遍历左子树
    InOrderTraverse(t->lchild);
    //输出根结点
    printf("%c\t",t->data);
    //先序遍历右子树
    InOrderTraverse(t->rchild);
}

后序遍历算法

后序遍历算法实现如下：

void PostOrderTraverse(BiTree t){
   
   
    //判断当前结点是否为空
    if(t == NULL){
   
   
        return;
    }
    //先序遍历左子树
    PostOrderTraverse(t->lchild);
    //先序遍历右子树
    PostOrderTraverse(t->rchild);
    //输出根结点
    printf("%c\t",t->data);
}

非递归遍历算法

遍历思想

前面介绍了三种遍历算法，都是通过递归实现的，虽然递归实现的代码量非常少，但是递归较难理解，而且空间消耗大，所以这里我也介绍一下遍历算法的非递归实现，具体想用哪种办法就看自己了。

这里以中序遍历算法的非递归实现作为例子重点讲述。
当然思想还是一样的，我们需要优先遍历左子树，然后访问根结点，最后访问右子树，既然是这样，根结点我们就需要先保存下来，这里可以用栈实现。
比如下面的这棵二叉树：
在这里插入图片描述
如何实现非递归的中序遍历呢？

中序遍历算法是先遍历左子树，然后访问根结点的，所以一开始传入根结点A，我们不能访问，此时将根结点A入栈，然后遍历根结点A的左子树。
在这里插入图片描述
此时以同样的方式遍历左子树，遇到左子树的根结点B，同样不能访问，将根结点B入栈，然后遍历根结点B的左子树。

我们接着遍历结点B的左子树，同样将根结点D入栈。

此时结点D无左孩子，这样就可以访问根结点了，对栈进行出栈操作，因为栈的特性，此时出栈结点为D。
在这里插入图片描述
然后遍历根结点D的右子树，因为结点D无右孩子，此时需要退回到结点B，这时候结点B的左子树已经遍历完了，可以访问根结点了，对栈进行出栈操作，出栈结点为B。

此时根结点A的左子树也遍历完了，又进行出栈操作，出栈结点为A。
在这里插入图片描述
以同样的方式遍历右子树，遇到结点C，先入栈，然后访问其左子树，结点C无左孩子，所以结点C出栈，接着遍历右子树，以此类推。

遍历结果为：D B A C E

算法实现

实现思想讲解清楚了，接下来是算法实现，在实现这个算法之前我们还需要实现一个栈结构，这里采用顺序栈。

#define TElemType char
int top=-1;//top变量时刻表示栈顶元素所在位置
//构造结点的结构体
typedef struct BiTNode{
   
   
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;

//前序和中序遍历使用的进栈函数
void push(BiTNode** a,BiTNode* elem){
   
   
    a[++top]=elem;
}
//弹栈函数
void pop( ){
   
   
    if (top==-1) {
   
   
        return ;
    }
    top--;
}
//模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode* elem){
   
   
    printf("%c ",elem->data);
}
//拿到栈顶元素
BiTNode* getTop(BiTNode**a){
   
   
    return a[top];
}

//中序遍历非递归实现
void InOrderTraverse(BiTree Tree){
   
   
    BiTNode* a[20];//定义一个顺序栈
    BiTNode * p;//临时指针
    p=Tree;
    //当p为NULL并且栈为空时，表明树遍历完成
    while (p != NULL || top!=-1) {
   
   
        //如果p不为NULL，将其压栈并遍历其左子树
        if (p != NULL) {
   
   
            push(a, p);
            p=p->lchild;
        }
        //如果p==NULL，表明左子树遍历完成，需要遍历上一层结点的右子树
        else{
   
   
            p=getTop(a);
            pop();
            displayElem(p);
            p=p->rchild;
        }
    }
}

层次遍历算法

层次遍历算法是通过二叉树的层次决定的，如下面的一棵二叉树：
在这里插入图片描述
它的层次遍历结果为：A B C D E，即从上到下，从左到右进行遍历。
对于层次遍历，我们可以使用队列实现。
首先传入根结点A，此时将根结点A入队，然后就可以执行出队操作，出队结点为A；

出队之后判断根结点A是否有左右孩子，如果有，则将结点B、C分别入队，然后执行出队操作，由于队列的特性，出队结点为B；
在这里插入图片描述
结点B出队之后判断结点B是否有左右孩子，有左孩子，则入队，然后执行出队操作，出队结点为C；

继续判断结点C是否有左右孩子，结点C有右孩子E，将结点E入队，然后执行出队操作，出队结点为D；

判断结点D是否有左右孩子，结点D无左右孩子，直接执行出队操作，出队结点为E；
结点E也无左右孩子，而队列也已经空了，此时遍历完成。

该算法和刚才介绍的非递归遍历算法有异曲同工之妙，这里就不具体写出该算法了，大家可以尝试着自己实现一下。

先序遍历建立二叉树算法

在学习遍历算法的时候，还记得我们是如何建立二叉树的吗？

int main(){
   
   
    //创建根结点
    BiTree root = (BiTree) malloc(sizeof(BiNode));
    root->data = 'A';

    //创建根结点的左孩子
    root->lchild  = (BiTree) malloc(sizeof(BiNode));
    root->lchild->data = 'B';

    //创建根结点的右孩子
    root->rchild  = (BiTree) malloc(sizeof(BiNode));
    root->rchild->data = 'C';

    //创建根结点的左孩子的左孩子
    root->lchild->lchild  = (BiTree) malloc(sizeof(BiNode));
    root->lchild->lchild->data = 'D';

    //创建根结点的左孩子的右孩子
    root->lchild->rchild  = (BiTree) malloc(sizeof(BiNode));
    root->lchild->rchild->data = 'E';

    //根结点的右孩子无左右孩子
    root->rchild->lchild = NULL;
    root->rchild->rchild = NULL;

    //根结点的左孩子的左孩子无左右孩子
    root->lchild->lchild->lchild = NULL;
    root->lchild->lchild->rchild = NULL;

    //根结点的左孩子右孩子无左右孩子
    root->lchild->rchild->lchild = NULL;
    root->lchild->rchild->rchild = NULL;

    return 0;
}

可以看到，这个方法非常麻烦，但是建立算法又建立在遍历算法之上，所以我们应该先掌握遍历算法，再来学习建立算法。

先序遍历建立算法即通过一个先序的遍历序列建立出一棵二叉树，比如下面的一个先序序列：
A B C D E G F
需要注意的是，单凭这个先序序列并不能唯一确定一棵二叉树。
在这里插入图片描述
比如这两棵二叉树的先序遍历结果均为：A B C D E G F。
所以我们需要对这棵二叉树进行补充，补充一些空结点，然后按照顺序进行建立：

先序遍历建立二叉树算法实现如下：

BiTree CreateBiTreePre(){
   
   
    BiTree root;
    char ch;
    printf("请输入结点数据：\n");
    scanf("%c",&ch);
    getchar(); //接收一个回车
    if(ch == '#'){
   
   
        root = NULL;
    }else{
   
   
        //创建结点
        root = (BiTree) malloc(sizeof(BiNode));
        root->data = ch;
        //递归建立左子树
        root->lchild = CreateBiTreePre();
        //递归建立右子树
        root->rchild = CreateBiTreePre();
    }
    return root;
}

测试一下：

int main(){
   
   
    BiTree root;
    //先序建立二叉树
    root = CreateBiTreePre();

    printf("先序遍历:");
    PreOrderTraverse(root);
    printf("\n");
    printf("中序遍历:");
    InOrderTraverse(root);
    printf("\n");
    printf("后序遍历:");
    PostOrderTraverse(root);
    return 0;
}

运行程序，输入：A B C # # D E # G # # F # # #
运行结果：

先序遍历:A      B       C       D       E       G       F
中序遍历:C      B       E       G       D       F       A
后序遍历:C      G       E       F       D       B       A

遍历二叉树算法的应用

下面介绍一下遍历二叉树算法的应用。

复制二叉树

通过遍历一棵二叉树，我们能够将一棵二叉树复制到另一棵二叉树上。

BiTree CopyTree(BiTree t){
   
   
    BiTree newT;
     if(t == NULL){
   
    
         return NULL;
     }else{
   
   
         //创建新结点
          newT = (BiTree) malloc(sizeof(BiNode));
          if(newT == NULL){
   
   
              exit(-1);
          }
          //复制结点的数据域
         newT->data = t->data;
         //递归复制左子树
          newT->lchild=CopyTree(t->lchild);
          //递归复制右子树
          newT->rchild=CopyTree(t->rchild);
          return newT;
     }
}

中序和后序复制二叉树的实现与其类似，不重复讨论。

计算二叉树的深度

遍历二叉树算法还可以用于计算二叉树的深度，算法如下：

int Depth(BiTree t){
   
   
    int m,n;
    //判断二叉树是否为空
    if(t == NULL){
   
   
        return 0;        //深度为0
    }
    //计算左子树深度
    m = Depth(t->lchild);
    //计算右子树深度
    n = Depth(t->rchild);
    //判断左右子树哪棵树深度最大，最后记得加1(加的是根结点)
    if(m > n){
   
   
        return m + 1;
    }else{
   
   
        return n + 1;
    }
}

这些算法都比较简单，就不一一分析了，看代码注释应该就能够理解了。

计算二叉树的结点总数

遍历算法因为要访问二叉树中的每个结点，所以它还能够用于计算结点总数，算法实现如下：

int GetNodeCount(BiTree t){
   
   
    if(t == NULL){
   
       //若当前结点为NULL，返回0
        return 0;
    }
    //返回左子树结点数 + 右子树结点数 + 根结点
    return GetNodeCount(t->lchild) + GetNodeCount(t->rchild) + 1;
}

计算二叉树的叶子结点数

计算叶子结点数的方式和刚才的算法类似，下面是代码实现：

int GetLeafCount(BiTree t){
   
   
    if(t == NULL){
   
       //若当前结点为NULL，返回0
        return 0;
    }
    if(t->lchild == NULL && t->rchild == NULL){
   
   
        //若当前结点无左右孩子，则表明是叶子结点
        return 1;
    }
    //返回左子树叶子结点数 + 右子树叶子结点数
    return GetLeafCount(t->lchild) + GetLeafCount(t->rchild);
}

线索二叉树的由来

先来看下面这棵二叉树：
在这里插入图片描述
这是二叉树存储结构中的二叉链表，其优点是能够很方便地找到任意结点的左右孩子，然而，它也有缺点：一般情况下，无法直接找到某个结点在某种遍历序列下的前驱结点和后继结点。

为了能够方便地找到任意结点的前驱和后继结点，我们可以在结点中保存其前驱和后继的结点地址，但如果为其增设两个指针域显然会牺牲很多空间，为此，我们可以利用二叉链表中的空指针域。

假设一棵具有n个结点的二叉树，其一共有2n个指针域，而n个结点的二叉树有n - 1个孩子结点，也就是说，该二叉树一共使用了n - 1个指针域用来指向左右孩子，这样就有n + 1个指针域是空着的，我们刚好可以利用这些指针域，用它们指向结点的前驱或者后继结点。

如何利用二叉链表中的空指针域

对于一棵二叉树的二叉链表结构，若某个结点的左孩子为空，则将空的左孩子指针域指向其前驱结点；同理，若某个结点的右孩子为空，则将空的友好孩子指针域指向其后继结点。我们将这种改变指向的指针称为"线索"，加上了线索的二叉树称为线索二叉树。

看这样的一个例子，比如下面的一棵二叉树：
在这里插入图片描述
我们说二叉树的线索化是相对于某个遍历序列而言的，上面这棵二叉树的中序遍历结果为：C B E G D F A
则对于中序遍历序列来说，该如何实现线索化呢？

先看结点A，其右孩子指针域为空，此时我们应该利用起来这个空指针域，让其指向它的后继结点，而从中序遍历结果得知，结点A无后继结点，所以我们最后还是让结点A的右孩子指针域为空，不作处理。

再看结点C，其左右孩子指针域均为空，此时我们先处理左孩子指针域。从中序遍历结果得知，结点C无前驱结点，但其后继结点为B，所以我们不对左孩子指针域作处理，而让右孩子指针域指向结点B。
在这里插入图片描述
继续看结点E，其左孩子指针域为空，而其前驱结点为B，所以让其左孩子指针域指向结点B。

处理结点F和结点G的方式也是一样的，最后线索化完成的结果应为：

看到线索化后的二叉树，很多同学可能懵了，这么多的指针指向，到底哪些是指向前驱和后继结点的，哪些是指向孩子结点的呢？

为了区分，我们可以对二叉链表的结点结构增设两个标志域ltag和rtag，并作出如下约定：

ltag = 0，lchild指向该结点的左孩子
ltag = 1，lchild指向该结点的前驱
rtag = 0，rchild指向该结点的右孩子
rtag = 1，rchild指向该结点的后继

所以其结点结构应为：

typedef struct BiThrNode{
   
   
    char data;
    struct BiThrNode *lchild,*rchild;
    int ltag,rtag;    //标志域
}BiThrNode,*BiThrTree;

看下面的一棵二叉树：
在这里插入图片描述
对其进行先序线索化，先得出先序遍历结果：A B C D E，其线索化结果为：

其中序线索化结果为(中序遍历结果：B C A E D)：

后序线索化就留给大家自己画一画了。

树和二叉树(二)

二叉树的遍历算法

先序遍历算法

中序遍历算法

后序遍历算法

非递归遍历算法

遍历思想

算法实现

层次遍历算法

先序遍历建立二叉树算法

遍历二叉树算法的应用

复制二叉树

计算二叉树的深度

计算二叉树的结点总数

计算二叉树的叶子结点数

线索二叉树的由来

如何利用二叉链表中的空指针域

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

树和二叉树(二)

二叉树的遍历算法

先序遍历算法

中序遍历算法

后序遍历算法

非递归遍历算法

遍历思想

算法实现

层次遍历算法

先序遍历建立二叉树算法

遍历二叉树算法的应用

复制二叉树

计算二叉树的深度

计算二叉树的结点总数

计算二叉树的叶子结点数

线索二叉树的由来

如何利用二叉链表中的空指针域

热门文章

最新文章

相关电子书