数据结构第六课 -----链式二叉树的实现

作者前言

🎂 ✨✨✨✨✨✨🍧🍧🍧🍧🍧🍧🍧🎂
​🎂 作者介绍： 🎂🎂
🎂 🎉🎉🎉🎉🎉🎉🎉 🎂
🎂作者id：老秦包你会， 🎂
简单介绍：🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂
喜欢学习C语言和python等编程语言，是一位爱分享的博主，有兴趣的小可爱可以来互讨 🎂🎂🎂🎂🎂🎂🎂🎂
🎂个人主页::小小页面🎂
🎂gitee页面:秦大大🎂
🎂🎂🎂🎂🎂🎂🎂🎂
🎂 一个爱分享的小博主 欢迎小可爱们前来借鉴🎂

链式二叉树

  • **作者前言**
  • 二叉树
  • 二叉树的遍历
    • 前序遍历
    • 中序遍历
    • 后序遍历
  • 小例子
  • 知识点

二叉树

前面粗略的介绍了二叉树
二叉树主要有两种 空树和非空树
而非空树拆分为 : 根节点 和左子树和右子树
在这里插入图片描述
二叉树的性质

  1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)个结点.

  2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h -1 .

  3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n0＝ n2＋1

  4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log(n+1) . (ps： 是log以2
    为底，n+1为对数)

  5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

    1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
    2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
    3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

二叉树的遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

  1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。(根 ->左 ->右)

  2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。(左->根->右)

  3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。(左->右->根)

为此特意构建一个二叉树

#include<stdio.h>
#include<stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType* val;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* rigth;

}BinaryTreeNode;
BinaryTreeNode* CreateNode(BTDataType elemest)
{
	BinaryTreeNode* p = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
	if (p == NULL)
	{
		perror("malloc");
		return -1;
	}
	p->val = elemest;
	return p;
}
int main()
{
	BinaryTreeNode* n1 = CreateNode(1);
	BinaryTreeNode* n2 = CreateNode(2);
	BinaryTreeNode* n3 = CreateNode(3);
	BinaryTreeNode* n4 = CreateNode(4);
	BinaryTreeNode* n5 = CreateNode(5);
	BinaryTreeNode* n6 = CreateNode(6);
	n1->left = n2;
	n1->rigth = n4;
	n2->left = n3;
	n2->rigth = NULL;
	n3->left = NULL;
	n3->rigth = NULL;
	n4->left = n5;
	n4->rigth = n6;
	n5->left = NULL;
	n5->rigth = NULL;
	n6->left = NULL;
	n6->rigth = NULL;
	return 0;
}

前序遍历

我们以上面图片为例
我们可以写成：
1 2 3 N N N 4 5 N N 6 N N
代码：

void PreOrder(BinaryTreeNode* n1)
{
	if (n1 == NULL)
	{
		printf("NULL ");
		return;
	}
		

	printf("%d ", n1->val);
	PreOrder(n1->left);
	PreOrder(n1->rigth);
}

在这里插入图片描述

中序遍历

我们可以写成：N 3 N 2 N 1 N 5 N 4 N 6 N
代码：

void InOrdef(BinaryTreeNode* n1)
{
	if (n1 == NULL)
	{
		printf("NULL ");
		return;
	}
	PreOrder(n1->left);
	printf("%d ", n1->val);
	PreOrder(n1->rigth);
}

后序遍历

我们可以写成： N N 3 N 2 N N 5 N N 6 4 1
代码：

void PostOrder(BinaryTreeNode* n1)
{
	if (n1 == NULL)
	{
		printf("NULL ");
		return;
	}
	PreOrder(n1->left);
	PreOrder(n1->rigth);
	printf("%d ", n1->val);
}

小例子

叶子节点个数
思路:左子树的节点个数加上右子树的节点个数加上根节点

//节点个数
int TreeSize(BinaryTreeNode* n1)
{
	if (n1 == NULL)
		return 0;
	return 1 + TreeSize(n1->left) + TreeSize(n1->rigth);
}

叶节点个数
思路:左子树的叶节点个数加上右子树的叶节点个数加上根节点 需要注意的是为空树.和只有根节点的情况

//叶节点的个数
int TreeLeafSize(BinaryTreeNode* n1)
{
	//为空树
	if (n1 == NULL)
		return 0;
	//只有一个节点
	if (n1->left == NULL && n1->rigth == NULL)
		return 1;
	return TreeLeafSize(n1->left) + TreeLeafSize(n1->rigth);
}

树的高度
思路:左子树的高度和右子树高度比较,大的高度加上1就是整个二叉树的高度,需要注意的是空树情况下

