喔嚯霍,二叉树的遍历,先序,中序,后序原来这么简单(附代码)!!!

简介: 喔嚯霍,二叉树的遍历,先序,中序,后序原来这么简单(附代码)!!!

二叉树的遍历

既然想要明白二叉树的遍历,那我们是不是要首先明白什么是二叉树呀?【手动狗头】

1.认识我们的二叉树兄弟

至于中间这多了一条腿的家伙,我打保票他肯定不是二叉树!!!【手动狗头】

听到二叉,那肯定是一个结点只有两个分支呀

那对于我们的二叉树我们又是怎么来储存,找相似结构!找相似结构!找相似结构!(重要的话说三遍)

有些小伙伴看不出,好家伙,这样呢!

因为2,4结点后面不是没有,那么就是空,于是我们不上NULL(空)是不是出来了,这样每一个结点都可以看作是

那我们之前的图是不是这样子的啦!!!

我们用结构体来表示

我们设立一个值来储存他结点的数值,用两个指针来指向下一个结点

typedef struct Tree{
 
 int data;          //  存放数据域
 struct Tree *lchild;     //  遍历左子树指针
 struct Tree *rchild;     //  遍历右子树指针
 
}Tree,*BitTree;

2.二叉树兄弟的存放

我们扩展和链接一下我们前面的知识,说到结构体,指针,NULL,无限月读(不断存储),首先想到什么?我们的链表好兄弟呀!当然当你学完这篇之后,我们还可以想到我们的二叉树兄弟啦【手动狗头】

回忆一下我们的链表,嗯~

是不是沿着一条边,一直存放下去,直到遇到了特定条件,为空时停止。那么在这里我们一样的,他还是我们用链表来存储储存的,别忘了我们的大杀器

递归!!!

BitTree CreateLink()
{
  int data;
  int temp;
  BitTree T;
  
  scanf("%d",&data);    //  输入数据
  
  if(data == -1){     //  输入-1 代表此节点下子树不存数据,也就是不继续递归创建
    
    return NULL;
  }else{
    T = (BitTree)malloc(sizeof(Tree));      //    
    T->data = data;               //    把当前输入的数据存入当前节点指针的数据域中
    
    printf("请输入%d的左子树: ",data);   
    T->lchild = CreateLink();         //    开始递归创建左子树
    printf("请输入%d的右子树: ",data);     
    T->rchild = CreateLink();         //    开始到上一级节点的右边递归创建左右子树
    return T;             //    返回根节点
  } 
  
}

他的基本逻辑是这样!

我们创建一个根结点,为我们的根结点赋值

我们有了一个1结点

然后T->lchild = CreateLink()我们链接我们的左结点,并回到我们一开始的时候,给我们的左节点赋值,有点类似于new,但是我们也别忘记了还有个T->rchild = CreateLink();

这一步的图解

好的,我们然后问你2结点的左节点了,重复上面的步骤

我们得到了

然后我们就可以,开始结束我们4号结点的赋值,当在此跳转到原来程序,询问你4号结点的左子树为多少时,我们输出-1,那么他的左节点为空,又不会执行我们的else,我们就会开始执行我们的右结点,问你4号结点的右子树为多少,我们输入-1;这个时候,我们开始来还我们前面的债务啦

先是

我们给2的右结点赋值为5,然后再次,问你5的左右结点是多少,和上面的方案是一样的,我们再次输入-1,这时就会开始给你的第一块红的开始赋值了,这是我最后的赋值结果

做到这一步的你超级棒啦,我们马上就OK啦!!!

我们开始遍历吧!!!

遍历的先序,中序,后序,先 中 后 指的是根的位置

1.先序(根 左 右)

先序我们掌握最基本的就好啦,就像这样(中序,后序也是可以的)

我们先序的结果是: 1(根)2(左)3(右)

为什么这没说呢?我们看这个长一点的图

我们先看个左边的小的

先序是不是2 4 5!

我们先看个右边的小的

是不是 3 6 7!

好的我们来看大的!合起来!

先序是:1(根) 245(左) 367(右)

看看代码吧!

//  先序遍历
void ShowXianXu(BitTree T)      //    先序遍历二叉树
{
  if(T==NULL)           //  递归中遇到NULL,返回上一层节点
  {
    return;
  }
  printf("%d ",T->data);
  ShowXianXu(T->lchild);      //  递归遍历左子树
  ShowXianXu(T->rchild);      //  递归遍历右子树
}

我们用的也是递归思想,我们不断地去通过ShowXianXu(T->lchild)指向下一级,同时还会预先留下ShowXianXu(T->rchild),来为我们实现左边的遍历,if用来判断是不是到达空结点 注意:T每一次的值都是不一样的喔!

你其实可以把这些看作:
根:printf("%d ",T->data);
左:ShowXianXu(T->lchild);
右:ShowXianXu(T->rchild);

2.中序 (左 根 右)

打好基本走遍天下都不怕!

