数据结构——遍历二叉树和线索二叉树，树和森林

目录

1.遍历的算法实现

1.先序遍历 

代码示例：

 

 2.中序遍历

代码示例：

 3.后序遍历

代码示例：

4.遍历算法的分析 

 

2.遍历二叉树的非递归算法

1.中序遍历非递归算法 

代码示例：

 3.二叉树的层次遍历

代码示例：

 

4.二叉树遍历算法的应用

1.二叉树的建立 

代码示例：

 2.复制二叉树

 代码示例：

3.计算二叉树深度 

代码示例：

 4.计算二叉树结点总数

代码示例：

 

5.计算二叉树叶子结点数 

代码示例：

 5.线索二叉树

1.线索二叉树的结构 

代码示例：

 2.先序线索二叉树

3.中序线索二叉树 

4.后序线索二叉树 

5.练习 

6.树和森林 

1.树的存储结构 

1.双亲表示法 

2.孩子链表 

3.孩子兄弟表示法 

2.树和二叉树的转换 

3.将二叉树转换为树 

7.树和森林的遍历

1.遍历的算法实现

1.先序遍历 

fafc6908807e44518c364a8a19b1f5ba.png

69678e22193e4c1db8a898f8b0a55ebb.png

ebb34f71d35b4728b2997519b25a9971.png

代码示例：

 

int preordertraverse(bitree t)
{
	if(t == NULL) return 0;
	else{
		printf("%d\t",t -> data);
		preordertraverse(t -> lchild);
		preordertraverse(t -> rchild);
	}
}

void pre(bitree t)
{
	if(t != NULL)
	{
		printf("%d\t",t -> data);
		pre(t -> lchild);
		pre(t -> rchild);
	}
}

 2.中序遍历

93194a14ab1b469d82012b46096a898b.png

fcdb27438bcc4d3682ccbf39badf158b.png

代码示例：

int inordertraverse(bitree t)
{
	if(t == NULL) return 0;
	else{
		inordertraverse(t -> lchild);
		printf("&d\t",t -> data);
		inordertraverse(t -> rchild);
	}
}

 3.后序遍历

497cf6dc808f4b0aa4e83fde78dcd919.png

1791c479cb8b48ffbd5404ef7edb54a8.png

代码示例：

int postordertraverse(bitree t)
{
	if(t == NULL) return 0;
	else{
		postordertraverse(t -> lchild);
		postordertraverse(t -> rchild);
		printf("%d\t",t -> data);
	}
}

4.遍历算法的分析 

 

cd156213da22440f9ad2a14bff4549c9.png

aac0282e8e254113aa0a5b787169c280.png

6719152c9107452f9fad855fd0e01f36.png

2.遍历二叉树的非递归算法

1.中序遍历非递归算法 

f66574e1debc43e095dc658d5e661ccc.png

4d5d51bd77974bbc87c416def237782e.png

925bef5487364737af8fab585029ab30.png

2c51c71272fb487aa2544fc18353d553.png

ce80c4bfd4d74af596dcb972108f85ed.png

eeee6682dc6b493cb3379d1e0963b6df.png

代码示例：

int inordertraverse2(bitree t)
{
	bitree p,q;
	initstack(s);
	p = t;
	while(p || !stackempty(s))
	{
		if(p != NULL)
		{
			push(s,p);
			p = p -> lchild;
		}
		else{
			pop(s,q);
			//使栈顶元素弹出，并且将栈顶元素的地址赋给q
			printf("%c",q -> data),p = q -> rchild;
		}
		return 1;
	}
}

 3.二叉树的层次遍历

926c70c3a82c45f287f1aa9bf91bb8b8.png

85c59ea0882e4095b556c703457179fd.png

e1958a411f8847bf878045f5501fb0be.png

903887185d624e42bd25d3395af990d2.png

6b818d3801424dbbb24a3c2229a0e8f7.png

9ddacc42cab64108a29d1860992671cf.png

代码示例：

 

typedef struct{
	btnode data[100];
	int front,rear;
}sqqueue;

void levelorder(btnode *b)
{
	btnode *p;
	sqqueue *qu;
	initqueue(qu);
	enqueue(qu,b);
	while(!queueempty(qu))
	{
		dequeue(qu,p);
		printf("%c",p -> data);
		if(p -> lchild != NULL) enqueue(qu,p -> lchild);
		if(p -> rchild != NULL) enqueue(qu,p -> rchild);
	}
}