int TreeHeigth(BinaryTreeNode* n1)
{
	if (n1 == NULL)
		return 0;
	if (n1->left == NULL && n1->rigth == NULL)
		return 1;
	int a = TreeHeigth(n1->left);
	int b = TreeHeigth(n1->rigth);
	return (a > b ? a : b) + 1;
}

#第k层的节点
思路: 左子树的第k-1层的节点个数 加上右子树的第k-1层的节点个数,如果k为0就是空,k=1,就是1
​

int NodeNum(BinaryTreeNode* n1, int k)
{
	if (n1 == NULL)
		return 0;
	if (k == 0)
		return 0;
	if (k == 1)
		return 1;
	return NodeNum(n1->left, k - 1) + NodeNum(n1->rigth, k - 1);
}

层次遍历
思路:层次遍历就是从第一层开始横向遍历
我们可以借助队列的性质,先进先出,我们先开始插入根节点,然后开始进行循环判断,只要出去的节点的左右孩子不为NULL就插入到队列,直到队列为空
在这里插入图片描述

// 层序遍历
void BinaryTreeLevelOrder(BinaryTreeNode* root)
{
	//创建一个队列
	Queue Qu;
	//初始化
	QueueInit(&Qu);
	//插入的是节点,
	if (root != NULL)
		QueuePush(&Qu, root);
	while (QueueSize(&Qu))
	{
		BinaryTreeNode* from = QueueFront(&Qu);
		
		
		printf("%d ", from->val);
		//删除
		QueuePop(&Qu);
		//需要注意的是删除只是释放掉存储了二叉树节点的地址的空间,并没有释放二叉树节点
		if (from->left != NULL)
		{
			QueuePush(&Qu, from->left);
		}
		if (from->rigth != NULL)
		{
			QueuePush(&Qu, from->rigth);
		}
		
	}
	printf("\n");
	QueueDestroy(&Qu);
	
	
	
}

这个是打印全部的
如果要一层层的打印
思路: 我们可以定义一个变量,用来统计当前队列的个数,也就是当层的节点个数,然后每出列一个就把对应的左右孩子插入进去,然后该变量减1,直到为0,也就是该层的节点全部出列了,然后再计算出队列的长度,也就是下一层的节点个数,然后继续，直到队列的长度为0

在这里插入图片描述

// 层序遍历
void BinaryTreeLevelOrder(BinaryTreeNode* root)
{
	//创建一个队列
	Queue Qu;
	//初始化
	QueueInit(&Qu);
	//插入的是节点,
	if (root != NULL)
		QueuePush(&Qu, root);
	int size = QueueSize(&Qu);
	while (QueueSize(&Qu))
	{
		while (size--)
		{
			BinaryTreeNode* from = QueueFront(&Qu);


			printf("%d ", from->val);
			//删除
			QueuePop(&Qu);
			//需要注意的是删除只是释放掉存储了二叉树节点的地址的空间,并没有释放二叉树节点
			if (from->left != NULL)
			{
				QueuePush(&Qu, from->left);
			}
			if (from->rigth != NULL)
			{
				QueuePush(&Qu, from->rigth);
			}
		}
		printf("\n");
		size = QueueSize(&Qu);
		
	}
	printf("\n");
	QueueDestroy(&Qu);
	
	
	
}

判断是否是完全二叉树
思路：我们和上面的层次遍历一样，先找一个队列进行一层层的入队和出队，如果遇见节点为NULL的就判断后面是否还有节点存在

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BinaryTreeNode* root)
{
	//创建一个队列
	Queue Qu;
	//初始化
	QueueInit(&Qu);
	//插入的是节点,
	if (root != NULL)
		QueuePush(&Qu, root);
	while (QueueSize(&Qu))
	{
		
		BinaryTreeNode* from = QueueFront(&Qu);
		if (from == NULL)
			break;
		//删除
        QueuePop(&Qu);
		//需要注意的是删除只是释放掉存储了二叉树节点的地址的空间,并没有释放二叉树节点
		QueuePush(&Qu, from->left);
		QueuePush(&Qu, from->rigth);
	}
	//判断后面是否还有非空
	while (!QueueEmtry(&Qu))
	{
		BinaryTreeNode* from = QueueFront(&Qu);
		if (from != NULL)
			return 0;
		//删除
		QueuePop(&Qu);
	}
	QueueDestroy(&Qu);
	return 1;

}

知识点

前序：深度优先遍历
层序： 广度优先遍历

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

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

相关文章

价差后的几种方向，澳福如何操作才能盈利

价差后的几种方向，澳福如何操作才能盈利