中序是:2(左) 1(根) 3(右)

看看代码吧!

//  中序遍历
void ShowZhongXu(BitTree T)     //    先序遍历二叉树
{
  if(T==NULL)           //  递归中遇到NULL,返回上一层节点
  {
    return;
  }
  
  ShowZhongXu(T->lchild);     //  递归遍历左子树
  printf("%d ",T->data);
  ShowZhongXu(T->rchild);     //  递归遍历右子树
  
}

一样的一样的

你其实可以把这些看作:

左:ShowZhongXu(T->lchild);

根:printf("%d ",T->data);

右:ShowZhongXu(T->rchild);

3.后序 (左 右 根)

后序是:2(左) 3(右) 1(根)

代码:

//  后序遍历
void ShowHouXu(BitTree T)     //    后序遍历二叉树
{
  if(T==NULL)           //  递归中遇到NULL,返回上一层节点
  {
    return;
  }
  
  ShowHouXu(T->lchild);     //  递归遍历左子树
  ShowHouXu(T->rchild);     //  递归遍历右子树
  printf("%d ",T->data);
}

又是一样的一样的

你其实可以把这些看作:

左:ShowHouXu(T->lchild);

右:ShowHouXu(T->rchild);

根:printf("%d ",T->data);

over!!!

整体代码

#include<stdio.h>
#include<stdlib.h>
typedef struct Tree{
 
 int data;          //  存放数据域
 struct Tree *lchild;     //  遍历左子树指针
 struct Tree *rchild;     //  遍历右子树指针
 
}Tree,*BitTree;
BitTree CreateLink()
{
  int data;
  int temp;
  BitTree T;
  
  scanf("%d",&data);    //  输入数据
  
  if(data == -1){     //  输入-1 代表此节点下子树不存数据,也就是不继续递归创建
    
    return NULL;
  }else{
    T = (BitTree)malloc(sizeof(Tree));      //    
    T->data = data;               //    把当前输入的数据存入当前节点指针的数据域中
    
    printf("请输入%d的左子树: ",data);   
    T->lchild = CreateLink();         //    开始递归创建左子树
    printf("请输入%d的右子树: ",data);     
    T->rchild = CreateLink();         //    开始到上一级节点的右边递归创建左右子树
    return T;             //    返回根节点
  } 
  
}
//  先序遍历
void ShowXianXu(BitTree T)      //    先序遍历二叉树
{
  if(T==NULL)           //  递归中遇到NULL,返回上一层节点
  {
    return;
  }
  printf("%d ",T->data);
  ShowXianXu(T->lchild);      //  递归遍历左子树
  ShowXianXu(T->rchild);      //  递归遍历右子树
}
//  中序遍历
void ShowZhongXu(BitTree T)     //    先序遍历二叉树
{
  if(T==NULL)           //  递归中遇到NULL,返回上一层节点
  {
    return;
  }
  
  ShowZhongXu(T->lchild);     //  递归遍历左子树
  printf("%d ",T->data);
  ShowZhongXu(T->rchild);     //  递归遍历右子树
  
}
//  后序遍历
void ShowHouXu(BitTree T)     //    后序遍历二叉树
{
  if(T==NULL)           //  递归中遇到NULL,返回上一层节点
  {
    return;
  }
  
  ShowHouXu(T->lchild);     //  递归遍历左子树
  ShowHouXu(T->rchild);     //  递归遍历右子树
  printf("%d ",T->data);
}
int main()
{
  BitTree S;
  printf("请输入第一个节点的数据:\n");
  S = CreateLink();     //    接受创建二叉树完成的根节点
  printf("先序遍历结果: \n");
  ShowXianXu(S);        //    先序遍历二叉树
  printf("\n中序遍历结果: \n");
  ShowZhongXu(S);       //    中序遍历二叉树
  
  printf("\n后序遍历结果: \n");
  ShowHouXu(S);       //    后序遍历二叉树
  
  return 0; 
}
相关文章
|
1月前
二叉树遍历及应用
二叉树遍历及应用
44 0
|
1月前
|
Linux
数据结构实验之二叉树八:(中序后序)求二叉树的深度
数据结构实验之二叉树八:(中序后序)求二叉树的深度
|
1月前
|
算法
带你深入理解二叉树的遍历
带你深入理解二叉树的遍历
|
1月前
【二叉树遍历和练习】
【二叉树遍历和练习】
40 0
|
11月前
1364:二叉树遍历(flist)
1364:二叉树遍历(flist)
|
7月前
|
算法
25 二叉树的遍历
25 二叉树的遍历
19 0
|
10月前
二叉树遍历
二叉树遍历
|
存储
二叉树的遍历问题
二叉树的遍历问题
|
前端开发
前端知识案例-二叉树的遍历(前序 中序 后序)
前端知识案例-二叉树的遍历(前序 中序 后序)
56 0
前端知识案例-二叉树的遍历(前序 中序 后序)

热门文章

最新文章