图解二叉树遍历方法-前序遍历、中序遍历、后序遍历

一、几个概念

二叉树(binary tree):是 n(n >= 0)个结点(每个结点最多只有2棵子树)的有限集合,该集合可为空集(称为空二叉树),或由一个根节点和两颗互不相交的,称为根节点的左子树和右子树的二叉树组成。

如下图中

图1是一棵二叉树。

图2是非二叉树,因为 A 结点有3棵子树,其次 E 结点和 F 结点相交了

二叉链表:是二叉树的一种链式存储结构,其中每个结点包含三个字段:一个数据字段(data)和两个指针字段(*lchild、*rchild),分别指向该结点的左孩子和右孩子。如果某个结点没有左孩子或右孩子,那么对应的指针字段为NULL。

用 C 语言可以表述为:

typedef struct binary_node {
    char data;
    struct binary_node *lchild, *rchild;
}binary_tree;

二、前序遍历二叉树(Pre-order Traversal

        前序遍历二叉树(Pre-order Traversal)的规则为:从根结点出发,先访问该结点,然后前序遍历该结点的左子树,再然后前序遍历该结点的右子树

所以,前序遍历图1这棵二叉树的步骤如图4所示

所以,图1这颗二叉树的前序遍历顺序为:ABDECF

1、算法思路

(1)从根结点 A 出发,A 结点入栈,先访问 A 结点,然后前序遍历 A 结点的左子树

(2)A 结点的左子树的根结点为 B,B 结点入栈,先访问 B 结点,然后前序遍历 B 结点的左子树

(3)B 结点的左子树的根结点为 D,D 结点入栈,先访问 D 结点,然后前序遍历 D 结点的左子树

(4)D 结点的左子树为空,则返回

(5)逻辑返回到 D 结点,然后前序遍历 D 结点的右子树

(6)D 结点的右子树为空,则返回

(7)逻辑返回到 D 结点,此时访问 D 结点,前序遍历 D 结点的左右子树的逻辑都已完成,则返回,D 结点出栈。

(8)逻辑返回到 B 结点,然后前序遍历 B 结点的右子树

(9)B 结点的右子树的根结点为 E,E 结点入栈,先访问 E 结点,然后前序遍历 E 结点的左子树

(10)E 结点的左子树为空,则返回

(11)逻辑返回到 E 结点,然后前序遍历 E 结点的右子树

(12)E 结点的右子树为空,则返回

(13)逻辑返回到 E 结点,此时访问 E 结点,前序遍历 E 结点的左右子树的逻辑都已完成,则返回,E 结点出栈。

(14)逻辑返回到 B 结点,此时访问 B 结点,前序遍历 B 结点的左右子树的逻辑都已完成,则函数返回,B 结点出栈。

(15)逻辑返回到 A 结点,然后前序遍历 A 结点的右子树

(16)A 结点的右子树的根结点为 C,C 结点入栈,先访问 C 结点,然后前序遍历 C 结点的左子树

(17)C 结点的左子树的根结点为 F,F 结点入栈,先访问 F 结点,然后前序遍历 F 结点的左子树

(18)F 结点的左子树为空,则返回

(19)逻辑返回到 F 结点,然后前序遍历 F 结点的右子树

(20)F 结点的右子树为空,则返回

(21)逻辑返回到 F 结点,此时访问 F 结点,前序遍历 F 结点的左右子树的逻辑都已完成,则返回,F 结点出栈。

(22)逻辑返回到 C 结点,然后前序遍历 C 结点的右子树

(23)C 结点的右子树为空,则返回

(24)逻辑返回到 C 结点,此时访问 C 结点,前序遍历 C 结点的左右子树的逻辑都已完成,则返回,C 结点出栈。

(25)逻辑返回到 A 结点,此时访问 A 结点,前序遍历 A 结点的左右子树的逻辑都已完成,则返回,A 结点出栈。

(26)前序遍历二叉树已完成, 所以,前序遍历顺序为:ABDECF

2、实现代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *g_str = "ABD##E##CF###"; // 扩展二叉树前序序列
int g_index = 0;
typedef struct binary_node {
    char data;
    struct binary_node *lchild, *rchild;
}binary_tree;

void create_binary_tree(binary_tree **T) {
    if (strlen(g_str) == 0)
        return;
    
    if (g_str[g_index] == '#') {
        *T = NULL;
        g_index++;
    } else {
        *T = malloc(sizeof(**T));
        (*T)->data = g_str[g_index];
        g_index++;
        create_binary_tree(&(*T)->lchild);
        create_binary_tree(&(*T)->rchild);
    }
}

void visit_node(binary_tree *T) {
    printf("%c\n", T->data);
}

void pre_order_tree(binary_tree *T) {
    if (!T)
        return;
    
    visit_node(T);
    pre_order_tree(T->lchild);
    pre_order_tree(T->rchild);
}

/*销毁用后序遍历*/
void destroy_binary_tree(binary_tree *T) {
    if (!T)
        return;
    
    destroy_binary_tree(T->lchild);
    destroy_binary_tree(T->rchild);
    printf("%c\n", T->data);
    free(T);
}

int main(int argc, char *argv[]) {
    binary_tree *T;
    create_binary_tree(&T);
    printf("------前序遍历-------\n");
    pre_order_tree(T);
    printf("------销毁二叉树------\n");
    destroy_binary_tree(T);
    return 0;
}

三、中序遍历二叉树(In-order Traversal

        中序遍历二叉树(In-order Traversal)的规则为:从根结点出发,先中序遍历该结点的左子树,然后访问该结点,再然后中序遍历该结点的右子树

所以,中序遍历图1这棵二叉树的步骤如下图所示

所以,图1这颗二叉树中序遍历顺序为:DBEAFC

1、算法思路

(1)从根结点 A 出发,A 结点入栈,先中序遍历 A 结点的左子树

(2)A 结点的左子树的根结点为 B,B 结点入栈,先中序遍历 B 结点的左子树

(3)B 结点的左子树的根结点为 D,D 结点入栈,先中序遍历 D 结点的左子树

(4)D 结点的左子树为空,则返回

(5)逻辑返回到 D 结点,然后访问 D 结点,再然后中序遍历 D 结点的右子树

(6)D 结点的右子树为空,则返回

(7)逻辑返回到 D 结点,此时中序遍历 D 结点的左子树,访问 D 结点,中序遍历 D 结点的右子树的逻辑都已完成,则返回,D 结点出栈。

(8)逻辑返回到 B 结点,然后访问 B 结点,再然后中序遍历 B 结点的右子树

(9)B 结点的右子树的根结点为 E,E 结点入栈,先中序遍历 E 结点的左子树

(10)E 结点的左子树为空,则返回

(11)逻辑返回到 E 结点,然后访问 E 结点,再然后中序遍历 E 结点的右子树

(12)E 结点的右子树为空,则返回

(13)逻辑返回到 E 结点,此时中序遍历 E 结点的左子树,访问 E 结点,中序遍历 E 结点的右子树的逻辑都已完成,则返回,E 结点出栈。

(14)逻辑返回到 B 结点,此时中序遍历 B 结点的左子树,访问 B 结点,中序遍历 B 结点的右子树的逻辑都已完成,则返回,B 结点出栈。

(15)逻辑返回到 A 结点,然后访问 A 结点,再然后中序遍历 A 结点的右子树

(16)A 结点的右子树的根结点为 C,C 结点入栈,先中序遍历 C 结点的左子树

(17)C 结点的左子树的根结点为 F,F 结点入栈,先中序遍历 F 结点的左子树

(18)F 结点的左子树为空,则返回

(19)逻辑返回到 F 结点,然后访问 F 结点,再然后中序遍历 F 结点的右子树

(20)F 结点的右子树为空,则返回

(21)逻辑返回到 F 结点,此时中序遍历 F 结点的左子树,访问 F 结点,中序遍历 F 结点的右子树的逻辑都已完成,则返回,F 结点出栈。

(22)逻辑返回到 C 结点,然后访问 C 结点,再然后中序遍历 C 结点的右子树

(23)C 结点的右子树为空,则返回

(24)逻辑返回到 C 结点,此时中序遍历 C 结点的左子树,访问 C 结点,中序遍历 C 结点的右子树的逻辑都已完成,则返回,C 结点出栈。

(25)逻辑返回到 A 结点,此时中序遍历 A 结点的左子树,访问 A 结点,中序遍历 A 结点的右子树的逻辑都已完成,则返回,A 结点出栈。

(26)中序遍历二叉树已完成, 所以,中序遍历顺序为:DBEAFC

2、实现代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *g_str = "ABD##E##CF###"; // 扩展二叉树前序序列
int g_index = 0;
typedef struct binary_node {
    char data;
    struct binary_node *lchild, *rchild;
}binary_tree;

void create_binary_tree(binary_tree **T) {
    if (strlen(g_str) == 0)
        return;
    
    if (g_str[g_index] == '#') {
        *T = NULL;
        g_index++;
    } else {
        *T = malloc(sizeof(**T));
        (*T)->data = g_str[g_index];
        g_index++;
        create_binary_tree(&(*T)->lchild);
        create_binary_tree(&(*T)->rchild);
    }
}

void visit_node(binary_tree *T) {
    printf("%c\n", T->data);
}

void pre_order_tree(binary_tree *T) {
    if (!T)
        return;
    
    visit_node(T);
    pre_order_tree(T->lchild);
    pre_order_tree(T->rchild);
}

void in_order_tree(binary_tree *T) {
    if (!T)
        return;
    
    in_order_tree(T->lchild);
    visit_node(T);
    in_order_tree(T->rchild);
}

/*销毁用后序遍历*/
void destroy_binary_tree(binary_tree *T) {
    if (!T)
        return;
    
    destroy_binary_tree(T->lchild);
    destroy_binary_tree(T->rchild);
    printf("%c\n", T->data);
    free(T);
}

int main(int argc, char *argv[]) {
    binary_tree *T;
    create_binary_tree(&T);
    printf("------中序遍历-------\n");
    in_order_tree(T);
    printf("------销毁二叉树------\n");
    destroy_binary_tree(T);
    return 0;
}

四、后序遍历二叉树(Post-order Traversal

        后序遍历二叉树(Post-order Traversal)的规则为:从根结点出发,先后序遍历该结点的左子树,然后后序遍历该结点的右子树,再然后访问该结点

所以,后序遍历图1这棵二叉树的步骤如下图所示

所以,图1这颗二叉树后序遍历顺序为:DEBFCA

1、算法思路

(1)从根结点 A 出发,A 结点入栈,先后序遍历 A 结点的左子树

(2)A 结点的左子树的根结点为 B,B 结点入栈,先后序遍历 B 结点的左子树

(3)B 结点的左子树的根结点为 D,D 结点入栈,先后序遍历 D 结点的左子树

(4)D 结点的左子树为空,则返回

(5)逻辑返回到 D 结点,然后后序遍历 D 结点的右子树

(6)D 结点的右子树为空,则返回

(7)逻辑返回到 D 结点,然后访问 D 结点,此时后序遍历 D 结点的左子树,后序遍历 D 结点的右子树,访问 D 结点的逻辑都已完成,则返回,D 结点出栈。

(8)逻辑返回到 B 结点,然后后序遍历 B 结点的右子树

(9)B 结点的右子树的根结点为 E,E 结点入栈,先后序遍历 E 结点的左子树

(10)E 结点的左子树为空,则返回

(11)逻辑返回到 E 结点,然后后序遍历 E 结点的右子树

(12)E 结点的右子树为空,则返回

(13)逻辑返回到 E 结点,然后访问 E 结点,此时后序遍历 E 结点的左子树,后序遍历 E 结点的右子树,访问 E 结点的逻辑都已完成,则返回,E 结点出栈。

(14)逻辑返回到 B 结点,然后访问 B 结点,此时后序遍历 B 结点的左子树,后序遍历 B 结点的右子树,访问 B 结点的逻辑都已完成,则返回,B 结点出栈。

(15)逻辑返回到 A 结点,然后后序遍历 A 结点的右子树

(16)A 结点的右子树的根结点为 C,C 结点入栈,先后序遍历 C 结点的左子树

(17)C 结点的左子树的根结点为 F,F 结点入栈,先后序遍历 F 结点的左子树

(18)F 结点的左子树为空,则返回

(19)逻辑返回到 F 结点,然后后序遍历 F 结点的右子树

(20)F 结点的右子树为空,则返回

(21)逻辑返回到 F 结点,然后访问 F 结点,此时后序遍历 F 结点的左子树,后序遍历 F 结点的右子树,访问 F 结点的逻辑都已完成,则返回,F 结点出栈。

(22)逻辑返回到 C 结点,然后后序遍历 C 结点的右子树

(23)C 结点的右子树为空,则返回

(24)逻辑返回到 C 结点,然后访问 C 结点,此时后序遍历 C 结点的左子树,后序遍历 C 结点的右子树,访问 C 结点的逻辑都已完成,则返回,C 结点出栈。

(25)逻辑返回到 A 结点,然后访问 A 结点,此时后序遍历 A 结点的左子树,后序遍历 A 结点的右子树,访问 A 结点的逻辑都已完成,则返回,A 结点出栈。

(26)后序遍历二叉树已完成, 所以,后序遍历顺序为:DEBFCA

2、实现代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *g_str = "ABD##E##CF###"; // 扩展二叉树前序序列
int g_index = 0;
typedef struct binary_node {
    char data;
    struct binary_node *lchild, *rchild;
}binary_tree;

void create_binary_tree(binary_tree **T) {
    if (strlen(g_str) == 0)
        return;
    
    if (g_str[g_index] == '#') {
        *T = NULL;
        g_index++;
    } else {
        *T = malloc(sizeof(**T));
        (*T)->data = g_str[g_index];
        g_index++;
        create_binary_tree(&(*T)->lchild);
        create_binary_tree(&(*T)->rchild);
    }
}

void visit_node(binary_tree *T) {
    printf("%c\n", T->data);
}

void pre_order_tree(binary_tree *T) {
    if (!T)
        return;
    
    visit_node(T);
    pre_order_tree(T->lchild);
    pre_order_tree(T->rchild);
}

void in_order_tree(binary_tree *T) {
    if (!T)
        return;
    
    in_order_tree(T->lchild);
    visit_node(T);
    in_order_tree(T->rchild);
}

void post_order_tree(binary_tree *T) {
    if (!T)
        return;
    
    post_order_tree(T->lchild);
    post_order_tree(T->rchild);
    visit_node(T);
}

/*销毁用后序遍历*/
void destroy_binary_tree(binary_tree *T) {
    if (!T)
        return;
    
    destroy_binary_tree(T->lchild);
    destroy_binary_tree(T->rchild);
    printf("%c\n", T->data);
    free(T);
}

int main(int argc, char *argv[]) {
    binary_tree *T;
    create_binary_tree(&T);
    printf("------后序遍历-------\n");
    post_order_tree(T);
    printf("------销毁二叉树------\n");
    destroy_binary_tree(T);
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/542047.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

编译 c++ 编译的艮,一个编译回合下来 的需要换电脑!

研究这些ui 组件。 这的单独给他准备一台电脑了。 不是cmake 版本对不对。就是qt 版本不对。或者vs 版本太低。 sdk 没有包&#xff0c;编译包&#xff0c;需要组件&#xff0c;组件需要 qt5.5 但是 安装6.5.3 一个回和下来&#xff0c; 电脑坏了。随后旧项目 不能编译了&…

文章解读与仿真程序复现思路——电网技术EI\CSCD\北大核心《风险感知的氢电耦合微网优化调度方法 》

本专栏栏目提供文章与程序复现思路&#xff0c;具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源…

金航标Type-C 母座 卧贴——KH-TYPE-C-16P

产品名称&#xff1a;金航标Type-C 母座 卧贴——KH-TYPE-C-16P 概述&#xff1a;KH-TYPE-C-16P Type-C 母座 卧贴是一款高品质、高性能的连接器&#xff0c;可满足各种电子设备的连接需求。 应用领域&#xff1a; 智能手机、平板电脑、笔记本电脑、数码相机、音频设备等。它可…

C++11 数据结构2 线性表的链式存储,实现,测试

线性表的链式存储 --单链表 前面我们写的线性表的顺序存储(动态数组)的案例&#xff0c;最大的缺点是插入和删除时需要移动大量元素&#xff0c;这显然需要耗费时间&#xff0c;能不能想办法解决呢&#xff1f;链表。 链表为了表示每个数据元素与其直接后继元素之间的逻辑关系…

基于spring boot的留守儿童爱心管理系统

基于spring boot的留守儿童爱心管理系统设计与实现 开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09; 数据库工具&#xff1a;Navicat11 开…

python输入某年某月某日判断这一天是这一年的第几天

如何使用python实现输入某年某月某日判断这一天是这一年的第几天 from datetime import datetime #引入日期类 def is_leap_year(year):"""判断是否为闰年"""return (year % 4 0 and year % 100 ! 0) or (year % 400 0)# 根据年份和月份返回当…

熟悉数电知识

23.数电 1. 建立时间、保持时间 建立时间setup time&#xff1a;时钟上升沿到来之前&#xff0c;输入端数据已经来到并稳定持续的时间。 保持时间hold time&#xff1a;时钟上升沿到来之后&#xff0c;传输端数据保持稳定并持续的时间。 2.二分频电路 每当输入一个时钟信号…

学习基于pytorch的VGG图像分类 day5

注&#xff1a;本系列博客在于汇总CSDN的精华帖&#xff0c;类似自用笔记&#xff0c;不做学习交流&#xff0c;方便以后的复习回顾&#xff0c;博文中的引用都注明出处&#xff0c;并点赞收藏原博主. 目录 VGG的数据集处理 1.数据的分类 2.对数据集的处理 VGG的分类标签设置 …

idea工具使用Tomcat创建jsp 部署servlet到服务器

使用tomcat创建jsp 在tomcat官网中下载对应windows版本的tomcat文件 Apache Tomcat - Welcome! 解压到系统目录中&#xff0c;记得不要有中文路径 新建一个java项目 点击右上角 点击加号 找到Tomcat Service的 Local 点击右下角的Fix一下&#xff0c;然后ok关闭 再重新打开一…

前端HTML入门基础6(框架标签,实体,全局属性,meta元信息)

前端HTML入门基础6&#xff08;框架标签&#xff0c;实体&#xff0c;全局属性&#xff0c;meta元信息&#xff09; 框架标签iframeHTML实体全局属性bdo标签里的dir&#xff0c;div里的dirmeta元信息 框架标签iframe 框架标签是HTML中用于创建网页布局的标签。常见的框架标签有…

vue2响应式原理----发布订阅模式

很多人感觉vue2的响应式其实用到了观察者发布订阅。我们先来看一下简单的发布订阅的代码&#xff1a; // 调度中心 class Dep {static subscribes {}// 订阅所有需求static subscribe (key, demand) {// 对需求分类收集if (!Dep.subscribes[key]) Dep.subscribes[key] []Dep…

C语言-详解内存函数

文章目录 1.memcpy使用和模拟实现1.1 memcpy函数的使用规则1.2 memcpy函数的使用1.2 模拟实现memcpy函数 2.memmove 函数的使用和模拟实现2.1 memmove 函数使用规则2.2 memmove函数的使用2.3 模拟实现memmove函数2.3.1 从后往前移2.3.2 从前往后移 2.4 算法实现2.4.1 从前往后移…

基于Springboot+Vue的Java项目-旅游网站系统(附演示视频+源码+LW)

大家好&#xff01;我是程序员一帆&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;Java毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计 &am…

JavaScript中的Blob、Buffer、ArrayBuffer和TypedArray详解

文章的更新路线&#xff1a;JavaScript基础知识-Vue2基础知识-Vue3基础知识-TypeScript基础知识-网络基础知识-浏览器基础知识-项目优化知识-项目实战经验-前端温习题&#xff08;HTML基础知识和CSS基础知识已经更新完毕&#xff09; 正文 摘要&#xff1a;本文详细介绍了JavaS…

我是如何快速上线项目文档的

Hello , 我是"小恒不会java" 本文适合有使用Markdown&#xff0c;HTML&#xff0c;nginx经验的读者阅读 其中每一个小标题代表作者的突破点&#xff0c;每个技巧都是小tip 说说我的上线流程 使用mkdocs生成模板写入写好的Markdown文件mkdocs build生成静态文件&…

C语言基础(四)

C语言基础 一维数组数组初始化全部初始化部分初始化数组的默认值冒泡排序 字符数组 二维数组初始化行数是否可省略列数是否可以省略部分初始化 访问二维字符数组 函数分类库函数自定义函数调用自定义函数函数声明 一维数组 概念&#xff1a;一组数据类型相同的元素的集合 <…

计算点到线的距离(友元)

计算点到直线的距离。类定义的基本要求&#xff1a; 定义一个点类Point&#xff0c;包含有2 个私有数据成员x和y,表示点的坐标&#xff1b;一个构造函数。定义一个直线类Line&#xff0c;包含有3 个私有数据成员a,b和c&#xff0c;表示直线方程axbyc 0&#xff1b;一个构造函数…

[大模型]# Yi-6B-Chat Lora 微调

Yi-6B-Chat Lora 微调 概述 本节我们介绍如何基于 transformers、peft 等框架&#xff0c;对 Yi-6B-Chat 模型进行 Lora 微调。Lora 是一种高效微调方法&#xff0c;深入了解其原理可参见博客&#xff1a;知乎|深入浅出Lora。 本节所讲述的代码脚本在同级目录 04-Yi-6B-Chat…

ThignsBoard通过服务端订阅共享属性

MQTT基础 客户端 MQTT连接 通过服务端订阅属性 案例 1、首先需要创建整个设备的信息&#xff0c;并复制访问令牌 ​​2、通过工具MQTTX连接上对应的Topic 3、测试链接是否成功 4、在MQTT上订阅对应的Topic 5、在客户端添加共享属性信息 6、查看整个设备的遥测数据 M…

数据库(2)

目录 6.buffer pool,redo log buffer和undo logo&#xff0c;redo logo,bin log概念以及关系&#xff1f; 7.从准备更新一条数据到事务的提交的流程描述&#xff1f; 8.能说下myisam和innodb的区别吗&#xff1f; 9.说下MySQL的索引有哪些吧&#xff1f; 10.什么是B树&…