二叉树三种遍历(动态图+代码深入理解)

简介: 二叉树三种遍历(动态图+代码深入理解)

一、图示理解(图片是一位前辈所留,在此感谢)


1、先序遍历


先序遍历可以想象成,小仙儿从树根开始绕着整棵树的外围转一圈,经过结点的顺序就是先序遍历的顺序


先序遍历结果:ABDHIEJCFKG



让我们来看下动画,和小仙儿一起跑两遍就记住啦,记住是绕着外围跑哦




2、中序遍历


中序遍历可以想象成,按树画好的左右位置投影下来就可以了


中序遍历结果:HDIBEJAFKCG



下面看下投影的过程动画,其实就是按左右顺序写下来就行了



3、后序遍历


后序遍历就像是剪葡萄,我们要把一串葡萄剪成一颗一颗的。


还记得我们先序遍历绕圈的路线么?


就是围着树的外围绕一圈,如果发现一剪刀就能剪下的葡萄(必须是一颗葡萄),就把它剪下来,组成的就是后序遍历了。


后序遍历结果:HIDJEBKFGCA



让我们来看下动画



4、层序遍历


层序遍历太简单了,就是按照一层一层的顺序,从左到右写下来就行了。


后序遍历结果:ABCDEFGHIJK



不知道通过这种方式,有没有觉得闭着眼睛都能写出前序、中序、后序 、层序了呀,不过这只是为了大家好理解,我想出的一种形象思维,为了用代码实现,我们还需要具体了解一下前序、中序、后序遍历。


二、深入理解三种遍历


来,让我们先把所有空结点都补上。


还记得我们先序和后序遍历时候跑的顺序么?按照这个顺序再跑一次,就是围着树的外围跑一整圈。


让我们来理解一下绕着外围跑一整圈的真正含义是:遍历所有结点时,都先往左孩子走,再往右孩子走。


观察一下,你有什么发现?


有没有发现,除了根结点和空结点,其他所有结点都有三个箭头指向它。


一个是从它的父节点指向它,一个是从它的左孩子指向它,一个是从它的右孩子指向它。


一个结点有三个箭头指向它,说明每个结点都被经过了三遍。一遍是从它的父节点来的时候,一遍是从它的左孩子返回时,一遍是从它的右孩子返回时。


其实我们在用递归算法实现二叉树的遍历的时候,不管是先序中序还是后序,程序都是按照上面那个顺序跑遍所有结点的。


先序中序和后序唯一的不同就是,在经过结点的三次中,哪次访问(输出或者打印或者做其他操作)了这个结点。有点像大禹治水三过家门,他会选择一次进去。


先序遍历顾名思义,就是在第一次经过这个结点的时候访问了它。就是从父节点来的这个箭头的时候,访问了它。


中序遍历也和名字一样,就是在第二次经过这个结点的时候访问了它。就是从左孩子返回的这个箭头的时候,访问了它。


后序遍历,就是在第三次经过这个结点的时候访问了它。就是从右孩子返回的这个箭头的时候,访问了它。


其实不管是前序中序还是后序,在程序里跑的时候都是按照同样的顺序跑的,每个结点经过三遍,第几遍访问这个结点了,就叫什么序遍历。


下面做一个实例吧




四种遍历代码


https://www.cnblogs.com/bigsai/p/11393609.html


三、代码实现加以理解


基础实例图(下面代码均围绕此展开)



我们先用代码基本实现一下遍历


void TraverseBiTree(BiTree T)
{
    if (T == NULL)
        return ;
    TraverseBiTree(T->lChild);
    TraverseBiTree(T->rChlid);
}


这个递归就能实现当遇到空指针时候返回,记住,每个结点先往左孩子走,再往右孩子走这个顺序。


如果我们想实现先序遍历,只需要在第一次经过这个结点的时候访问(输出)他就可以了,只需要加上一句printf。


//先序遍历二叉树
void TraverseBiTree(BiTree T)
{
    if (T == NULL)
        return ;
    printf("%c ", T->data);
    TraverseBiTree(T->lChild);
    TraverseBiTree(T->rChlid);
}


中序遍历,就是在第二次经过这个结点的时候访问它。


//中序遍历二叉树
void InOrderBiTree(BiTree T)
{
    if (T == NULL)
        return ;
    InOrderBiTree(T->lChild);
    printf("%c ", T->data);
    InOrderBiTree(T->rChlid);
}


后序遍历,就是在第三次经过这个结点的时候访问它。


//后序遍历二叉树
void PostOrderBiTree(BiTree T)
{
    if (T == NULL)
        return ;
    PostOrderBiTree(T->lChild);
    PostOrderBiTree(T->rChlid);
    printf("%c ", T->data);
}


我们可以看到,差别仅仅是printf出现的位置,也就是我们访问结点的位置,在递归算法中其他并没有差别。


怎么样,是不是觉得很简单!!!!!!


以下是C语言全部代码实现