4.二叉树遍历算法的应用

1.二叉树的建立 

c016951a15fb4e51af02adb503d08879.png

21c494ccb63f41d7a0e51333d704c617.png

c5bb5ed9b3be498684f50c4f0095b594.png

代码示例：

int createbitree(bitree &t)
{
	cin >> ch;
	if(ch == '#') t = NULL;
	else{
		t = new bitnode;
		t -> data = ch;
		createbitree(t -> lchild);
		createbitree(t -> rchild);
	}
	return 1;
}

 2.复制二叉树

982d6a90b716481db0c78f177ca2f980.png

 代码示例：

int copy(bitree t,bitree &newt)
{
	if(t == NULL)
	{
		newt = NULL;
		return 0;
	}
	else{
		newt = new bitnode;
		newt -> data = t -> data;
		copy(t -> lchild,newt -> lchild);
		copy(t -> rchild,newt -> lchild);
	}
}

3.计算二叉树深度 

321263016a1b4578b12c027275382418.png

代码示例：

int depth(bitree t)
{
	if(t == NULL) return 0;
	else{
		int m,n;
		m = depth(t -> lchild);
		n = depth(t -> rchild);
		if(m > n) return m + 1;
		else return n + 1;
	}
}

 4.计算二叉树结点总数

9fbbb895865c4f479315f90bfa0b84f9.png

代码示例：

 

int nodecount(bitree t)
{
	if(t == NULL) return 0;
	else{
		return nodecount(t -> lchild) + nodecount(t -> rchild) + 1;
	}
}

5.计算二叉树叶子结点数 

9771b582b89c49a183ad73c4f6b442e1.png

代码示例：

int leafcount(bitree t)
{
	if(t == NULL) return 0;
	if(t -> lchild == NULL && t -> rchild == NULL) return 1;
	else return leafcount(t -> lchild) + leafcount(t -> rchild);
}

 5.线索二叉树

bb0b2824402a4af6a570516840c4fb2b.png

445fa532c4ef4929a2144251db22f348.png

5cc54f1232a342ca8749b2d6d56501ba.png

25cc24506a464950ae2bbec033675087.png

044ca47bb6c2402d9a4df5f5ce260522.png

3808e823b78f4fae9b637683781f25f5.png

1.线索二叉树的结构 

7cba2174004f450880e59f5ff4829843.png

代码示例：

typedef struct bithrnode{
	int data;
	int ltag,rtag;
	struct bithrnode *lchild,*rchild;
}bithrnode,*bithrtree;

 2.先序线索二叉树

81347271a2e94f518bb2d3538c9d2796.png

3.中序线索二叉树 

2f8ca093e9a44be9bf982a81c776a4d7.png

4.后序线索二叉树 

ccbbe06e2ce14b9eb18e87c277628e2a.png

5.练习 

16ee657a95824cfdb6d21249757c1a7b.png

92ea03e792fc45c9b6f78ba28929187d.png

6.树和森林 

6854da0bfc3441ee8753a6609678ecd2.png

1.树的存储结构 

1.双亲表示法 

348e9ac43b844399863533c911d4ebc6.png

b60513672ae84806acf6bde7e1a16747.png

2.孩子链表 

4f17ad62bc94453891760de6c22e19bf.png

81c125f9fb6d4945bde84ba612cbab25.png

a77b1a5fb75440ecb3b3ce3ebdf269c9.png

eafe682694484826bd9777def5b42694.png

3.孩子兄弟表示法 

b71056328b15455bb40f6404f970a329.png

215d350a102346feb4f4835499f050bc.png

2.树和二叉树的转换 

55a4538f587a49a387d730168df7ad2b.png

0811ab99f5274557aed325465c375f5c.png

85b64e3de32f4b35b9475ad125e9e6c0.png

811bb68ea7fc447986031a3083fa4394.png

3.将二叉树转换为树 

e0a63cdf1ae048c3b6bde8311b03940c.png

81d81da1eb72443b8a1f6f6321b49904.png

 

03020388d9f745379af6fea7b934385a.png

