数据结构与算法教程，数据结构C语言版教程！（第六部分、数据结构树，树存储结构详解）三

第六部分、数据结构树，树存储结构详解

数据结构的树存储结构，常用于存储逻辑关系为 "一对多" 的数据。

树存储结构中，最常用的还是二叉树，本章就二叉树的存储结构、二叉树的前序、中序、后序以及层次遍历、线索二叉树、哈夫曼树等，详细介绍二叉树。

树是数据结构中的重点，同时更是难点，没有捷径，需要初学者静下心，死扣各个知识点。

五、由浅入深讲二叉树4种遍历算法的由来

遍历二叉树可以算作是对树存储结构做的最多的操作，既是重点，也是难点。本节将从初学者的角度给大家分析一下 4 种遍历二叉树算法的由来。

1、遍历二叉树的算法

图 1 二叉树示意图

图 1 是一棵二叉树，对于初学者而言，遍历这棵二叉树无非有以下两种方式。

（1）层次遍历

前面讲过，树是有层次的，拿图 1 来说，该二叉树的层次为 3。通过对树中各层的节点从左到右依次遍历，即可实现对正棵二叉树的遍历，此种方式称为层次遍历。

比如，对图 1 中二叉树进行层次遍历，遍历过程如图 2 所示：

图 2 层次遍历二叉树示意图

（2）普通遍历

其实，还有一种更普通的遍历二叉树的思想，即按照 "从上到下，从左到右" 的顺序遍历整棵二叉树。

还拿图 1 中的二叉树举例，其遍历过程如图 3 所示：

图 3 普通方式遍历二叉树

以上仅是从初学者的角度，对遍历二叉树的过程进行了分析。接下来我们从程序员的角度再对以上两种遍历方式进行剖析。

这里，我们要建立一个共识，即成功遍历二叉树的标志是能够成功访问到二叉树中所有的节点。

2、二叉树遍历算法再剖析

首先观察图 2 中的层次遍历，整个遍历过程只经过各个节点一次，因此在层次遍历过程，每经过一个节点，都必须立刻访问该节点，否则错失良机，后续无法再对其访问。

若对图 1 中二叉树进行层次遍历，则访问树中节点的次序为：

1 2 3 4 5 6 7

而普通遍历方式则不同，通过观察图 3 可以看到，整个遍历二叉树的过程中，每个节点都被经过了 3 次（虽然叶子节点看似只经过了 2 次，但实际上可以看做是 3 次）。以图 3 中的节点 2 为例，如图 4 所示，它被经过了 3 次。

图 4 遍历节点 2 的过程示意图

因此，在编程实现时，我们可以设定真正访问各个节点的时机，换句话说，我们既可以在第一次经过各节点时就执行访问程序，也可以在第二次经过各节点时访问，甚至可以在最后一次经过各节点时访问。

这也就引出了以下 3 种遍历二叉树的算法：

  1. 先序遍历：每遇到一个节点，先访问，然后再遍历其左右子树（对应图 4 中的 ①）；
  2. 中序遍历：第一次经过时不访问，等遍历完左子树之后再访问，然后遍历右子树（对应图 4 中的 ②）；
  3. 后序遍历：第一次和第二次经过时都不访问，等遍历完该节点的左右子树之后，最后访问该节点（对应图 4 中的 ③）；

以图 1 中的二叉树为例，其先序遍历算法访问节点的先后次序为：

1 2 4 5 3 6 7

中序遍历算法访问节点的次序为：

4 2 5 1 6 3 7

后序遍历访问节点的次序为：

4 5 2 6 7 3 1

以上就是二叉树 4 种遍历算法的由来，其各个算法的具体实现过程其代码实现后续章节会详解介绍。

六、二叉树先序遍历（递归与非递归）及C语言实现

二叉树先序遍历的实现思想是：

  1. 访问根节点；
  2. 访问当前节点的左子树；
  3. 若当前节点无左子树，则访问当前节点的右子树；