#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef char  ElemType; //数据类型
//定义二叉树结构
typedef struct BiTreeNode
{
    ElemType  data; //数据域
    struct BiTreeNode *lChild;
    struct BiTreeNode *rChlid;
} BiTreeNode, *BiTree;
//先序创建二叉树
void CreateBiTree(BiTree *T)//要改变指针,所以要把指针的地址传进来
{
    ElemType ch;
    scanf("%c", &ch);//注意数据类型
    getchar();//吸收空格或者回车
    if (ch == '#')
        *T = NULL;
    else
    {
        *T = (BiTree)malloc(sizeof(BiTreeNode));
        if (!(*T))//检查是否分配成功
            exit(-1);
        (*T)->data = ch;
        CreateBiTree(&(*T)->lChild);//printf("输入%d的左孩子:", ch);
        CreateBiTree(&(*T)->rChlid);//printf("输入%d的右孩子:", ch);
    }
}
//先序遍历二叉树
void TraverseBiTree(BiTree T)
{
    if (T == NULL)
        return ;
    printf("%c ", T->data);
    TraverseBiTree(T->lChild);
    TraverseBiTree(T->rChlid);
}
//中序遍历二叉树
void InOrderBiTree(BiTree T)
{
    if (T == NULL)
        return ;
    InOrderBiTree(T->lChild);
    printf("%c ", T->data);
    InOrderBiTree(T->rChlid);
}
//后序遍历二叉树
void PostOrderBiTree(BiTree T)
{
    if (T == NULL)
        return ;
    PostOrderBiTree(T->lChild);
    PostOrderBiTree(T->rChlid);
    printf("%c ", T->data);
}
//主函数
int main(void)
{
    BiTree T;
    printf("请输入先序遍历顺序下各个结点的值,#表示没有结点:\n");
    CreateBiTree(&T);
    printf("先序遍历二叉树:\n");
    TraverseBiTree(T);
    printf("\n");
    printf("中序遍历二叉树:\n");
    InOrderBiTree(T);
    printf("\n");
    printf("后序遍历二叉树:\n");
    PostOrderBiTree(T);
    printf("\n");
    return 0;
}


(其中初始化时候,以输入‘#’作为空)


结果:



下面是同样的例子用c++实现,大家可以参考一下


#include<iostream>
using namespace std;
typedef char  ElemType; //数据类型
typedef struct BiTreeNode//定义结构体
{
    ElemType  data; //数据域
    struct BiTreeNode *lChild;//左孩子
    struct BiTreeNode *rChlid;//右孩子
} BiTreeNode, *BiTree;
//先序创建二叉树
void CreateBiTree(BiTree &T)//要改变指针,C++可以把指针的引用传进来
{
    ElemType ch;
    cin >> ch;
    if (ch == '#')
        T = NULL;
    else
    {
        T = new BiTreeNode;
        T->data = ch;
        CreateBiTree(T->lChild);//cout<<"输入"<<ch<<"的左孩子:" ;
        CreateBiTree(T->rChlid);//cout<<"输入"<<ch<<"的右孩子:" ;
    }
}
//先序遍历二叉树
void TraverseBiTree(BiTree T)
{
    if (T == NULL)
        return ;
    cout << T->data <<" ";
    TraverseBiTree(T->lChild);
    TraverseBiTree(T->rChlid);
}
//中序遍历二叉树
void InOrderBiTree(BiTree T)
{
    if (T == NULL)
        return ;
    InOrderBiTree(T->lChild);
    cout << T->data <<" ";
    InOrderBiTree(T->rChlid);
}
//后序遍历二叉树
void PostOrderBiTree(BiTree T)
{
    if (T == NULL)
        return ;
    PostOrderBiTree(T->lChild);
    PostOrderBiTree(T->rChlid);
    cout << T->data <<" ";
}
int main(void)
{
    BiTree T;
    cout << "请输入先序遍历顺序下各个结点的值,#表示没有结点:" << endl;
    CreateBiTree(T);
    cout<<"先序遍历二叉树:"<<endl;
    TraverseBiTree(T);
    cout<<endl;
    cout<<"中序遍历二叉树:"<<endl;
    InOrderBiTree(T);
    cout<<endl;
    cout<<"后序遍历二叉树:"<<endl;
    PostOrderBiTree(T);
    cout<<endl;
    return 0;
}
目录
打赏
0
1
0
0
40
分享
相关文章
|
8月前
|
二叉树链式结构的实现(二叉树的遍历以及各种常用功能函数的实现)
二叉树链式结构的实现(二叉树的遍历以及各种常用功能函数的实现)
60 0
同一段代码写N遍?通用树结构一次搞定
本文深入探讨了树形结构在实际应用中的广泛使用及其重要性,并提出了一套通用且高效的工具类TreeUtil来处理与树形数据相关的操作。
图与树的遍历:探索广度优先、深度优先及其他遍历算法的原理与实现
图与树的遍历:探索广度优先、深度优先及其他遍历算法的原理与实现
502 0
|
6月前
|
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
92 0
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
|
8月前
|
从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)(上)
从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)
67 4
|
8月前
|
从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)(下)
从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)
59 2
|
8月前
遍历思路与子问题思路:详解二叉树的基本操作 (一)
这篇内容介绍了二叉树的基本概念和操作,包括二叉树的结构定义以及一些基本操作如前序遍历、中序遍历、后序遍历、获取树中节点个数等。
60 0
java实现树的前序遍历,递归和非递归实现(简单明了)
java实现树的前序遍历,递归和非递归实现(简单明了)
115 0
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力(上)
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力
133 0
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力(下
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力
99 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等