搜索
查看
编辑修改
首页
UNITY
NODEJS
PYTHON
AI
GIT
PHP
GO
CEF3
JAVA
HTML
CSS
搜索
Guff_9hys
这个屌丝很懒,什么也没留下!
关注作者
热门标签
jquery
HTML
CSS
PHP
ASP
PYTHON
GO
AI
C
C++
C#
PHOTOSHOP
UNITY
iOS
android
vue
xml
爬虫
SEO
LINUX
WINDOWS
JAVA
MFC
CEF3
CAD
NODEJS
GIT
Pyppeteer
article
热门文章
1
(7-3)基于隐语义模型的推荐:潜在狄利克雷分配(LDA)_lda构建文档-词频矩阵
2
100天精通Python(可视化篇)——第90天:Pyecharts可视化神器基础入门
3
基于单片机的电流检测装置
4
Explain(sql的执行计划)详解_sql执行计划
5
HAL STM32G4内部运放的使用_stm32g473内部运放
6
angular和vue和react的区别_vue react angular
7
面试?跳槽?涨薪?这些你必须先了解:互联网大厂的薪资和职级一览!_腾讯产品职级
8
了解小程序_完成小程序开发者绑定与开发信息配置后,可以下载开发工具进行小程序的开发与调试工作属于
9
MySQL的SQL预编译及防SQL注入_mysql 防注入 预编译
10
超详细!Python爬虫实战案例
当前位置:
article
> 正文
数据结构——二叉树_采用二叉链表存储结构,visit是对数据元素操作的应用函数。 中序遍历二叉树t的递归
作者:Guff_9hys | 2024-07-01 11:04:42
赞
踩
采用二叉链表存储结构,visit是对数据元素操作的应用函数。 中序遍历二叉树t的递归
树的定义和基本术语
树型结构是一类重要的非线性数据结构,一个对多个,其中以树和二叉树最为常用。
树的定义:
树(Tree)是n(n≥0)个结点的有限集,它或为空树(n = 0);或为非空树,对于非空树T:
(1)有且仅有一个称之为根(Root)的结点;
(2)除根结点以外的其余结点可分为m(m>0)个互不相交的有限集T1, …, Tm , 其中每一个集合Ti本身又是一棵树,并且称为根的子树(SubTree)。
根(Root)
:即根结点(没有前驱)
叶子(Leaf)
:即终端结点(没有后继)
森林(Forest)
:指m棵不相交的树的集合 (例如删除A后的子树个数)
有序树
:结点各子树从左至右有序,不能互换(左为第一)
无序树
:结点各子树可互换位置
双亲(Parent)
:即上层的那个结点(直接前驱)
孩子(Child)
:即下层结点的子树的根(直接后继)
兄弟(Sibling)
:同一双亲下的同层结点(孩子之间互称兄弟)
堂兄弟
:即双亲位于同一层的结点(但并非同一双亲)
祖先
:即从根到该结点所经分支的所有结点
子孙
:即该结点下层子树中的任一结点
结点
:即树的数据元素
结点的度(degree)
:结点挂接的子树数(孩子数【0,1,2】)
结点的层次
:从根到该结点的层数(根结点算第一层)
终端结点
:即度为0的结点,即叶子
分支结点
:即度不为0的结点(也称为内部结点)
树的度
:所有结点度中的最大值
树的深(高)度
:指所有结点中最大的层数
二叉树
二叉树(Binary Tree)是 n (n≥0) 个结点所构成的集合,它或为空树(n = 0);或为非空树,对于非空树T:满足
(1)有且仅有一个称之为根的结点;
(2)除根结点以外的其余结点分为
两个互不相交的子集
T1和T2,分别称为T的
左子树
和
右子树
,且T1和T2本身又都是二叉树。
二叉树的性质:
性质1
: 在二叉树的
第i层
上至多有
2
i-1
个结点
性质2
: 深度为k的二叉树至多有
2
k
-1
个结点
性质3
: 对于任何一棵二叉树,若度为2的结点数有n2个,则叶子数n0必定为n2+1 (即n0=n2+1)
完全二叉树和满二叉树:
满二叉树:一棵深度为k 且有2^k -1个结点的二叉树。(特点:每层都“充满”了结点)
完全二叉树:深度为k 的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n 的结点一一对应,见下图。
特点:(1)叶子结点只可能在层次最大的两层上出现
(2)对任一结点,若其右分支下的子孙的最大层次为l,则其左分支下的子孙的最大层次必为l或l+1。
两者之间的差别:满二叉树是叶子一个也不少的树,而完全二叉树虽然前n-1层是满的,但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。
性质4
: 具有n个结点的完全二叉树的深度必为
ë
log
2
n
û
+
1
(向下取整)
性质5
: 对完全二叉树,若从上至下、从左至右编号, 则编号为 i 的结点, 其左孩子(若存在)编号必为2i, 其右孩子(若存在)编号必为2i+1;其双亲的编号必为
ë
i
/2
û
。
二叉树的存储结构
1.顺序存储结构
用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。(0表示不存在此结点)
顺序存储结构的缺点:仅适用于完全二叉树,因为一个深度为k且只有k个结点的单支树(树中不存在度为2的结点)却需要长度为
2
k
-1
的一维数组。
2.链式存储结构
二叉树的结点:
二叉链表:二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成,则表示二叉树的链表中的结点至少包括3个域:数据域和左、右指针域。
三叉链表:为了便于找到结构中的双亲再在结点结构中增加一个指向其双亲结点的指针域
二叉树的二叉链表存储表示:
typedef struct BiNode{
TElemType data;
struct BiNode *lchild,*rchild; //左右孩子指针
}BiNode,*BiTree;
二叉树的二叉链表存储表示:
typedef struct TriTNode
{ TelemType data;
struct TriTNode *lchild,*rchild;
struct TriTNode *parent;
}TriTNode,*TriTree;
习题:
遍历和搜索二叉树
一、遍历二叉树
遍历定义:指按某条搜索路线遍访每个结点且不重复(又称周游)。
遍历用途:它是树结构插入、删除、修改、查找和排序运算的前提,是二叉树一切运算的基础和核心。
遍历二叉树的递归算法:
(1)先序遍历(DLR):根——左——右
Status PreOrderTraverse(BiTree T){
if(T==NULL)
return OK; //空二叉树
else{
cout<<T->data; //访问根结点
PreOrderTraverse(T->lchild); //递归遍历左子树
PreOrderTraverse(T->rchild); //递归遍历右子树
}
}
(2)中序遍历(LDR):左——根——右
Status InOrderTraverse(BiTree T){
if(T==NULL)
return OK; //空二叉树
else{
InOrderTraverse(T->lchild); //递归遍历左子树
cout<<T->data; //访问根结点
InOrderTraverse(T->rchild); //递归遍历右子树
}
}
(3)后序遍历(LRD):左——右——根
Status PostOrderTraverse(BiTree T){
if(T==NULL)
return OK; //空二叉树
else{
PostOrderTraverse(T->lchild); //递归遍历左子树
PostOrderTraverse(T->rchild); //递归遍历右子树
cout<<T->data; //访问根结点
}
}
时间复杂度和空间复杂度都是O(n);
二叉树遍历算法的应用:
1.计算二叉树遍历总数:
* 如果是空树,则结点个数为0;
* 否则,结点个数为左子树的结点个数+右子树的结点个数再+1。
int NodeCount(BiTree T){
if(T == NULL ) return 0;
else
return NodeCount(T->lchild)+ NodeCount(T->rchild) + 1;
}
2.计算二叉树叶子结点总数
* 如果是空树,则叶子结点个数为0;
* 否则,为左子树的叶子结点个数+右子树的叶子结点个数。
int LeadCount(BiTree T){
if(T==NULL) return 0; //如果是空树返回0
if (T->lchild == NULL && T->rchild == NULL)
return 1; //如果是叶子结点返回1
else
return LeafCount(T->lchild) + LeafCount(T->rchild);
}
结论:
若二叉树中各结点的值均不相同,则:由二叉树的前序序列和中序序列,或由其后序序列和中序序列均能唯一地确定一棵二叉树,但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。
习题:已知一棵二叉树的
中序序列
和
后序序列
分别是
BDCEAFHG
和
DECBHGFA
,请画出这棵二叉树。
解析:
①由后序遍历特征,根结点必在后序序列尾部(A);
②由中序遍历特征,根结点必在其中间,而且其左部必全部是左子树子孙(BDCE),其右部必全部是右子树子孙(FHG);
③继而,根据后序中的DECB子树可确定B为A的左孩子,根据HGF子串可确定F为A的右孩子;以此类推。
中序遍历递归算法执行过程中递归工作栈的状态:
(1)记录中包括两项:递归调用的语句编号;指向根结点的指针,当栈顶记录中的指针非空时,应遍历左子树,即指向左子树根的指针进栈。
(2)若栈顶记录中的指针值为空,则应退至上一层,若是从左子树返回,则应访问 当前层即栈顶记录中指针所指向的根结点。
(3)若从右子树返回则表明当前层的遍历结束,应继续退栈。
从另一个角度看,这意味着遍历右子树不再需要保护当前层的根指针,可直接修改栈顶记录中的指针即可。
//中序遍历二叉树的非递归算法(左根右)
Status InOrderTraverse(BiTree,Status(*Visit)(TElemType e){
//采用二叉链表存储结构,Visit是对数据元素操作的应用函数,每个数据元素调用函数Visit.
InitStack(S); Push(S,T);//根指针进栈
while(!StackEmpty(S)){
while(GetTop(S,p)&&p)Push(S,p->lchild);//向左走到尽头
Pop(S,p); //空指针退栈
if(!StackEmpty(S)){//访问结点,向右走一步
Pop(S,p);if(!Visit(p->data))return ERROR;
Push(S,p->rchild);
}
}
return OK;
}
例:按先序序列建立二叉树的二叉链表,再读入字符
Status CreateBiTree(BiTree &T){
scanf(&ch);//读入字符
if(ch==' ')T=NULL;
else{
if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);
T->data=ch;//生成根结点
CreateBiTree(T->lchild);//构造左子树
CreateBiTree(T->rchild);//构造右子树
}
return OK;
}
二叉链表的缺点:二叉链表空间效率这么低,存在空闲区
改进:使用空闲区存放当前结点的直接前驱和后继等线索,以加快查找速度。
二、搜索化二叉树
遍历二叉树实际上是对一个非线性结构进行线性化操作。但是当以二叉链表作为存储结构时,只能找到结点的左右孩子信息,而不能直接得到结点在任意序列中的前驱和后继信息(只能遍历得到)。
那么如何保存这种遍历过程中的信息呢?
1.在每个结点上增加两个指针域fwd和bkwd,分别只是结点在任意次序遍历时得到的前驱和后继信息。这样能大大的降低结构的存储密度。
2.使用n个结点的二叉链表中的n+1个空链域。
定义:
线索:指向结点前驱和后继的指针
线索链表:加上线索二叉链表
线索二叉树:加上线索的二叉树(图形式样)
线索化:对二叉树以某种次序遍历使其变为线索二叉树的过程
声明:
本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:
https://www.wpsshop.cn/w/Guff_9hys/article/detail/776095
推荐阅读
article
c++
数据结构:
链表
_
c++
链表
...
用一组任意的存储单元存储线性表的数据元素(这些存储单元可以是连续的,也可以是不连续的)_
c++
链表
c++
链表
...
赞
踩
article
【
数据结构
】
堆
...
二叉树里的
堆
的实现【
数据结构
】
堆
堆
堆
的结构与实现
堆
...
赞
踩
article
【
数据结构
】
单链
表
OJ
题
(
一
)...
在上
一
期中我们给大家介绍了
单链
表
,也了解了
单链
表
的实现。接下来就让我们进入实践,练习
一
些经典
题
目,让我们拿捏
单链
表
。【数...
赞
踩
article
【
数据结构
】初识
数据结构
之
复杂度
与
链表
...
哈喽,各位小伙伴大家好!今天我们开启全新的篇章,
数据结构
。简单来说
数据结构
就是数据在内存中的管理。今天给大家带来的是数据...
赞
踩
article
数据结构
——
单向
链表
(C
语言
版)_
c
语言
单向
链表
...
数据结构
单向
链表
简单直白的教学_
c
语言
单向
链表
c
语言
单向
链表
在
数据结构
和算法中,...
赞
踩
article
数据结构
——
算法
和
算法
效率
的
度量...
在大O渐进表示中有一些特殊
的
:比如有两个变量N和M,在没有特殊说明N或者M远远大于另外一个时:O(N+M);O(常数)时...
赞
踩
article
【
数据结构
】
排序
——
插入
排序
,
选择
排序
_实验十五
插入
排序
与
选择
排序
...
前言本篇博客我们正式开启
数据结构
中的
排序
,
说到
排序
,
我们能联想到我之前在C语言博客中的冒泡
排序
,
它是
排序
中的一种
,
但实现...
赞
踩
article
【
数据结构
】
顺序
表实操
—
—
通讯录
项目...
基于
顺序
表的
通讯录
项目【
数据结构
】
顺序
表实操
—
—
通讯录
项目 ...
赞
踩
article
SCAU期末笔记 -
数据结构
(
STL
版)_8579链式
线性表
的
基本操作
scau
...
华南农业大学校OJ
数据结构
课后习题题解_8579链式
线性表
的
基本操作
scau
8579链式
线性表
的
基本操作
scau
...
赞
踩
article
数据结构
/
算法
快速
复习
篇_
算法
快速
复习
...
一、常见的
数据结构
.栈。先进后出,如同一口井。队列。先进先出,如同一条2头通的管道。链表。以单个或多个结点,连接在一起的...
赞
踩
article
数据结构
-
一些
常用
的
算法
技巧
总结_
数据结构
与
算法
答题
技巧
...
本文由 简悦 SimpRead 转码, 原文地址 mp.weixin.qq.com脚本之家你
与
百万开发者在一起来源公众号...
赞
踩
article
数据结构
---
二叉树
前中后序
遍历
...
2.
二叉树
的先序
遍历
和中序
遍历
如下:先序
遍历
: EFHIGJK;中序
遍历
: HFIEJKG. 则
二叉树
根结点为()4....
赞
踩
article
数据结构
——
堆
_
堆
条件...
堆
“
堆
”(Heap),实际上就是一种特殊的树。什么样的树才是
堆
?需要满足两个条件一、
堆
是一个完全二叉树;二、
堆
中每一...
赞
踩
article
【
数据结构
】C
语言
实现
堆
(附完整运行代码)_c
语言
创建
堆
...
使用C
语言
实现
堆
程序新手入门详解,包括
堆
程序每个函数的设计思路及逻辑图示物理图示,简洁明了,直观易懂,文末附程序运行完整...
赞
踩
article
(
数据结构
)
二叉树
后序
遍历
_求
二叉树
的
后序
遍历
...
二叉树
后序
遍历
二叉树
后序
遍历
的实现思想是:访问当前节点的左子树 访问当前节点的右子树 访问根节点图 1
二叉树
以上图 1...
赞
踩
article
哈夫曼
树
(
Huffman
)【
数据结构
】...
假如_
哈夫曼
树
哈夫曼
树
目录 编辑 一、基本概念 二、
哈夫曼
树
的构造算法&...
赞
踩
article
数据结构
—
基础知识
:
哈夫曼
树...
主要讲解了
哈夫曼
树的概念和如何构造一棵
哈夫曼
树,WPL等_
哈夫曼
树
哈夫曼
树 ...
赞
踩
article
数据结构
【
哈夫曼
树
】_
哈夫曼
树
的
构造
...
哈夫曼
树
的概念
哈夫曼
树
的
构造
构造
算法的实现
哈夫曼
树
应用
哈夫曼
编码
哈夫曼
编码的算法实现_
哈夫曼
树
的
构造
哈夫曼
树
的
构造
...
赞
踩
article
毕业设计
:
python
哔哩
哔哩
弹幕
数据分析
可视化系统 B站 bilibili
弹幕
Django
框架...
毕业设计
:
python
哔哩
哔哩
弹幕
数据分析
可视化系统 B站 bilibili
弹幕
Django
框架(源码)✅_
哔哩
哔哩
...
赞
踩
article
数据结构
-顺序表
的
交换
排序
...
快速
排序
是对冒泡
排序
的
一种改进,它
的
基本思想是铜鼓哦一趟
排序
将待
排序
的
数据分割成独立
的
两个部分,其中一部分比另一部分要小...
赞
踩
相关标签
链表
数据结构
c++
算法
c语言
开发语言
数据库
linux
笔记
分布式
mysql
java