代码实现二叉树的三种遍历_遍历二叉树口诀

代码实现二叉树的三种遍历_遍历二叉树口诀文章目录一、图示理解(图片是一位前辈所留,在此感谢)1、先序遍历2、中序遍历3、后序遍历4、层序遍历二、深入理解三种遍历让我们来理解一下绕着外围跑一整圈的真正含义是:遍历所有结点时,都先往左孩子走,再往右孩子走。下面做一个实例吧三、代码实现加以理解以下是C语言全部代码实现下面是同样的例子用c++实现,大家可以参考一下一、图示理解(图片是一位前辈所留,在此感谢)1、先序遍历先序遍历可以想象成,…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

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

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;
}


版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/170892.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Plc编程入门基础知识,在短时间内如何学会编程[通俗易懂]

    Plc编程入门基础知识,在短时间内如何学会编程[通俗易懂]Plc编程入门基础知识,在短时间内如何学会编程PLC:可编程逻辑控制器。实质是一种专用于工业控制的计算机,其硬件结构基本上与微型计算机相同,基本组成如下图所示:工业生产和科技的发展都离不开plc的自动化控制,作为一名电工,想要不被时代所抛弃,就要不断充实自己、投资自己、学习PLC。那么电工学习PLC该如何入门呢?我是一个自动化行业职业计划者。给初学者略略总结一下,希望对你有所帮助。1选择学习的类型市场的主流plc有三菱,西门子,欧姆龙等等,我推荐先学习三菱,西门子基本上了解这两种,不愁没饭吃2从基

  • ES 安装 elasticsearch-sql插件「建议收藏」

    ES 安装 elasticsearch-sql插件「建议收藏」1、查看sql插件githubhttps://github.com/NLPchina/elasticsearch-sql2、安装1、cdelasticsearch#进入目录2、./bin/elasticsearch-plugininstallhttps://github.com/NLPchina/elasticsearch-sql/releases/download/5.4.3.0/elasticsearch-sql-5.4.3.0.zip3、下载SQL的Serverwget

  • 矩阵求秩[通俗易懂]

    矩阵求秩[通俗易懂]矩阵的秩怎么计算,这个问题一下子我居然不知道怎么下手。。虽然本科的时候学过线性代数,但是好久不用,很多东西都忘了。。今天略微梳理一下吧。最简单直观的方法:化成行最简形(或行阶梯形),然后数一下非零行数例如:将矩阵做初等行变换后,非零行的个数叫行秩将其进行初等列变换后,非零列的个数叫列秩矩阵的秩是方阵经过初等行变换或者列变换后的行秩或列秩矩阵的秩是线性代数中的一个概念。在线性代…

  • 浅谈UML的概念和模型之UML九种图

    浅谈UML的概念和模型之UML九种图

    2021年11月16日
  • aliddns ipv6_群晖使用阿里云DDNS(ipv4和ipv6)「建议收藏」

    aliddns ipv6_群晖使用阿里云DDNS(ipv4和ipv6)「建议收藏」复制,写成sh脚本,添加进群晖定时任务即可。ipv4注意前四个需要自己填入,还有获取ip那里要注意网络接口,我的是ppp0。#!/bin/shApiId=”***************”ApiKey=”***************”Domain=’************’SubDomain=’********’#这四个自己写Nonce=$(date-u”+%N”)Timest…

  • 制作html5移动端页面,移动端H5页面制作规范「建议收藏」

    制作html5移动端页面,移动端H5页面制作规范「建议收藏」计量单位的使用css的计量单位有三种选择:px:固定的相素值em:相对父级元素的font-size设置来作为当前元素1em所代表的像素值,如父节点的font-size:10px,当前节点的font-size:1.2em,则当前节点的font-size实为12px;rem:相对根节点html的font-size设置来作为当前元素1rem所代表的像素值,与em的区别就是rem的基本度量单位与父节点…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号