二叉树链式结构

1.前置说明

 我们手动构建一棵二叉树：

注意：上述代码并不是创建二叉树的方式

从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的

2.二叉树的遍历

2.1前序、中序以及后序遍历

学习二叉树结构，最简单的方式就是遍历

所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题

遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础

其实可以这样理解：

  • 前序遍历：根->左子树->右子树
  • 中序遍历：左子树->根->右子树
  • 后序遍历：左子树->右子树->根

以下面这个二叉树为例：

  • 前序遍历：1->2->3->4->5->6
  • 中序遍历：3->2->1->5->4->6
  • 后序遍历：3->2->5->6->4->1

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树

NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历

遍历的实现需要用到递归

2.2前序遍历

代码实现是这样的：

2.3中序遍历

2.4后序遍历

2.5层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。

设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历

我们可以利用队列先进先出的特点来实现：

  • 定义一个q队列
  • 如果root不为空，则将root入队列
  • 用front来保存队头数据，将队头数据pop，打印队头数据；然后遍历下一层：如果左孩子不为空，左孩子入队列；右孩子不为空，右孩子入队列；当队列不为空则继续遍历下一层，直到队列为空退出循环

关于这块的指针问题，我们画图解释一下

我们修改val也为BTNode*类型

分层打印

我们可以定义一个levelsize保存每一层的数据个数，控制一层一层打印

队列的size就是下一层的数据个数

效果是这样的

3.节点个数

3.1二叉树的节点个数

3.1叶子节点个数

4.求树的高度

  1. 如果为空 返回0
  2. 不为空 左子树和右子树高度更高的那个+1

5.求第k层的节点个数

  1. 如果为空 返回0
  2. 如果不为空 且k=1 返回1
  3. 如果不为空 且k>1 返回左子树的k-1层+右子树的k-1层

5.查找值为x的节点 

6.构建一棵链式二叉树

假设给一个前序遍历的数组，将其构建成一棵二叉树

7.判断完全二叉树

完全二叉树的节点都是连续的，所以不可能出现一个NULL节点的后面存在非空节点的情况，我们用层序遍历的思路，入队列的时候不管是不是NULL节点都入队列，出队列的时候如果遇到NULL节点，则停止出队列，判断后面是否还有非空节点，我们用while循环来控制，如果队列不为空则出队列，如果队头数据有不为空的情况，则返回false

8.销毁二叉树

销毁我们为了防止形成野指针，从下往上，从左往右，即后序遍历依次销毁

代码示例 

Queue

Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
//创建
typedef struct BTNode* QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
//把队列的头尾封装在一个结构体中

//初始化
void QInit(Queue* pq);
//销毁
void QDestroy(Queue* pq);

//入队列
void QPush(Queue* pq, QDataType x);
//出队列
void QPop(Queue* pq);
//取队头数据
QDataType QFront(Queue* pq);
//取队尾数据
QDataType QBack(Queue* pq);
//判空
bool QEmpty(Queue* pq);
//返回队列有效元素个数
int QSize(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//初始化
void QInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//销毁
void QDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//入队列
void QPush(Queue* pq, QDataType x)
{
	assert(pq);
	//创建newnode
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
//出队列
void QPop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	QNode* del = pq->phead;
	pq->phead = pq->phead->next;
	free(del);
	del = NULL;
	if (pq->phead == NULL)
	{
		pq->ptail = NULL;
		//防止ptail成为野指针
	}
	pq->size--;
}
//取队头数据
QDataType QFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}
//取队尾数据
QDataType QBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->val;
}
//判空
bool QEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}
//返回队列有效元素个数
int QSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

TreeNode

