树和二叉树(二)

简介: 树和二叉树(二)

@[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):
在这里插入图片描述
后序线索化就留给大家自己画一画了。

相关文章
|
7月前
|
存储 算法 数据库
树中枝繁叶茂:探索 B+ 树、B 树、二叉树、红黑树和跳表的世界
树中枝繁叶茂:探索 B+ 树、B 树、二叉树、红黑树和跳表的世界
71 0
树和二叉树(三)
树和二叉树(三)
|
7月前
|
存储
树与二叉树
树与二叉树
|
存储
树和二叉树
树和二叉树
73 0
|
7月前
|
机器学习/深度学习 存储 算法
树【二叉树,红黑树,B树,B+树】
树【二叉树,红黑树,B树,B+树】
72 0
|
存储 人工智能 算法
树结构的讲解与二叉树的基本运用
树结构的讲解与二叉树的基本运用
|
存储 人工智能 BI
树和二叉树(一)
树和二叉树(一)
|
存储 算法
九、树和二叉树2
九、树和二叉树
九、树和二叉树2
|
存储 机器学习/深度学习 算法
九、树和二叉树
九、树和二叉树
九、树和二叉树