1949a8f057b24c4fb4219ceafafce7de.png

b1467793aed44d3abc57dd9bf2362fe8.png

ac746065e9ec47eaa38d0dffb4fd8fe1.png

7.树和森林的遍历

355879a716184f6ab59dc8ec81fa9bfa.png

 4f74efd2dcb94e21927f75a0bd84a6ae.png

81631c5013af4b81a7e8b363e3b8cdea.png

c430052d7aeb480ea06949237a26bddd.png

d0f9049bf17e44ffb80c847d0aee8550.png

8.总的代码

typedef struct binode{
	int data;
	struct binode *lchild,*rchild;
}binode,*bitree;

int preordertraverse(bitree t)
{
	if(t == NULL) return 0;
	else{
		printf("%d\t",t -> data);
		preordertraverse(t -> lchild);
		preordertraverse(t -> rchild);
	}
}

void pre(bitree t)
{
	if(t != NULL)
	{
		printf("%d\t",t -> data);
		pre(t -> lchild);
		pre(t -> rchild);
	}
}

int inordertraverse(bitree t)
{
	if(t == NULL) return 0;
	else{
		inordertraverse(t -> lchild);
		printf("&d\t",t -> data);
		inordertraverse(t -> rchild);
	}
}

int postordertraverse(bitree t)
{
	if(t == NULL) return 0;
	else{
		postordertraverse(t -> lchild);
		postordertraverse(t -> rchild);
		printf("%d\t",t -> data);
	}
}

int inordertraverse2(bitree t)
{
	bitree p,q;
	initstack(s);
	p = t;
	while(p || !stackempty(s))
	{
		if(p != NULL)
		{
			push(s,p);
			p = p -> lchild;
		}
		else{
			pop(s,q);
			//使栈顶元素弹出，并且将栈顶元素的地址赋给q
			printf("%c",q -> data),p = q -> rchild;
		}
		return 1;
	}
}

typedef struct{
	btnode data[100];
	int front,rear;
}sqqueue;

void levelorder(btnode *b)
{
	btnode *p;
	sqqueue *qu;
	initqueue(qu);
	enqueue(qu,b);
	while(!queueempty(qu))
	{
		dequeue(qu,p);
		printf("%c",p -> data);
		if(p -> lchild != NULL) enqueue(qu,p -> lchild);
		if(p -> rchild != NULL) enqueue(qu,p -> rchild);
	}
}

int createbitree(bitree &t)
{
	cin >> ch;
	if(ch == '#') t = NULL;
	else{
		t = new bitnode;
		t -> data = ch;
		createbitree(t -> lchild);
		createbitree(t -> rchild);
	}
	return 1;
}

int copy(bitree t,bitree &newt)
{
	if(t == NULL)
	{
		newt = NULL;
		return 0;
	}
	else{
		newt = new bitnode;
		newt -> data = t -> data;
		copy(t -> lchild,newt -> lchild);
		copy(t -> rchild,newt -> lchild);
	}
}

int depth(bitree t)
{
	if(t == NULL) return 0;
	else{
		int m,n;
		m = depth(t -> lchild);
		n = depth(t -> rchild);
		if(m > n) return m + 1;
		else return n + 1;
	}
}

int nodecount(bitree t)
{
	if(t == NULL) return 0;
	else{
		return nodecount(t -> lchild) + nodecount(t -> rchild) + 1;
	}
}

int leafcount(bitree t)
{
	if(t == NULL) return 0;
	if(t -> lchild == NULL && t -> rchild == NULL) return 1;
	else return leafcount(t -> lchild) + leafcount(t -> rchild);
}

typedef struct bithrnode{
	int data;
	int ltag,rtag;
	struct bithrnode *lchild,*rchild;
}bithrnode,*bithrtree;

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

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

相关文章

C#/.NET/.NET Core优秀项目和框架2024年3月简报

C#/.NET/.NET Core优秀项目和框架2024年3月简报

前言 公众号每月定期推广和分享的C#/.NET/.NET Core优秀项目和框架（每周至少会推荐两个优秀的项目和框架当然节假日除外），公众号推文中有项目和框架的介绍、功能特点、使用方式以及部分功能截图等（打不开或者打开GitHub很慢的同学…
阅读更多...
BUUCTF [安洵杯 2019]吹着贝斯扫二维码 1