TreeNode.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include "Queue.h"
//创建
typedef char BTDataType;
typedef struct BTNode
{
	BTDataType data;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;

//BTNode* BuyNode(BTDataType x)
//{
//	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
//	node->data = x;
//	node->left = NULL;
//	node->right = NULL;
//	return node;
//}
//构建二叉树
BTNode* BTCreate(BTDataType*a,int*pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	root->data = a[(*pi)++];
	root->left = BTCreate(a,pi);
	root->right = BTCreate(a,pi);
	return root;
}
//先序遍历
void BTPrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	printf("%c ", root->data);
	BTPrevOrder(root->left);
	BTPrevOrder(root->right);
}
//中序遍历
void BTInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	BTInOrder(root->left);
	printf("%c ", root->data);
	BTInOrder(root->right);
}
//后序遍历
void BTPostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	BTPostOrder(root->left);
	BTPostOrder(root->right);
	printf("%c ", root->data);
}
// 层序遍历
void BTLevelOrder(BTNode* root)
{
	Queue q;
	QInit(&q);
	if (root)
		QPush(&q, root);
	int levelsize = 1;
	while (!QEmpty(&q))
	{
		while (levelsize--)
		{
			BTNode* front = QFront(&q);
			QPop(&q);
			printf("%c ", front->data);
			if (front->left)
				QPush(&q, front->left);
			if (front->right)
				QPush(&q, front->right);
		}
		printf("\n");
		levelsize = QSize(&q);
	}
	printf("\n");
	QDestroy(&q);
}
//判断完全二叉树
bool BTComplete(BTNode* root)
{
	Queue q;
	QInit(&q);
	if (root)
		QPush(&q, root);
	int levelsize = 1;
	while (!QEmpty(&q))
	{
		BTNode* front = QFront(&q);
		QPop(&q);
		if (front == NULL)
			break;
		QPush(&q, front->left);
		QPush(&q, front->right);
	}
	while (!QEmpty(&q))
	{
		BTNode* front = QFront(&q);
		QPop(&q);
		if (front)
		{
			QDestroy(&q);
			return false;
		}
	}
	QDestroy(&q);
	return true;
}
//销毁
void BTDestroy(BTNode* root)
{
	if (root == NULL)
		return;
	BTDestroy(root->left);
	BTDestroy(root->right);
	free(root);
}
//二叉树结点个数
//static int size = 0;
int BTSize(BTNode* root)
{
	/*if (root == NULL)
	{
		return;
	}
	++size;
	BTSize(root->left);
	BTSize(root->right);
	return size;*/
	return root == NULL ? 0 : 
		BTSize(root->left) + 
		BTSize(root->right)+1;
}
//叶子节点个数
int BTLSize(BTNode* root)
{
	/*if (root == NULL)
	{
		return 0;
	}
	return root->left == NULL && root->right == NULL ? 1:
		BTLSize(root->left) + BTLSize(root->right);*/
	return (root == NULL ? 0 : 
		(root->left == NULL && root->right == NULL ? 1 :
		BTLSize(root->left) + BTLSize(root->right)));
}
//求树的高度
int BTHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftHeight = BTHeight(root->left);
	int rightHeight = BTHeight(root->right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
//求第k层的节点个数
int BTLKSize(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BTLKSize(root->left, k - 1) + BTLKSize(root->right, k - 1);
}
//查找值为x的节点
BTNode* BTFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* leftnode = BTFind(root->left, x);
	if (leftnode)
		return leftnode;
	BTNode* rightnode = BTFind(root->right, x);
	if (rightnode)
		return rightnode;
	return NULL;
}
int main()
{
	//char a[] = "ABD##E#H##CF##G##";
	char a[] = "ABC##D##EF##G##";
	int i = 0;
	BTNode* root = BTCreate(a,&i);
	BTPrevOrder(root);
	printf("\n");
	BTInOrder(root);
	printf("\n");
	BTPostOrder(root);
	printf("\n");
	int size1 = BTSize(root);
	printf("%d\n", size1);
	int size2 = BTSize(root);
	printf("%d\n", size2);
	int size3 = BTLSize(root);
	printf("%d\n", size3);
	int h = BTHeight(root);
	printf("%d\n", h);
	int s = BTLKSize(root, 3);
	printf("%d\n", s);

	BTLevelOrder(root);
	printf("%d\n", BTComplete(root));

	BTDestroy(root);
	root = NULL;
	return 0;
}

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

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

相关文章

基于c++版本链队列改-Python版本链队列基础理解

基于c++版本链队列改-Python版本链队列基础理解

##基于链表的队列实现 可以将链表的“头节点”和“尾节点”分别视为“队首”和“队尾”&#xff0c;规定队尾仅可添加节点&#xff0c;队首仅可删除节点。 ##图解 ##基于链表的队列实现代码 class ListNode:"""定义链表"""def __init__(self)…
阅读更多...
Nexus搭建npm私库（角色管理、上传脚本）

Nexus搭建npm私库（角色管理、上传脚本）

