1. Toy模板网首页
  2. > Toy博客

【数据结构】---几分钟简单几步学会手撕链式二叉树(下)

7月前 作者：小沈熬夜秃头中୧⍤⃝❅ 分类：Toy博客 阅读(31) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】---几分钟简单几步学会手撕链式二叉树(下)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

👧个人主页：@小沈熬夜秃头中୧⍤⃝❅
😚小编介绍：欢迎来到我的乱七八糟小星球🌝
📋专栏：数据结构
🔑本章内容：手撕链式二叉树
送给各位💌：成为更好的自己才是应该做的事
记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~

提示：以下是本篇文章正文内容，下面案例可供参考

🌟一、二叉树链式结构的实现

🌏1.1 二叉树叶子节点个数

💫代码：

int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

💫流程图：

【数据结构】---几分钟简单几步学会手撕链式二叉树(下)

🌏1.2 二叉树的高度

💫第一种写法(不支持)：

📒代码：
int BTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	return BTreeHeight(root->left) > BTreeHeight(root->right) ?
		BTreeHeight(root->left) + 1 : BTreeHeight(root->right) + 1;
}
📒流程图：

由图可知，每次比较完后并没有记录数据而是再次调用当树跃高底层最大的那个函数调用的次数就越多，所以这种方法虽然对但是耗时太长，而底层也就变成了所谓的天选打工人【数据结构】---几分钟简单几步学会手撕链式二叉树(下)

💫第二种写法：

📒代码：
int BTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftHeight = BTreeHeight(root->left);
	int rightHeight = BTreeHeight(root->right );
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
📒流程图：

每次调用都记录上数据，这样比较完直接返回大的那个+1；【数据结构】---几分钟简单几步学会手撕链式二叉树(下)

🌏1.3 二叉树第K层的节点个数

💫代码：

int BTreeLevelKSize(BTNode* root,int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BTreeLevelKSize(root->left, k - 1) 
		+ BTreeLevelKSize(root->right, k - 1);
}

💫流程图：

【数据结构】---几分钟简单几步学会手撕链式二叉树(下)
【数据结构】---几分钟简单几步学会手撕链式二叉树(下)

🌏1.4 二叉树查找值为x的节点

💫第一种写法(错误示范)：

📒代码：
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data  == x)
		return root;
	BTreeFind(root->left, x);
	BTreeFind(root->right, x);
}
📒流程图：

【数据结构】---几分钟简单几步学会手撕链式二叉树(下)

💫第二种写法(正确写法)：

📒代码：
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data  == x)
		return root;
	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;
	BTNode* ret2 = BTreeFind(root->left, x);
	if (ret2)
		return ret2;
	return NULL;
}
📒流程图：

【数据结构】---几分钟简单几步学会手撕链式二叉树(下)

🌏1.5 层序遍历

📒代码：
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	printf("\n");
	QueueDestroy(&q);
}
📒思路流程(多种嵌套)：

对于层序遍历,可以采用队列的思想(先进先出)
具体核心思想：上一层出时带下一层进队列所以进入时不能存储树节点的值而是存储树节点指针
【数据结构】---几分钟简单几步学会手撕链式二叉树(下)
【数据结构】---几分钟简单几步学会手撕链式二叉树(下)

🌏1.6 二叉树销毁(采用后序)

📒代码：
void BTreeDestroy(BTNode* root)
{
	if (root == NULL)
		return;
	BTreeDestroy(root->left);
	BTreeDestroy(root->right);
	free(root);
}
📒流程图：

【数据结构】---几分钟简单几步学会手撕链式二叉树(下)

🌏1.7 判断二叉树是否是完全二叉树

📒代码：
bool BTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//遇到空就跳出
		if (front == NULL)
			break;

		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	//检查后面的节点有没有非空
	//有非空不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)//往外拿数出现非空就不是完全二叉树
		{
			return false;
			QueueDestroy(&q);
		}
	}
	return true;
	QueueDestroy(&q);
}
📒思路流程：

和上述层序遍历一样，采用队列思想，上一层出时带下一层进入，出现NULL时跳出然后将里面的数字往外拿，出现非空不是完全二叉树【数据结构】---几分钟简单几步学会手撕链式二叉树(下)>N代表空【数据结构】---几分钟简单几步学会手撕链式二叉树(下)

🌟二、二叉树链式结构完整代码

//Queue.h
#pragma once
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>

typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode//每个节点的结构
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