BUUCTF [安洵杯 2019]吹着贝斯扫二维码 1

BUUCTF:https://buuoj.cn/challenges 题目描述： 得到的 flag 请包上 flag{} 提交。 密文： 下载附件解压，得到很多没有后缀的文件和一个ZIP压缩包。 解题思路： 1、首先，查看ZIP压缩包，发现有密码&#xf…
阅读更多...
GreatSQL 优化技巧：将 MINUS 改写为标量子查询

GreatSQL 优化技巧：将 MINUS 改写为标量子查询

GreatSQL 优化技巧：将 MINUS 改写为标量子查询 前言 minus 指令运用在两个 SQL 语句上，取两个语句查询结果集的差集。它先找出第一个 SQL 所产生的结果，然后看这些结果有没有在第二个 SQL 的结果中，如果在，那这些数据…
阅读更多...
2024年山东临沂教育人才引进报名流程

2024年山东临沂教育人才引进报名流程

2024年山东临沂教育人才引进报名流程
阅读更多...
表单全选反选(前端)

表单全选反选(前端)

1.Html和JavaScript <table><tr><th class"allCheck"><input type"checkbox" name"" id"checkAll"> <span class"all">全选</span></th><th>商品</th><th>商…
阅读更多...
Hive函数笔试题（简单）

Hive函数笔试题（简单）

第1题 有如下的用户访问数据 userId visitDate visitCount u01 2017/1/21 5 u02 2017/1/23 6 u03 2017/1/22 8 u04 2017/1/20 3 u01 2017/1/23 6 u01 2017/2/21 8 u02 2017/1/23 6 u01 2017/2/22 4 要求使用SQL统计出每个用户的累积访问次数&…
阅读更多...
Qt中继承QCheckBox的类结合QTableWidget实现多选并且每个多选的id都不一样

Qt中继承QCheckBox的类结合QTableWidget实现多选并且每个多选的id都不一样

1.相关描述 继承QCheckBox的类MyCheckBox&#xff0c;利用QTableWidget的setCellWidget方式添加MyCheckBox类的对象 2.相关页面 3.相关代码 mycheckbox.h #ifndef MYCHECKBOX_H #define MYCHECKBOX_H#include <QCheckBox> #include <QObject>class MyCheckBox : pu…
阅读更多...
DSSS-UQPSK学习笔记

DSSS-UQPSK学习笔记

文章目录 非平衡四相键控-直接序列扩频&#xff08;UQPSK-DSSS&#xff09;信号因其能同时传输两路不同功率、不同速率信号的特点&#xff0c;在需要图象和数据综合业务传输的领域得到了广泛应用。 系统信号的调制方式为非平衡四相键控&#xff08;Unbalanced Quadrature Phase…
阅读更多...
SpringBoot 整合Redis第1篇

SpringBoot 整合Redis第1篇

SpringBoot是一个开发框架&#xff0c;Redis是一个高性能的键值存储数据库&#xff0c; 常用于缓存、会话管理、消息队列等应用场景。 定义 Redis是什么&#xff1f; 它是一个存储层级&#xff0c; 在实际项目中&#xff0c;位于关系数据库之上&#xff0c; 类似Android分为5…
阅读更多...
vue3封装Element导航菜单

vue3封装Element导航菜单

1. 导航外层布局 AsideView.vue <template><el-menu:default-active"defaultActive"class"my-menu":collapse"isCollapse":collapse-transition"false"open"handleOpen"close"handleClose"><menu…
阅读更多...
【机器学习入门】拥抱人工智能，从机器学习开始

【机器学习入门】拥抱人工智能，从机器学习开始

拥抱人工智能&#xff0c;从机器学习开始 目录&#xff1a; 1. 机器学习&#xff1a;一种实现人工智能的方法2. 机器学习算法&#xff1a;是使计算机具有智能的关键3. Anaconda&#xff1a;初学Python、入门机器学习的首选4. 总结 转载链接&#xff1a;文章-阿里云开发者社区…
阅读更多...
PyTorch深度学习入门-1

PyTorch深度学习入门-1