安装Nexus 官网下载 https://www.sonatype.com/products/sonatype-nexus-oss-download 进入官网下载&#xff0c;最新下载方式需要输入个人信息才能下载了 选择对应的系统进行下载 Windows 推荐也下载 UNIX 版本&#xff08;Windows 版本配置比较难改&#xff09; 如果没有下…
阅读更多...
​LeetCode解法汇总2477. 到达首都的最少油耗

​LeetCode解法汇总2477. 到达首都的最少油耗

目录链接&#xff1a; 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目&#xff1a; https://github.com/September26/java-algorithms 原题链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 描述&#xff1a; 给你一棵 …
阅读更多...
org.springframework.jdbc.datasource.lookup.AbstractRoutingDataSource

org.springframework.jdbc.datasource.lookup.AbstractRoutingDataSource

DynamicDataSource-CSDN博客 /** Copyright 2002-2020 the original author or authors.** Licensed under the Apache License, Version 2.0 (the "License");* you may not use this file except in compliance with the License.* You may obtain a copy of the L…
阅读更多...
排序算法基本原理及实现2

排序算法基本原理及实现2

&#x1f4d1;打牌 &#xff1a; da pai ge的个人主页 &#x1f324;️个人专栏 &#xff1a; da pai ge的博客专栏 ☁️宝剑锋从磨砺出&#xff0c;梅花香自苦寒来 &#x1f324;️冒泡排序 &#x1…
阅读更多...
解决mybatis-plus中，当属性为空的时候，update方法、updateById方法无法set null，直接忽略了

解决mybatis-plus中，当属性为空的时候，update方法、updateById方法无法set null，直接忽略了

问题描述 当indexId set 22的时候是可以set的 我们发现sql语句也是正常的 表中数据也被更改了 但是当我们indexId为空的时候 sql语句中没有了set indexId这一属性。。 既然属性都没了&#xff0c;表是肯定没做修改的 问题解决 在实体类对应的字段上加注解TableField(strategy…
阅读更多...
每日一练【有效三角形的个数】

每日一练【有效三角形的个数】

一、题目描述 611. 有效三角形的个数 给定一个包含非负整数的数组 nums &#xff0c;返回其中可以组成三角形三条边的三元组个数。 示例 1: 输入: nums [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3示例 2: 输入: nums [4,2…
阅读更多...
《WebGIS快速开发教程》第5版“惊喜”更新啦

《WebGIS快速开发教程》第5版“惊喜”更新啦

我的书籍《WebGIS快速开发教程》第5版&#xff0c;经过忙碌的编写&#xff0c;终于发布啦&#xff01; 先给大家看看新书的封面&#xff1a; 这次的封面我们经过了全新的设计&#xff0c;不同于以往的任何一个版本。从封面就可以看出第5版肯定有不小的更新。 那么我们话不多说…
阅读更多...
ChatGPT，作为一种强大的自然语言处理模型，具备显著优势，能够帮助您在各个领域取得突破

ChatGPT，作为一种强大的自然语言处理模型，具备显著优势，能够帮助您在各个领域取得突破

2023年随着OpenAI开发者大会的召开&#xff0c;最重磅更新当属GPTs&#xff0c;多模态API&#xff0c;未来自定义专属的GPT。微软创始人比尔盖茨称ChatGPT的出现有着重大历史意义&#xff0c;不亚于互联网和个人电脑的问世。360创始人周鸿祎认为未来各行各业如果不能搭上这班车…
阅读更多...
Linux服务器部署XXL-JOB

Linux服务器部署XXL-JOB

参考文档及下载地址&#xff1a;分布式任务调度平台XXL-JOB 1 从git拉取XXL-JOB代码 我们的大部分变动&#xff0c;是发生在xxl-job-admin&#xff0c;最终将这个模块打包成jar包部署在linux服务器上。 2 执行数据库脚本 doc\db\tables_xxl_job.sql 3 修改pom文件&#xff0c…
阅读更多...
【Linux】信号的保存和捕捉

【Linux】信号的保存和捕捉

文章目录 一、信号的保存——信号的三个表——block表&#xff0c;pending表&#xff0c;handler表sigset_t信号集操作函数——用户层sigprocmask和sigpending——内核层 二、信号的捕捉重谈进程地址空间&#xff08;第三次&#xff09;用户态和内核态sigaction可重入函数volat…
阅读更多...
语义分割 LR-ASPP网络学习笔记 （附代码）

语义分割 LR-ASPP网络学习笔记 （附代码）

论文地址&#xff1a;https://arxiv.org/abs/1905.02244 代码地址&#xff1a;https://github.com/WZMIAOMIAO/deep-learning-for-image-processing/tree/master/pytorch_segmentation/lraspp 1.是什么&#xff1f; LR-ASPP是一个轻量级语义分割网络&#xff0c;它是在Mobil…
阅读更多...
如何做好软文推广的选题？媒介盒子分享常见套路

如何做好软文推广的选题？媒介盒子分享常见套路

选题是软文推广的重中之重&#xff0c;主题选得好&#xff0c;不仅能够戳到用户&#xff0c;提高转化率&#xff0c;还能让各位运营的写作效率大幅度提升&#xff0c;今天媒介盒子就来和大家分享软文选题的常见套路&#xff0c;助力各位品牌进行选题。 一、 根据产品选题 软文…
阅读更多...
安卓开发APP应用程序和苹果iOS开发APP应用程序有什么区别？

安卓开发APP应用程序和苹果iOS开发APP应用程序有什么区别？

随着智能手机和平板电脑在全球的普及&#xff0c;APP移动应用已成为日常生活中不可或缺的组成部分。从社交网络到电子商务平台&#xff0c;从个人理财到游戏娱乐&#xff0c;APP几乎渗透了人们所有的活动领域。在开发APP时&#xff0c;开发者通常要面对两大主流平台&#xff1a…
阅读更多...
鸿蒙4.0开发笔记之ArkTS语法基础的UI描述、基础组件的使用与如何查看组件是否有参数（八）

鸿蒙4.0开发笔记之ArkTS语法基础的UI描述、基础组件的使用与如何查看组件是否有参数（八）

文章目录 一、声明式UI描述1、无/有参数组件2、如何查看组件是否有参数 二、Image组件的使用三、组件的属性设置四、补充1、使用组件的成员函数配置组件的事件方法2、配置子组件3、多组件嵌套 一、声明式UI描述 在HarmonyOS的ArkTS语法中&#xff0c;万物皆组件。ArkTS以声明方…
阅读更多...
Spring-Boot---配置文件

Spring-Boot---配置文件

文章目录 配置文件的作用配置文件的格式PropertiesProperties基本语法读取Properties配置文件 ymlyml基本语法读取yml配置文件 Properties VS Yml 配置文件的作用 整个项目中所有重要的数据都是在配置文件中配置的&#xff0c;具有非常重要的作用。比如&#xff1a; 数据库的…
阅读更多...
【TiDB理论知识09】TiFlash

【TiDB理论知识09】TiFlash

一 TiFlash架构 二 TiFlash 核心特性 TiFlash 主要有 异步复制、一致性、智能选择、计算加速 等几个核心特性。 1 异步复制 TiFlash 中的副本以特殊角色 (Raft Learner) 进行异步的数据复制&#xff0c;这表示当 TiFlash 节点宕机或者网络高延迟等状况发生时&#xff0c;Ti…
阅读更多...
SCAU:18049 迭代法求平方根

SCAU:18049 迭代法求平方根

18049 迭代法求平方根 时间限制:1000MS 代码长度限制:10KB 提交次数:0 通过次数:0 题型: 填空题 语言: G;GCC;VC Description 使用迭代法求a的平方根。求平方根的迭代公式如下&#xff0c;要求计算到相邻两次求出的x的差的绝对值小于1E-5时停止&#xff0c;结果显示4位小…
阅读更多...
神经网络模型流程与卷积神经网络实现

神经网络模型流程与卷积神经网络实现

神经网络模型流程 神经网络模型的搭建流程&#xff0c;整理下自己的思路&#xff0c;这个过程不会细分出来&#xff0c;而是主流程。 在这里我主要是把整个流程分为两个主流程&#xff0c;即预训练与推理。预训练过程主要是生成超参数文件与搭设神经网络结构&#xff1b;而推理…
阅读更多...
Redis集群：Sentinel哨兵模式（图文详解）

Redis集群：Sentinel哨兵模式（图文详解）

在 Redis 主从复制模式中&#xff0c;因为系统不具备自动恢复的功能&#xff0c;所以当主服务器&#xff08;master&#xff09;宕机后&#xff0c;需要手动把一台从服务器&#xff08;slave&#xff09;切换为主服务器。在这个过程中&#xff0c;不仅需要人为干预&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站