图 1 二叉树

以图  1 为例，采用先序遍历的思想遍历该二叉树的过程为：

  1. 访问该二叉树的根节点，找到 1；
  2. 访问节点 1 的左子树，找到节点 2；
  3. 访问节点 2 的左子树，找到节点 4；
  4. 由于访问节点 4 左子树失败，且也没有右子树，因此以节点 4 为根节点的子树遍历完成。但节点 2 还没有遍历其右子树，因此现在开始遍历，即访问节点 5；
  5. 由于节点 5 无左右子树，因此节点 5 遍历完成，并且由此以节点 2 为根节点的子树也遍历完成。现在回到节点 1 ，并开始遍历该节点的右子树，即访问节点 3；
  6. 访问节点 3 左子树，找到节点 6；
  7. 由于节点 6 无左右子树，因此节点 6 遍历完成，回到节点 3 并遍历其右子树，找到节点 7；
  8. 节点 7 无左右子树，因此以节点 3 为根节点的子树遍历完成，同时回归节点 1。由于节点 1 的左右子树全部遍历完成，因此整个二叉树遍历完成；

因此，图 1 中二叉树采用先序遍历得到的序列为：

1 2 4 5 3 6 7

1、递归实现

二叉树的先序遍历采用的是递归的思想，因此可以递归实现，其 C 语言实现代码为：

#include <stdio.h>

#include <string.h>

#define TElemType int

//构造结点的结构体

typedef struct BiTNode{

        TElemType data;//数据域

        struct BiTNode *lchild,*rchild;//左右孩子指针

}BiTNode,*BiTree;

//初始化树的函数

void CreateBiTree(BiTree *T){

        *T=(BiTNode*)malloc(sizeof(BiTNode));

        (*T)->data=1;

        (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));

        (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));

        (*T)->lchild->data=2;

        (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));

        (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));

        (*T)->lchild->rchild->data=5;

        (*T)->lchild->rchild->lchild=NULL;

        (*T)->lchild->rchild->rchild=NULL;

        (*T)->rchild->data=3;

        (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));

        (*T)->rchild->lchild->data=6;

        (*T)->rchild->lchild->lchild=NULL;

        (*T)->rchild->lchild->rchild=NULL;

        (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));

        (*T)->rchild->rchild->data=7;

        (*T)->rchild->rchild->lchild=NULL;

        (*T)->rchild->rchild->rchild=NULL;

        (*T)->lchild->lchild->data=4;

        (*T)->lchild->lchild->lchild=NULL;

        (*T)->lchild->lchild->rchild=NULL;

}

//模拟操作结点元素的函数，输出结点本身的数值

void displayElem(BiTNode* elem){

        printf("%d ",elem->data);

}

//先序遍历

void PreOrderTraverse(BiTree T){

        if (T) {

                displayElem(T);//调用操作结点数据的函数方法

                PreOrderTraverse(T->lchild);//访问该结点的左孩子

                PreOrderTraverse(T->rchild);//访问该结点的右孩子

        }

        //如果结点为空，返回上一层

        return;

}

int main() {

        BiTree Tree;

        CreateBiTree(&Tree);

        printf("先序遍历: \n");

        PreOrderTraverse(Tree);

}

运行结果：

先序遍历:
1 2 4 5 3 6 7

2、非递归实现

而递归的底层实现依靠的是栈存储结构，因此，二叉树的先序遍历既可以直接采用递归思想实现，也可以使用栈的存储结构模拟递归的思想实现，其 C 语言实现代码为：

#include <stdio.h>

#include <string.h>

#define TElemType int

int top=-1;//top变量时刻表示栈顶元素所在位置

//构造结点的结构体

typedef struct BiTNode{

        TElemType data;//数据域

        struct BiTNode *lchild,*rchild;//左右孩子指针

}BiTNode,*BiTree;

//初始化树的函数