PyTorch深度学习快速入门教程&#xff08;绝对通俗易懂&#xff01;&#xff09;【小土堆】_哔哩哔哩_bilibili \ PyTorch 和 TensorFlow 是两个深度学习框架&#xff0c;TensorBoard 是 TensorFlow 提供的可视化工具&#xff0c;Transforms是 PyTorch 中用于数据预处理的工具…
阅读更多...
可视化图表：K线图，快速搞清价格波动。

可视化图表：K线图，快速搞清价格波动。

2023-08-21 21:20贝格前端工场 Hi&#xff0c;我是贝格前端工场的老司机&#xff0c;本文分享可视化图表设计的K线图设计&#xff0c;欢迎老铁持续关注我们。 一、K线图的含义 K线图&#xff08;K Line Chart&#xff09;是一种常用于股票、期货等金融市场的可视化图表&…
阅读更多...
如何将图片识别转文字？这3种工具简单易操作

如何将图片识别转文字？这3种工具简单易操作

如何将图片识别转文字&#xff1f;在数字化时代&#xff0c;图片识别转文字技术的需求愈发凸显。无论是处理海量的扫描文档&#xff0c;从中迅速提取关键信息&#xff0c;还是通过照片轻松记录菜单上的文字&#xff0c;这一技术都展现出了其强大的实用性。它极大地提高了我们的…
阅读更多...
计算机网络—VLAN 间路由配置

计算机网络—VLAN 间路由配置

目录 1.拓扑图 2.实验环境准备 3.为 R3 配置 IP 地址 4.创建 VLAN 5.配置 R2 上的子接口实现 VLAN 间路由 6.配置文件 1.拓扑图 2.实验环境准备 配置R1、R3和S1的设备名称&#xff0c;并按照拓扑图配置R1的G0/0/1接口的IP地址。 [Huawei]sysname R1 [R1]interface Giga…
阅读更多...
机器视觉/将HIK海康面阵相机连接Halcon软件

机器视觉/将HIK海康面阵相机连接Halcon软件

文章目录 概述工业相机客户端动态库拷贝Halcon连接HIK相机的配置相机参数其他 概述 本文简述了如何将海康面阵相机连接到Halcon软件中进行实时取图的过程。 补充&#xff0c; 整个实践过程使用 17.12 / x64-win64 Halcon 软件版本 海康 MV-CE200-10GM 面阵相机。从左到右简解…
阅读更多...
机器学习周报第35期

机器学习周报第35期

目录 一、文献阅读&#xff1a;You Only Look Once: Unified, Real-Time Object Detection1.1 摘要1.2 背景1.3 论文模型1.4 网络设计1.5 YOLO的局限性1.6 实现代码 target 7*7*30 值域为0-1 一、文献阅读&#xff1a;You Only Look Once: Unified, Real-Time Object Detection…
阅读更多...
C/C++ 之 GSL 数学运算库使用笔记

C/C++ 之 GSL 数学运算库使用笔记

Part.I Introduction 本文主要记录一下笔者使用 GSL 过程当中所做的一些笔记。 Chap.I 传送门 一些传送门 GSL源码&#xff08;CMakeList 版本-Windows&#xff09;GSL源码&#xff08;configure 版本-Linux&#xff09;GSL 在线文档GSL 文档下载 Chap.II GSL 简介 GSL 全…
阅读更多...
【Java EE】多线程（一）

【Java EE】多线程（一）

&#x1f4da;博客主页&#xff1a;爱敲代码的小杨. ✨专栏&#xff1a;《Java SE语法》 | 《数据结构与算法》 | 《C生万物》 |《MySQL探索之旅》 |《Web世界探险家》 ❤️感谢大家点赞&#x1f44d;&#x1f3fb;收藏⭐评论✍&#x1f3fb;&#xff0c;您的三连就是我持续更…
阅读更多...
Python爬虫验证码识别——手机验证码的自动化处理

Python爬虫验证码识别——手机验证码的自动化处理

手机验证码的自动化处理 有一种验证码就是手机验证码&#xff0c;如果在PC上出现了一个手机验证码&#xff0c;需要先在PC上输入手机号&#xff0c;然后把短信验证码发到手机上&#xff0c;再在PC上输入收到的验证码&#xff0c;才能通过验证。 遇到这样的情况&#xff0c;如…
阅读更多...
最新文章

Copyright @ 2022~2023