//初始化
void QueueInit(Queue* pq);
//释放
void QueueDestroy(Queue* pq);
//尾插(入队)
void QueuePush(Queue* pq, QDataType x);
//头删(出队)
void QueuePop(Queue* pq);
//队头数据
QDataType QueueFront(Queue* pq);
//队尾数据
QDataType QueueBack(Queue* pq);
//数据个数
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);


//Queue.c
#include"Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

void QueueDestroy(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 QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->ptail == NULL)
	{
		assert(pq->phead == NULL);

		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}


	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//一个队列
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = NULL;
		pq->ptail = NULL;
	}
	//多个队列
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
	/*return pq->phead == NULL && pq->ptail == NULL;*/
	return pq->size == 0;
}


//Test.c
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
#include"Queue.h"

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	node5->left = node7;
	return node1;
}


void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

//二叉树节点个数 --- 遍历计数
//int size = 0;
//void BTreeSzie(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return size;
//	}
//	size++;
//	BTreeSzie(root->left);
//	BTreeSzie(root->right);
//	return size;
//}

//int BTreeSzie(BTNode* root)
//{
//	static int size = 0;
//	//printf("%p,%d\n", &size,size);
//	if (root == NULL)
//	{
//		return size;
//	}
//	size++;
//	BTreeSzie(root->left );
//	BTreeSzie(root->right );
//	return size;
//}


int BTreeSzie(BTNode* root)
{
	return root == NULL ? 0 :
		BTreeSzie(root->left)
		+ BTreeSzie(root->right) + 1;
}

//二叉树叶子节点个数
int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return BTreeLeafSize(root->left)
		+ BTreeLeafSize(root->right);
}

//二叉树树的高度
int BTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftHeight = BTreeHeight(root->left);
	int rightHeight = BTreeHeight(root->right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

//二叉树第k层的节点个数
int BTreeLevelKSize(BTNode* root, int k)
{
	assert(k >= 1);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BTreeLevelKSize(root->left, k - 1)
		+ BTreeLevelKSize(root->right, k - 1);
}

//二叉树查找值为x的节点
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	/*BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;
	BTNode* ret2 = BTreeFind(root->left, x);
	if (ret2)
		return ret2;
	return NULL;*/
	//BTreeFind(root->left, x);
	//BTreeFind(root->right, x);
	//return NULL;
	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;
	return BTreeFind(root->left, x);
}

//层序遍历---用队列
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	printf("\n");
	QueueDestroy(&q);
}

void BTreeDestroy(BTNode* root)
{
	if (root == NULL)
		return;
	BTreeDestroy(root->left);
	BTreeDestroy(root->right);
	free(root);
}

//判断二叉树是否是完全二叉树
bool BTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//遇到空就跳出
		if (front == NULL)
			break;

		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	//检查后面的节点有没有非空
	//有非空不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			return false;
			QueueDestroy(&q);
		}
	}
	return true;
	QueueDestroy(&q);
}

int main()
{
	BTNode* root = CreatBinaryTree();
	PrevOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");
	//printf("BTreeSize:%d\n", BTreeSzie(root));
	//printf("BTreeSize:%d\n", BTreeSzie(root));
	//printf("BTreeSize:%d\n", BTreeSzie(root));
	/*BTreeSzie(root);
	printf("BTreeSize:%d\n", size);
	size = 0;
	BTreeSzie(root);
	printf("BTreeSize:%d\n", size);
	size = 0;
	BTreeSzie(root);
	printf("BTreeSize:%d\n", size);*/

	printf("BTreeSize:%d\n", BTreeSzie(root));
	printf("BTreeLeafSize: % d\n", BTreeLeafSize(root));
	printf("BTreeHeight: % d\n", BTreeHeight(root));
	printf("BTreeLevelKSize: % d\n", BTreeLevelKSize(root, 3));
	printf("BTreeLevelKSize: % d\n", BTreeLevelKSize(root, 2));
	

	LevelOrder(root);

	printf("BTreeComplete: % d\n", BTreeComplete(root));
	
	BTreeDestroy(root);
	root = NULL;
	return 0;
}

😽总结

【数据结构】---几分钟简单几步学会手撕链式二叉树(下)
😽Ending,今天的链式二叉树的内容就到此结束啦~，如果后续想了解更多，就请关注我吧，一键三连哦 ~文章来源地址https://www.toymoban.com/news/detail-479406.html