void CreateBiTree(BiTree *T){

        *T=(BiTNode*)malloc(sizeof(BiTNode));

        (*T)->data=1;

        (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));

        (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));

        (*T)->lchild->data=2;

        (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));

        (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));

        (*T)->lchild->rchild->data=5;

        (*T)->lchild->rchild->lchild=NULL;

        (*T)->lchild->rchild->rchild=NULL;

        (*T)->rchild->data=3;

        (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));

        (*T)->rchild->lchild->data=6;

        (*T)->rchild->lchild->lchild=NULL;

        (*T)->rchild->lchild->rchild=NULL;

        (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));

        (*T)->rchild->rchild->data=7;

        (*T)->rchild->rchild->lchild=NULL;

        (*T)->rchild->rchild->rchild=NULL;

        (*T)->lchild->lchild->data=4;

        (*T)->lchild->lchild->lchild=NULL;

        (*T)->lchild->lchild->rchild=NULL;

}

//前序遍历使用的进栈函数

void push(BiTNode** a,BiTNode* elem){

        a[++top]=elem;

}

//弹栈函数

void pop( ){

        if (top==-1) {

                return ;

        }

        top--;

}

//模拟操作结点元素的函数，输出结点本身的数值

void displayElem(BiTNode* elem){

        printf("%d ",elem->data);

}

//拿到栈顶元素

BiTNode* getTop(BiTNode**a){

        return a[top];

}

//先序遍历非递归算法

void PreOrderTraverse(BiTree Tree){

        BiTNode* a[20];//定义一个顺序栈

        BiTNode * p;//临时指针

        push(a, Tree);//根结点进栈

        while (top!=-1) {

                p=getTop(a);//取栈顶元素

                pop();//弹栈

                while (p) {

                        displayElem(p);//调用结点的操作函数

                        //如果该结点有右孩子，右孩子进栈

                        if (p->rchild) {

                                push(a,p->rchild);

                        }

                        p=p->lchild;//一直指向根结点最后一个左孩子

                }

        }

}

int main(){

        BiTree Tree;

        CreateBiTree(&Tree);

        printf("先序遍历: \n");

        PreOrderTraverse(Tree);

}

运行结果

先序遍历:
1 2 4 5 3 6 7

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

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

相关文章

APUE学习之管道（pipe）与命名管道（fifo）

APUE学习之管道（pipe）与命名管道（fifo）

目录 一、简介 二、管道&#xff08;Pipe&#xff09; 1、管道的基本概念 2、管道的局限性 3、管道的创建 4、管道的读写规则 5、实战演练 三、命名管道&#xff08;fifo&#xff09; 1、命名管道的基本概念 2、命名管道的创建 3、实战演练 4、运行结果 四、补充 …
阅读更多...
flyway使用配置参数和注意事项介绍

flyway使用配置参数和注意事项介绍

文章目录 业务场景参数介绍initSqlsbaselineOnMigratebaselineVersiontargetvalidateOnMigrate SQL注意事项 业务场景 对于生产环境&#xff0c;随着项目版本迭代&#xff0c;数据库结构也会变动。如果一个项目在多个地方实施部署&#xff0c;且版本不一致&#xff0c;就需要一…
阅读更多...
lqb日志08

lqb日志08

一只小蒟蒻备考蓝桥杯的日志 文章目录 笔记坐标相遇判断工作调度问题&#xff08;抽象时间轴绘制&#xff09; 刷题心得小结 笔记 坐标相遇判断 我是小懒虫&#xff0c;碰了一下运气&#xff0c;开了个“恰当”的数&#xff08;7000&#xff09;如果&#xff0c;7000次还不能…
阅读更多...
使用sdbg执行smali简单片段解混淆

使用sdbg执行smali简单片段解混淆

