数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解

简介: 本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。

本文逻辑:
本文由二叉树的遍历起手,讲解了二叉树的三种遍历方式,以及如何构造一颗二叉树,并在此基础上,扩展了更好的二叉树-线索二叉树。树和森林的存储结构讲解中,重点就是将树与森林转换为二叉树,这样二叉树的手段就能使用到树与森林当中。最后,讲解了二叉树与森林的遍历。

1.二叉树的遍历

什么是遍历
遍历:按照某种次序把所有的结点都访问一遍
什么是层次遍历:基于树的层次特性确定的次序规则(从上到下,从左到右的遍历)

二叉树的递归特性:
:one: 要么是个空二叉树
:two: 要么就是由根节点+左子树+右子树 组成的二叉树

1.1 二叉树的前,中,后序遍历

二叉树有三种遍历的情形
:one:先序遍历:根左右
:two:中序遍历:左根右
:three: 后序遍历:左右根

image.png

二叉树的遍历(手算)

给你一个二叉树,写出他的先序遍历,中序遍历,后序遍历,属于简单题
给出一个手算技巧,留出空,根据遍历规则,补全

1.2 二叉树的层次遍历

  • 算法思想
    :one: 初始化一个辅助队列
    :two: 根结点入队
    :three: 若队列为空,则头结点出队。将其左孩子,右孩子插入队尾(如果有的话
    :four: 重复:three:直至队列为空

1.3构造二叉树

直接说结论:
想要构造一个二叉树,必须知道的两种遍历序列,其中还必须有中序遍历。
也就是中序遍历+(前序遍历or后序遍历or层次遍历)

线索二叉树引入:

在二叉树的基础上,我们能否从一个指定结点开始中序遍历?
如何找到指定结点p在中序遍历序列中的前驱
如何找到p的中序后继
解决思路:
两个指针+目标结点p
从根节点出发,重新进行一次中序遍历,指针q记录当前访问的结点,指针pre记录上一个被访问的结点
当q==p时,pre为前驱
当pre==p时,q为后继。
通过这种方法解决还是太麻烦了,所以引入线索二叉树

2.线索二叉树

2.1 以中序线索二叉树为例,讲解线索二叉树

n个结点的二叉树,有n+1个空链域,用来构成线索,记录前驱和后继

  • 前驱线索(由左孩子指针充当)
  • 后继线索(由右孩子指针充当)
    image.png

三种线索二叉树的对比
image.png

2.2 二叉树的线索化

为了区分指针是指向了孩子还是指向了前驱/后继
我们还需要两个标志 一个是ltag,一个是rtag,记录当前结点是否记录了线索

  • ltag=0,lchild指向左孩子
  • ltag=1,lchild指向前驱
  • rtag=0,lchild指向右孩子
  • rtag=1,lchild指向后继

一棵二叉树的中序线索化:
1.首先取得二叉树的中序序列,
假设是A~4~,A~2~,A~5~,A~1~,A~6~,A~3~
2.A~4~的前驱指针指向NULL,A~3~的后继指针指向NULL
3.遍历一遍树,如果左指针为空就指向前驱,如果右指针为空就指向后继。

2.3 线索二叉树中找前驱后继

2.3.1 中序线索二叉树寻找前驱后继(重点)

中序线索二叉树找中序后继

明确p点肯定有右孩子,没有右孩子的话,中序后继直接为NULL了
根据左根右,他的后继是右,也就是右子树,右孩子如果还有孩子,那继续左根右,即首先访问最左的点
综上所述,中序后继=p的右子树中最左下结点。

中序线索二叉树找中序前驱
有了之前的分析过程,很好推出,中序前驱=p的左子树中最右下结点

2.3.2 先序线索二叉树寻找前驱后继(了解)

先序线索二叉树找先序前驱
无法实现,除非土办法遍历或者,使用三叉链表(能找到p结点的父结点)
下面假设可以找到p的父节点.
image.png

先序线索二叉树找先序后继
先序后继就是最左的节点

2.3.3 后序线索二叉树寻找前驱后继(了解)

后序线索二叉树寻找后序前驱
p肯定有左孩子,若p有右孩子,则后序前驱是他的右孩子,没有就是左孩子

后序线索二叉树寻找后序后继
无法实现,除非土办法遍历或者,使用三叉链表(能找到p结点的父结点)
下面假设可以找到p的父节点.

image.png

3.树的存储结构

  • 双亲表示法(顺序存储)
  • 孩子表示法(顺序+链式存储)
  • :star:孩子兄弟表示法(链式存储)

3.1 双亲表示法(顺序存储)

核心:每个结点中保存指向双亲的指针
image.png

增删改查思路:
增加一个孩子,直接在顺序的数组中增加即可
删除一个孩子,会让某一块为空,可以让最后一个存储的孩子,覆盖上去,提高效率
查找的话:想要找到某个结点的孩子,比较麻烦,要全部遍历一遍树

优缺点:
优点:查指定结点的双亲很方便。
缺点:查指定结点的孩子只能从头遍历。

3.2 孩子表示法(顺序+链式存储)

核心:结点顺序存储,每一个结点的孩子,用链式存储
在这里插入图片描述

3.3 孩子兄弟表示法(链式存储)->重点

核心目的:将逻辑结构树能够转换为存储结构是二叉树的形式储存,这样我们就可以用处理二叉树的手段,处理它。

核心思路:左指针指向第一个孩子(最左边的孩子),右指针指向他的右兄弟

我们可以 轻松的将一个树改写成这种孩子兄弟表示法的形式
在这里插入图片描述

3.4 森林和二叉树的转换

在3.3的基础上,我们不难理解森林和二叉树的转换,就是按照孩子兄弟表示法

4.树的遍历

  • 树的先根遍历

4.1 树的先根遍历(先根,先根,就是先遍历根,再遍历子树)

核心:先根遍历。若树非空,先访问根结点,再依次对每棵子树进行先根遍历。

与二叉树遍历对比:==树的先根遍历序列与二叉树的先序遍历相同==

4.2 树的后根遍历

核心:后根遍历。若树非空,先依次对每棵子树进行后根遍历,最后访问根结点
与二叉树遍历对比:==树的后根遍历序列与二叉树的中序遍历相同==

4.3 树的层次遍历

跟二叉树的层次遍历一样,用队列实现

5.森林的遍历

森林是m棵互不相交的树的集合。每棵树去掉根节点,其各个子树又组成森林。

5.1 先序遍历森林

若森林为非空,则按如下规则进行遍历;
访问森林中第一棵树的根结点。
先序遍历第一棵树中根结点的子树森林
先序遍历除去第一棵之后剩余的树构成的森林。

与==树的遍历==对比:==效果等同于依次对各个树进行先根遍历==

5.2 中序遍历森林

若森林为非空,则按如下规则进行遍历
中序遍历森林中第一棵树的根结点的子树森林
访问第一棵树的根结点。
中序遍历除去第一棵树之后剩余的树构成的森林。

与==树的遍历==对比:==效果等同于依次对各个树进行后根遍历==

相关文章
|
11月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
461 1
|
8月前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
9月前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
9月前
|
存储 算法 C++
【C++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。
291 10
|
1月前
|
存储 C语言
`scanf`是C语言中用于按格式读取标准输入的函数
`scanf`是C语言中用于按格式读取标准输入的函数,通过格式字符串解析输入并存入指定变量。需注意输入格式严格匹配,并建议检查返回值以确保读取成功,提升程序健壮性。
759 0
|
3月前
|
安全 C语言
C语言中的字符、字符串及内存操作函数详细讲解
通过这些函数的正确使用,可以有效管理字符串和内存操作,它们是C语言编程中不可或缺的工具。
262 15
|
9月前
|
存储 算法 C语言
【C语言程序设计——函数】素数判定(头歌实践教学平台习题)【合集】
本内容介绍了编写一个判断素数的子函数的任务,涵盖循环控制与跳转语句、算术运算符(%)、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码,测试说明提供了输入输出示例,最后给出通关代码和测试结果。 任务核心:编写判断素数的子函数并在主函数中调用,涉及循环结构和条件判断。
420 23
|
8月前
|
人工智能 Java 程序员
一文彻底搞清楚C语言的函数
本文介绍C语言函数:函数是程序模块化的工具,由函数头和函数体组成,涵盖定义、调用、参数传递及声明等内容。值传递确保实参不受影响,函数声明增强代码可读性。君志所向,一往无前!
235 1
一文彻底搞清楚C语言的函数
|
9月前
|
算法 C语言
【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数(头歌实践教学平台习题)【合集】
本文档介绍了如何编写两个子函数,分别求任意两个整数的最大公约数和最小公倍数。内容涵盖循环控制与跳转语句的使用、最大公约数的求法(包括辗转相除法和更相减损术),以及基于最大公约数求最小公倍数的方法。通过示例代码和测试说明,帮助读者理解和实现相关算法。最终提供了完整的通关代码及测试结果,确保编程任务的成功完成。
327 15
【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数(头歌实践教学平台习题)【合集】