到了这里，关于【数据结构】---几分钟简单几步学会手撕链式二叉树(下)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】手撕顺序表

    【数据结构】手撕顺序表

    顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储； 在数组上完成数据的增删查改。  1，  静态顺序表 ：使用 定长数组 存储元素。 2.， 动态顺序表 ：使用 动态开辟 的数组存储。   静态顺序表只适用于确定知道需要存多少数

    2024年02月11日
    浏览(33)
  • 数据结构之——（手撕）顺序表

    数据结构之——（手撕）顺序表

    本章会介绍的知识点如下图：                    顺序表的结构：逻辑结构与物理结构都是内存中一块连续开辟的空间，都是11对应的线性结构。 两种定义顺序表的方式代码如下         静态的顺序表         动态的顺序表：          在这两种结构中通常我们是会

    2024年02月11日
    浏览(27)
  • 手撕数据结构之栈+例题

    手撕数据结构之栈+例题

    目录 一、栈的概念及结构 二、栈的头文件及基本框架 三、接口实现 1、对栈的初始化  2、栈的销毁 3、入栈操作 4、出栈操作  5、判断栈是否为空 6、返回栈顶元素 7、遍历栈 四、有效的括号 - 力扣（LeetCode） 题目描述：  思路： 代码： 栈：一种特殊的线性表，其只允许

    2024年02月13日
    浏览(37)
  • 【数据结构】手撕双向链表

    【数据结构】手撕双向链表

    目录 前言 1. 双向链表  带头双向循环链表的结构 2. 链表的实现 2.1 初始化 2.2 尾插 2.3 尾删 2.4 头插 2.5 头删 2.6 在pos位置之前插入 2.7 删除pos位置 3.双向链表完整源码 List.h List.c 在上一期中我们介绍了单链表，也做了一些练习题，在一些题中使用单链表会十分繁琐。因为单链

    2024年02月05日
    浏览(37)

  • 【手撕数据结构】二分查找(好多细节)

    🌈键盘敲烂，年薪30万🌈 目录 普通版本的二分查找： right只负责控制边界(少了两次比较)： 时间复杂度更稳定的版本： BSLeftmost： BSRightmost：   🏸细节1：循环判定条件是left = right ⭐细节2：mid = (left + right ) 1 原因见代码注释 改动1：while条件是left right 改动2：right = nums.len

    2024年02月05日
    浏览(36)
  • 【数据结构】手撕归并排序（含非递归）

    【数据结构】手撕归并排序（含非递归）

    目录 一，归并排序（递归） 1，基本思想  2，思路实现 二，归并排序（非递归） 1，思路实现 2，归并排序的特性总结： 1，基本思想 归并排序 （MERGE-SORT） 是建立在 归并操作 上的一种 有效的排序算法 ,该算法是采用 分治法（Divide and Conquer） 的一个非常典型的应用； 将 已

    2024年02月08日
    浏览(36)
  • 数据结构---手撕图解双向循环链表

    数据结构---手撕图解双向循环链表

    在前面学完单链表后，我们思考这样一个问题，单链表和顺序表比起来，功能确实相当强大，有很多优势，但是于此同时，我们也应思考下面的问题 单链表有什么不足的地方？ 如果你把单链表的各个函数都自己实现过，那么下面的问题你一定有相同的感悟 单链表实现尾插尾

    2024年02月15日
    浏览(43)
  • 数据结构：手撕图解双向循环链表

    数据结构：手撕图解双向循环链表

    在前面学完单链表后，我们思考这样一个问题，单链表和顺序表比起来，功能确实相当强大，有很多优势，但是于此同时，我们也应思考下面的问题 单链表有什么不足的地方？ 如果你把单链表的各个函数都自己实现过，那么下面的问题你一定有相同的感悟 单链表实现尾插尾

    2024年02月15日
    浏览(76)
  • 数据结构之队列详解（C语言手撕）

    数据结构之队列详解（C语言手撕）

    🎉个人名片： 🐼作者简介：一名乐于分享在学习道路上收获的大二在校生 🙈个人主页🎉：GOTXX 🐼个人WeChat：ILXOXVJE 🐼本文由GOTXX原创，首发CSDN🎉🎉🎉 🐵系列专栏：零基础学习C语言----- 数据结构的学习之路----C++的学习之路 🐓每日一句：如果没有特别幸运，那就请特

    2024年03月10日
    浏览(54)
  • 【数据结构】手撕排序NO.1----排序初识

    【数据结构】手撕排序NO.1----排序初识

    目录  一. 前言 二. 排序的概念及运用         2.1 排序的概念         2.2 排序的运用         2.3 常见的排序算法 三. 冒泡and选择排序         3.1 冒泡排序         3.2 选择排序 四. 各大排序算法的复杂度和稳定性        从本期开始，我们的数据结构将迎来一个新的

    2024年02月16日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包