https://github.com/CalebFenton/simplify/releases/download/v1.3.0/sdbg-0.1.0.jar "C:\Program Files\Java\jre-1.8\bin\java.exe" -jar sdbg-0.1.0.jar smali "Lu/ad;->c()V"其中smali为文件夹名称。 ###### Class p124u.C12414ad (u.ad) .class …
阅读更多...
Modern C++ std::unique_ptr的实现原理

Modern C++ std::unique_ptr的实现原理

​ unique_ptr是一个非常简单的类，没有计数没有原子操作，非常类似纯指针。 它的类定义也非常简单： 它针对数组做了模板偏特化，因为它得支持数组操作比如Arr[i]。 unique_ptr的本质就是std::tuple, 里面第一项为指针指向管理对象，第二项为deleter：是一个函数指针或仿函数…
阅读更多...
电脑屏幕色彩调整

电脑屏幕色彩调整

显卡驱动 如果你的电脑是笔记本且没有独显直连&#xff0c;那你就不能在独显里面调屏幕色彩&#xff0c;就要去下载对应核显的驱动&#xff0c;然后去核显的驱动程序里面可以调节。比如&#xff1a;我的笔记本是华硕天选2&#xff0c;无独显直连&#xff0c;锐龙处理器&#x…
阅读更多...
Nginx基础篇【一】

Nginx基础篇【一】

Nginx基础篇【一】 一、Nginx基础篇【一】1.1.背景介绍1.2.名词解释1.2.1. WEB服务器&#xff1a;1.2.2. HTTP:1.2.3. POP3/SMTP/IMAP&#xff1a;1.2.4. 反向代理1.2.5.常见服务器对比1.2.5.1.IIS1.2.5.2.Tomcat1.2.5.3.Apache1.2.5.4.Lighttpd1.2.5.5.其他的服务器 1.3.Nginx…
阅读更多...
跟着cherno手搓游戏引擎【12】渲染context和首个三角形

跟着cherno手搓游戏引擎【12】渲染context和首个三角形

渲染上下文&#xff1a; 目的&#xff1a;修改WindowsWindow的结构&#xff0c;把glad抽离出来 WindowsWindow.h:新建m_Context #pragma once #include "YOTO/Window.h" #include <YOTO/Renderer/GraphicsContext.h> #include<GLFW/glfw3.h> #include…
阅读更多...
Ps：将文件载入堆栈

Ps：将文件载入堆栈

Ps菜单&#xff1a;文件/脚本/将文件载入堆栈 Scripts/Load Files into Stack 将文件载入堆栈 Load Files into Stack脚本命令可用于将两个及以上的文件载入到同一个 Photoshop 新文档中。 载入的每个文件都将成为独立的图层&#xff0c;并使用其原始文件名作为图层名。 Photos…
阅读更多...
GraphicsMagick 的 OpenCL 开发记录（二十五）

GraphicsMagick 的 OpenCL 开发记录（二十五）

文章目录 如何修复R6025 pure virtual function call问题 <2022-04-19 周二> 如何修复R6025 pure virtual function call问题 运气好&#xff0c;修复了这个问题。即&#xff0c;在ExitInstance()函数中调用一下MagickLib::DestroyMagick();即可。 过程中也经历了尝试…
阅读更多...
CSS探索浏览器兼容性

CSS探索浏览器兼容性

学习如何探索浏览器的兼容性对于编写跨浏览器兼容的CSS代码非常重要。以下是一些学习CSS兼容性的方法&#xff1a; MDN文档&#xff1a;Mozilla开发者网络&#xff08;MDN&#xff09;提供了广泛而详细的CSS文档&#xff0c;其中包含有关CSS属性、选择器和功能的信息。在MDN上…
阅读更多...
最新技术实战 | 无视杀软使用远控工具进行横向移动Tips

最新技术实战 | 无视杀软使用远控工具进行横向移动Tips