在价差出现时&#xff0c;澳福认为会出现以下几种方向。 昂贵资产的贬值和便宜资产的平行升值。昂贵的资产贬值&#xff0c;而便宜的资产保持不变。昂贵资产的贬值和便宜资产的平行贬值&#xff0c;但昂贵资产的贬值速度更快&#xff0c;超过便宜资产。更贵的一对的进一步升值和…
阅读更多...
python pyaudio对音频进行端点检测，检测出说话区间

python pyaudio对音频进行端点检测，检测出说话区间

python pyaudio对音频进行端点检测&#xff0c;检测出说话区间 主要采用过零率和语音能量来进行检测&#xff0c;并设置双阈值。 代码如下&#xff1a; # -*- coding: utf-8 -*- import wave import os import matplotlib.pyplot as plt import numpy as np# 判断是否变号 de…
阅读更多...
大数据技术学习笔记（四）—— HDFS

大数据技术学习笔记（四）—— HDFS

目录 1 HDFS 概述1.1 HDFS 背景与定义1.2 HDFS 优缺点1.3 HDFS 组成架构1.4 HDFS 文件块大小 2 HDFS的shell操作2.1 上传2.2 下载2.3 HDFS直接操作 3 HDFS的客户端操作3.1 Windows 环境准备3.2 获取 HDFS 的客户端连接对象3.3 HDFS文件上传3.4 HDFS文件下载3.5 HDFS删除文件和目…
阅读更多...
Lab 3: Recursion, Tree Recursion(CS61A 2020)

Lab 3: Recursion, Tree Recursion(CS61A 2020)

在网上没有lab3相应的答案&#xff0c;作者也卡蛮久 作者可能就自己的卡住过的问题做一些总结&#xff0c;不能面面俱到&#xff0c;请见谅 &#xff08;就此补充一下答案&#xff09;&#xff08;完整答案在最后&#xff09; Q2: WWPD: Journey to the Center of the Earth…
阅读更多...
AcW730.机器人跳跃问题(二分法)-Java版

AcW730.机器人跳跃问题(二分法)-Java版

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;//由题目可知,无论能量大与小,都满足 e 2 * e - h[i]; //初始能量越大,最终的结果越大,要找到一个满足条件的最小值 //可以根据二分的向左找模板: /*if(check(mid)) r mid;els…
阅读更多...
【C++ STL】vector类最全详解（什么是vector?vector类的常用接口有哪些？）

【C++ STL】vector类最全详解（什么是vector?vector类的常用接口有哪些？）

目录 一、前言 二、什么是vector ? &#x1f4a6; vector的基本概念 &#x1f4a6;vector的作用是什么 &#x1f4a6;总结 三、 vector的(一维)定义 四、vector(一维)常用接口的使用 &#x1f4a6;vector的常见构造&#xff08;初始化&#xff09; &#x1f4a6;vector…
阅读更多...
11. 哈希冲突

11. 哈希冲突

上一节提到&#xff0c;通常情况下哈希函数的输入空间远大于输出空间&#xff0c;因此理论上哈希冲突是不可避免的。比如&#xff0c;输入空间为全体整数&#xff0c;输出空间为数组容量大小&#xff0c;则必然有多个整数映射至同一桶索引。 哈希冲突会导致查询结果错误&#…
阅读更多...
探索人工智能领域——每日20个名词详解【day6】

探索人工智能领域——每日20个名词详解【day6】

目录 前言 正文 总结 &#x1f308;嗨&#xff01;我是Filotimo__&#x1f308;。很高兴与大家相识&#xff0c;希望我的博客能对你有所帮助。 &#x1f4a1;本文由Filotimo__✍️原创&#xff0c;首发于CSDN&#x1f4da;。 &#x1f4e3;如需转载&#xff0c;请事先与我联系以…
阅读更多...
C++ 指针详解

C++ 指针详解

目录 一、指针概述 指针的定义 指针的大小 指针的解引用 野指针 指针未初始化 指针越界访问 指针运算 二级指针 指针与数组 二、字符指针 三、指针数组 四、数组指针 函数指针 函数指针数组 指向函数指针数组的指针 回调函数 指针与数组 一维数组 字符数组…
阅读更多...
【C++】C/C++内存管理

【C++】C/C++内存管理

前言&#xff1a; 前面我们已经学习了类与对象&#xff0c;认识了六个默认成员函数。这一篇文章我们来学习C/C内存管理&#xff0c;深入了解这套机制有利于我们之后写出更好的C/C程序。 一、C/C内存分布&#xff1a; 1.C/C中程序内存区域划分&#xff1a; 在C中&#xff0c;内…
阅读更多...
多要素环境监测一体机-生态环境的守护者