最新技术实战 | 无视杀软使用远控工具进行横向移动Tips。 杀软是什么意思&#xff1f;杀软是杀毒软件的简称&#xff0c;取的杀毒首字与软件首字组合而成&#xff0c;将杀毒软件简要的称之为杀软&#xff0c;所以&#xff0c;杀软的意思就是杀毒软件&#xff0c;专注于信息领域…
阅读更多...
day34_js

day34_js

今日内容 0 复习昨日 1 事件 1.1 事件介绍 1.2 事件绑定方式 1.3 不同事件的演示 2 DOM操作 2.1 概述 2.2 查找元素 2.3 元素内容的查找和设置 2.4 元素属性的查找和设置 2.5 元素CSS样式的查找和设置 2.6 创建元素 2.7 创建文本节点 2.8 追加元素 2.9 删除元素 3 案例练习 0 复…
阅读更多...
基于springboot+vue的明星周边产品销售网站(前后端分离)

基于springboot+vue的明星周边产品销售网站(前后端分离)

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战 主要内容&#xff1a;毕业设计(Javaweb项目|小程序等)、简历模板、学习资料、面试题库、技术咨询 文末联系获取 研究背景…
阅读更多...
如何快速在阿里云上更新幻兽帕鲁服务器？

如何快速在阿里云上更新幻兽帕鲁服务器？

如何快速在阿里云上更新幻兽帕鲁服务器&#xff1f;幻兽帕鲁更新之后&#xff0c;服务器需要同步更新才能继续游戏&#xff0c;大家可以按照文章操作完成服务升级。 1、如果大家是通过阿里云计算巢部署的&#xff0c;请参考&#xff1a;计算巢部署更新方式。 2、如果不是通过阿…
阅读更多...
前端——HTML

前端——HTML

目录 文章目录 前言 一.HTML的基本标签 二.HTML标签 1.块级标签 1.1块级标签特征 1.2标题标签 ​编辑 1.3 水平线标签 1.4 段落标签 1.5 无序列表标签 1.6 有序列表标签 1.7 表格标签 1.8层标签 1.9 表单 2. 行级标签 2.1行级标签特征 2.2图像标签 2.3 范围…
阅读更多...
epoll示例

epoll示例

一、服务端 下面是一个使用epoll机制在Linux上编写的简单套接字程序示例&#xff1a; #include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #include <sys/socket.h> #include <netinet/in.h> #include &l…
阅读更多...
一天吃透面试八股文

一天吃透面试八股文

内容摘自我的学习网站&#xff1a;topjavaer.cn 分享50道Java并发高频面试题。 线程池 线程池&#xff1a;一个管理线程的池子。 为什么平时都是使用线程池创建线程&#xff0c;直接new一个线程不好吗&#xff1f; 嗯&#xff0c;手动创建线程有两个缺点 不受控风险频繁创…
阅读更多...
滴水逆向三期笔记与作业——02C语言——10 Switch语句反汇编

滴水逆向三期笔记与作业——02C语言——10 Switch语句反汇编

滴水逆向三期笔记与作业——02C语言——10 Switch语句反汇编 一、Switch语句1、switch语句 是if语句的简写2、break加与不加有什么特点?default语句可以省略吗&#xff1f;3、游戏中的switch语句&#xff08;示例&#xff09;4、添加case后面的值&#xff0c;一个一个增加&…
阅读更多...
LLM之llm-viz：llm-viz(3D可视化GPT风格LLM)的简介、安装和使用方法、案例应用之详细攻略

LLM之llm-viz：llm-viz(3D可视化GPT风格LLM)的简介、安装和使用方法、案例应用之详细攻略

LLM之llm-viz&#xff1a;llm-viz(3D可视化GPT风格LLM)的简介、安装和使用方法、案例应用之详细攻略 目录 llm-viz的简介 1、LLM可视化 2、CPU模拟&#xff08;WIP&#xff1b;尚未公开&#xff01;&#xff09; llm-viz的安装和使用方法 llm-viz的案例应用 1、三维可视化…
阅读更多...
最新文章

Copyright @ 2022~2023