多要素环境监测一体机-生态环境的守护者

随着人类活动的不断增加&#xff0c;环境问题日益凸显。为了实时了解环境状况&#xff0c;保护生态环境&#xff0c;一款多要素环境监测一体机应运而生。 一、实时监测&#xff0c;掌握环境动态 WX-CSQX12 多要素环境监测一体机能够实时监测空气质量、温湿度、噪音、风速等多…
阅读更多...
SSM项目实战-前端-添加分页控件-调正页面布局

SSM项目实战-前端-添加分页控件-调正页面布局

1、Index.vue <template><div class"common-layout"><el-container><el-header><el-row><el-col :span"24"><el-button type"primary" plain click"toAdd">新增</el-button></el-…
阅读更多...
华清远见嵌入式学习——C++——作业3

华清远见嵌入式学习——C++——作业3

作业要求&#xff1a; 代码&#xff1a; #include <iostream>using namespace std;class Per { private:string name;int age;double *high;double *weight; public://有参构造函数Per(string n,int a,double h,double w):name(n),age(a),high(new double(h)),weight(ne…
阅读更多...
CoreDNS实战(一)-构建高性能、插件化的DNS服务器

CoreDNS实战(一)-构建高性能、插件化的DNS服务器

1 概述 在企业高可用DNS架构部署方案中我们使用的是传统老牌DNS软件Bind, 但是现在不少企业内部流行容器化部署&#xff0c;所以也可以将Bind替换为 CoreDNS &#xff0c;由于 CoreDNS 是 Kubernetes 的一个重要组件&#xff0c;稳定性不必担心&#xff0c;于此同时还可将K8S集…
阅读更多...
QT之QString

QT之QString

QT之QString 添加容器 点击栅格布局 添加容器&#xff0c;进行栅格布局 布局总结&#xff1a;每一个模块放在一个Group中&#xff0c;排放完之后&#xff0c;进行栅格布局。多个Group进行并排时&#xff0c;先将各个模块进行栅格布局&#xff0c;然后都选中进行垂直布…
阅读更多...
Python中对数组连续赋值的问题

Python中对数组连续赋值的问题

问题描述 在python中&#xff0c;首先用两个等号对两个数组进行初始化并赋值。之后&#xff0c;对任何一个数组进行赋值&#xff0c;都会将其赋予相同值。 import numpy as np Array1 Array2 np.empty(2) Array1[0],Array2[0]70,80 print(Array1[0],Array2[0])80.0 80.0 …
阅读更多...
Learning Normal Dynamics in Videos with Meta Prototype Network 论文阅读

Learning Normal Dynamics in Videos with Meta Prototype Network 论文阅读

文章信息&#xff1a;发表在cvpr2021 原文链接&#xff1a; Learning Normal Dynamics in Videos with Meta Prototype Network 摘要1.介绍2.相关工作3.方法3.1. Dynamic Prototype Unit3.2. 视频异常检测的目标函数3.3. 少样本视频异常检测中的元学习 4.实验5.总结代码复现&a…
阅读更多...
【电机控制】PMSM无感foc控制（六）相电流检测及重构 — 双电阻采样、三电阻采样

【电机控制】PMSM无感foc控制（六）相电流检测及重构 — 双电阻采样、三电阻采样

0. 前言 目前&#xff0c;永磁同步电机的电流信号采样方法应用较多的是分流电阻采样&#xff0c;包括单电阻、双电阻以及三电阻采样法。其中&#xff0c;单电阻采样上一章节已经讲解&#xff0c;这章讲双电阻以及三电阻电流采样法。 1. 双电阻采样 1.1 双电阻采样原理 双电阻采…
阅读更多...
FPGA时序分析与时序约束（一）

FPGA时序分析与时序约束（一）

一、为什么要进行时序分析和时序约束 PCB通过导线将具有相关电气特性的信号相连接&#xff0c;这些电气信号在PCB上进行走线传输时会产生一定的传播延时。 而FPGA内部也有着非常丰富的可配置的布线资源&#xff0c;能够让位于不同位置的逻辑资源块、时钟处理单元、BLOCK RAM、D…
阅读更多...
线性回归 numpy实现线性回归

线性回归 numpy实现线性回归

手写线性回归 使用numpy随机生成数据 import numpy as np import matplotlib.pyplot as plt# 生成模拟数据 np.random.seed(42) X 2 * np.random.rand(200, 1) y 4 3 * X np.random.randn(200, 1)# 可视化数据 plt.scatter(X, y) plt.xlabel(X) plt.ylabel(y) plt.title(…
阅读更多...
最新文章

Copyright @ 2022~2023