二叉树各种函数的实现

这篇具有很好参考价值的文章主要介绍了二叉树各种函数的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

如果你觉得迷茫,那就尽可能选择比较困难的路。
二叉树各种函数的实现,数据结构知识讲解,数据结构,算法,学习
目录
 

前言:

🍀一.通过前序遍历创建二叉树

🍁二.二叉树的四种遍历 

🍂1.二叉树的前序遍历

🌼2.二叉树的中序遍历 

🍌3.二叉树的后序遍历 

🍊4.二叉树的层序遍历

🍍三.二叉树的结点个数

🍎四.二叉树的叶子结点的个数 

🍉五.二叉树的k层结点的个数 

🍋六.二叉树查找值为x的节点 

🌸七.判断二叉树是否是完全二叉树

🍇八.二叉树的销毁 

🍁九.全部代码:

1.Binary tree.h

2.Binary tree.c

3.test.c

4.Queue.h

5.Queue.c


前言:

最近一个月,都在备战期末考试,也就一直没有敲什么代码,也没有写CSDN,所以现在期末考试考完了,自己这一个月没有白努力吧,感觉是考的很好的,也可能是学校出的题真的很简单。反正都考完了,只要不挂科就行。接下来虽然要在学校上课十多天才放假,但是都是计算机的专业课,从现在到暑假这差不多两个多月吧,没有其他的羁绊了全身心的投入到敲代码上了,现在差不多把数据结构给学完了,就差二叉树的这篇文章和几个排序算法了,把这几篇博客写了之后,我也就会投入到C++的和Linux的学习中去了,老铁们,暑假准备好一起沉淀了吗?我们一起加油啊。话不多说,进入今天的主题:二叉树的各种函数的实现。

🍀一.通过前序遍历创建二叉树

关于什么是二叉树的前中后层序遍历?
前序遍历:先根结点,再左子树,最后再右子树。
中序遍历:先左子树,再根结点,最后再右子树。
后序遍历:先右子树,再左子树,最后再根结点。
层序遍历:也就是二叉树一层一层的遍历。层序遍历也是最好理解的。

关于前中后序遍历,也就是看根结点的访问位置,根最先访问就是前序,根在中间访问就是中序,根在最后访问就是后序遍历。
这里我也不过多赘述了,这里有一篇关于前中后层序遍历很优质的讲解,动图的方式呈现,非常的好理解:数据结构——二叉树先序、中序、后序及层次四种遍历(C语言版)。

这里我们通过前序遍历把一个字符串给构建成二叉树。我们通过画图来理解一下。假设给的字符串为ABD##E#H##CF##G##。(这里的#就表示为空指针NULL
二叉树各种函数的实现,数据结构知识讲解,数据结构,算法,学习

依靠前序遍历其实是很好就可以把这个二叉树给构建出来的,难的就是如何通过代码来实现这个功能。这里我们使用递归来实现。注意:后面的函数实现基本上都是靠递归来实现,所以递归在二叉树这个地方是非常重要的,不理解就多画图,反正就是反复反复的理解,熟能生巧。

BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
//这里必须传地址pi过来
	if (a[*pi] == '#')//如果当前这个字符是#,那么就表示它是NULL。
	{
	   (*pi)++;
	    return NULL;
	}
		BTNode * root = BuyTreeNode(a[*pi]);//创建一个结点
		(*pi)++;
		//创建左子树和右子树
		root->left = BinaryTreeCreate(a, pi);
		root->right = BinaryTreeCreate(a, pi);
		return root;
}

函数递归本身就是不断的创建函数的栈帧,我们需要不断遍历字符串,然后构建出二叉树,这里我们必须传指针*pi过来,这样每一次创建的函数栈帧里面的地址解引用找到的都是同一个pi,这样就可以遍历数组了。如果不传指针过来,每一次函数递归创建的函数栈帧里面的pi++,是不会影响上一次的pi,这样就无法达到遍历字符串数组了。

创建结点的函数:

BTNode* BuyTreeNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc");
		return NULL;
	}
	node->data = x;
	node->right = node->left = NULL;
	return node;
}

通过这个前序遍历字符串数组如何就将字符串构建为二叉树了呢?还是一样,我们把二叉树的递归展开图画一下。
二叉树各种函数的实现,数据结构知识讲解,数据结构,算法,学习

就这样我们就通过前序遍历字符串数组把二叉树给构建出来了。 

🍁二.二叉树的四种遍历 

🍂1.二叉树的前序遍历

先创建一个结构体,一个结点存放一个值,左指针和右指针。

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)//当root为NULL,那么直接打印出来就是。
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);//先打印根结点再是左子树,最后再右子树
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}

只需要这么简单的代码,我们就可以实现,打印前序遍历了,同样这是通过递归来实现的,我们还是画图来理解一下。 
二叉树各种函数的实现,数据结构知识讲解,数据结构,算法,学习

🌼2.二叉树的中序遍历 

有了前序遍历的基础,那么中序,后序遍历也就迎刃而解了,只需要改变一下,打印根节点的位置即可,非常的简单。

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%c ", root->data);
	BinaryTreeInOrder(root->right);
}

🍌3.二叉树的后序遍历 

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c ", root->data);
}

写了三个遍历函数,我们可以先测试一下,看看我们写得有问题没有。
二叉树各种函数的实现,数据结构知识讲解,数据结构,算法,学习 可以看出,肥肠的完美。

🍊4.二叉树的层序遍历

二叉树各种函数的实现,数据结构知识讲解,数据结构,算法,学习
层序遍历就是一层一层的遍历,如图所示,层序遍历的结果就是ABCDEFGH。
这个要这么实现呢?这里我们会用到队列来实现。一样我们通过画图来看看,通过队列的先进先出,如何进行层序遍历。
二叉树各种函数的实现,数据结构知识讲解,数据结构,算法,学习

就这样,通过队列的先进先出,即可实现层序遍历了。
这里队列里面存放的是二叉树的结点,而不是值了,所以队列的typedef我们需要改一下。

typedef struct BinaryTreeNode* QDataType;
//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)//结点不为空指针,即入队列
		QueuePush(&q, root);
	while (!QueueEmpty(&q))//如果队列不为空,我们就可以继续操作
	{
		BTNode* front = QueueFront(&q);//队列头的结点
		QueuePop(&q);//出队列
		printf("%c ", front->data);

		if (front->left)//依次往队列入左右孩子
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	QueueDestroy(&q);

二叉树各种函数的实现,数据结构知识讲解,数据结构,算法,学习就这样,我们就把二叉树的四种遍历给搞清楚了。不理解,反正就是不断画图,多来几遍,过一段时间又来做做,直到理解透彻。

🍍三.二叉树的结点个数

这里我们使用分治法,也就是递归嘛,计算总的结点数,只需要计算根结点+左子数和右子树的结点数,然后计算左子树和右子树的方法又是一样。分而治之,把大问题化成小问题。

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

不理解就画递归展开图。
二叉树各种函数的实现,数据结构知识讲解,数据结构,算法,学习

就这样进行下去,就可以把二叉树给遍历完,然后算出该二叉树的结点个数。
二叉树各种函数的实现,数据结构知识讲解,数据结构,算法,学习

🍎四.二叉树的叶子结点的个数 

这个和求结点的个数的方法是差不多的,只是叶子结点比较特殊,叶子结点就是度为0的结点,没有孩子的结点。

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)//当左右孩子都为NULL,即为叶子结点
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

这里我就不画递归展开图了,不理解的可以自己动手画画。

🍉五.二叉树的k层结点的个数 

这里有一个难点,如何找这个结点时第几层的,也就是假如k是3层,我们如何找出结点就是第3层的,这是一个比较难受的地方。
我们可以倒着来,根结点为第k层,然后往下k依次递减,当k==1时,即时我们要找到的k层结点,然后计算该层的结点即可。

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)//当为空时,不管你第几层,都是0个结点
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->left, k - 1) +
		BinaryTreeLevelKSize(root->right, k - 1);
}

二叉树各种函数的实现,数据结构知识讲解,数据结构,算法,学习 

就这样,就可以把二叉树的第k个结点数给求出来了。
二叉树各种函数的实现,数据结构知识讲解,数据结构,算法,学习 

🍋六.二叉树查找值为x的节点 

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode * root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)//找到了就直接返回
		return root;

	BTNode* ret1 = BinaryTreeFind(root->left, x);//这里记得保存结点
	if (ret1)
		return ret1;
	BTNode*ret2 = BinaryTreeFind(root->right, x);
	if (ret2)
		return ret2;
	return NULL;
}

注意这里返回,不是直接返回到最外面,而是返回到上一层函数的栈帧,一层一层的返回。

🌸七.判断二叉树是否是完全二叉树

什么是完全二叉树?之前我们学过的,也就是一种特殊的二叉树,其中除了最后一层以外,其他所有层的节点都被完全填满,并且所有节点都尽可能地向左对齐。
其中完全二叉树不一定是完美二叉树,而完美二叉树一定是完全二叉树。

这里又会用到层序遍历时,使用到的队列了,当遇到空时,我们就退出循环,然后判断队列中是否还有字符,如果还有字符,那么这颗树就不是完全二叉树,因为如果是完全二叉树,当把所有的字符都出队列了之后,才会遇到NULL。

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if(root)
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)//遇到NULL就退出循环
			break;
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)//如果队列中还有字符,那么这颗树肯定就不是完全二叉树
		{
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

二叉树各种函数的实现,数据结构知识讲解,数据结构,算法,学习

🍇八.二叉树的销毁 

销毁二叉树,我们还要注意顺序,这里我们使用后序遍历,先销毁左子树,再销毁右子树,最后再是根节点。而且这里注意要传二级指针,因为销毁了之后,我们要改变该指针,将free的指针,指向NULL。那么就需要指针的指针,也就是二级指针。文章来源地址https://www.toymoban.com/news/detail-555218.html

// 二叉树销毁
void BinaryTreeDestroy(BTNode** root)
{
	if ((*root) == NULL)
		return;
	BinaryTreeDestroy((*root)->left);//先左子树
	BinaryTreeDestroy((*root)->right);//再右子树
	free(*root);//最后再销毁根结点
	*root = NULL;
}

🍁九.全部代码:

1.Binary tree.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
 //判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
// 二叉树销毁
void BinaryTreeDestroy(BTNode** root);

2.Binary tree.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Binary tree.h"
#include"Queue.h"
BTNode* BuyTreeNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc");
		return NULL;
	}
	node->data = x;
	node->right = node->left = NULL;
	return node;
}


BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
	if (a[*pi] == '#')
	{
	   (*pi)++;
	    return NULL;
	}
		BTNode * root = BuyTreeNode(a[*pi]);
		(*pi)++;
		//创建左子树和右子树
		root->left = BinaryTreeCreate(a, pi);
		root->right = BinaryTreeCreate(a, pi);
		return root;
}

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%c ", root->data);
	BinaryTreeInOrder(root->right);
}

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c ", root->data);
}

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

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

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->left, k - 1) +
		BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode * root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)//找到了
		return root;

	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if (ret1)
		return ret1;
	BTNode*ret2 = BinaryTreeFind(root->right, x);
	if (ret2)
		return ret2;
	return NULL;
}


//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)//结点不为空指针,即入队列
		QueuePush(&q, root);
	while (!QueueEmpty(&q))//如果队列不为空,我们就可以继续操作
	{
		BTNode* front = QueueFront(&q);//队列头的结点
		QueuePop(&q);//出队列
		printf("%c ", front->data);

		if (front->left)//依次往队列入左右孩子
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	QueueDestroy(&q);
}
// 二叉树销毁
void BinaryTreeDestroy(BTNode** root)
{
	if ((*root) == NULL)
		return;
	BinaryTreeDestroy((*root)->left);//先左子树
	BinaryTreeDestroy((*root)->right);//再右子树
	free(*root);//最后再销毁根结点
	*root = NULL;
}

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if(root)
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)//遇到NULL就退出循环
			break;
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)//如果队列中还有字符,那么这颗树肯定就不是完全二叉树
		{
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Binary tree.h"
#include"Queue.h"

int main()
{
	char arr[100] = "ABD##E#H##CF##G##";
	int i = 0;
	BTNode*root= BinaryTreeCreate(arr, &i);
	printf("前序遍历结果为:\n");
	BinaryTreePrevOrder(root);
	printf("\n");

	printf("中序遍历结构为:\n");
	BinaryTreeInOrder(root);
	printf("\n");
	printf("后序遍历结果为:\n");
	BinaryTreePostOrder(root);
	printf("\n");
	printf("层序遍历为:\n");
	BinaryTreeLevelOrder(root);

	printf("\n二叉树结点的个数为:\n");
	printf("%d\n", BinaryTreeSize(root));

	printf("二叉树中叶子结点的个数为:\n");
	printf("%d\n", BinaryTreeLeafSize(root));

	BTNode* ret = BinaryTreeFind(root, 'F');
	if (ret)
		printf("找到该字符了\n");
	else
		printf("没有找到字符\n");

	printf("二叉树中第4层的结点个数为:\n");
	printf("%d\n", BinaryTreeLevelKSize(root, 4));
	if (BinaryTreeComplete(root))
	{
		printf("该二叉树是完全二叉树\n");
	}
	else
	{
		printf("该二叉树不是完全二叉树\n");
	}
	
	return 0;
}

4.Queue.h

#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
typedef struct BinaryTreeNode* QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;
	QNode* rear;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType x);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);

// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

5.Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
// 初始化队列 
#include"Queue.h"
void QueueInit(Queue* q)
{
	assert(q);
	q->front = q->rear = NULL;
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc\n");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	//当只要一个结点
	if (q->rear == NULL)
	{
		q->rear = q->front = newnode;
	}
	//当有两个结点的时候
	else
	{
		q->rear->next = newnode;
		q->rear = newnode;
	}
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->front);
	//当只要一个结点时
	if (q->front->next == NULL)
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	else//当有两个及两个以上的结点的时候
	{
		Queue* next = q->front->next;
		free(q->front);
		q->front = NULL;
		q->front = next;
	}
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->front);
	return q->front->data;
}

// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	if (q->front == NULL)
		return 1;
	else
		return 0;
}



// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	Queue* cur = q->front;
	while (cur)
	{
		Queue* next = q->front->next;
		free(cur);
		cur = next;
	}
	q->front = q->rear = NULL;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	assert(q->front);
	int count = 0;
	QNode* cur = q->front;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->rear);
	return q->rear->data;
}


 

到了这里,关于二叉树各种函数的实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构 —— 二叉树的链式结构实现】

    树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 1.有一个 特殊的结点,称为根结点 ,根节点没有前驱结点 2.除根节点外, 其余结点被分成M(M0)个互不相交

    2024年02月05日
    浏览(56)
  • 数据结构-二叉树·堆(顺序结构的实现)

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

    2024年02月05日
    浏览(46)
  • 【数据结构—二叉树的链式结构实现】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、二叉树的存储结构 二、二叉树链式结构的实现 2.1手动构建一课树 2.2二叉树的遍历 三、二叉树链式结构的实现 3.1前序遍历(递归) 3.2中序遍历(递归) 3.3后序遍历(递归) 3.4层序遍历(非递

    2024年02月03日
    浏览(58)
  • 数据结构和算法学习记录——初识二叉树(定义、五种基本形态、几种特殊的二叉树、二叉树的重要性质、初识基本操作函数)

    目录 二叉树的定义 二叉树具体的五种基本形态 1.空树 2.只有一个节点 3.有左子树,但右子树为空 4.有右子树,但左子树为空  5.左右两子树都不为空 特殊二叉树 斜二叉树 满二叉树  完全二叉树 二叉树的几个重要性质 初识二叉树的几个操作函数  二叉树T: 一个有穷的节点

    2024年02月03日
    浏览(61)
  • 数据结构之二叉树与堆以及力扣刷题函数扩展

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力 目录 1.前言 2.树 2.1概念  2.2树的相关概念 3.堆 3.1堆的概念 3.2小堆函数实现 4.力扣刷

    2024年02月04日
    浏览(40)
  • 【数据结构】二叉树——堆如何实现

    目录 一、二叉树的顺序结构 二、堆的概念及结构 三、堆的实现 四、堆的应用 4.1 堆排序 4.1.1 建堆 4.1.2 利用堆删除思想来进行排序 4.2 TOP-K问题 很多时候,我们竞争对手是我们自己,而不是别人。   普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费

    2024年02月13日
    浏览(34)
  • 【数据结构】二叉树的实现

    一棵二叉树是结点的一个有限集合,该集合分为两点: 一是为空和二是由一个根节点加上两棵别称为左子树和右子树的二叉树组成从图上看出有2个性质: 二叉树不存在度大于2的结点 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树 对于任意的二叉树都是由以下

    2024年02月02日
    浏览(38)
  • 数据结构——二叉树(堆的实现)

    目录   树概念及结构 树的相关概念 树的表示  二叉树的概念及结构   堆 堆的实现   结构体建立 初始化   添加元素  打印堆  删除堆首元素  返回首元素  判断是否为空 空间销毁  刷题找工作的好网站——牛客网 牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推,

    2024年02月11日
    浏览(44)
  • 【数据结构】二叉树的链式结构及实现

    目录 1. 前置说明 2. 二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 3. 节点个数及高度等 4. 二叉树的创建和销毁 在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,为了降低大家学习成

    2024年02月08日
    浏览(43)
  • 数据结构:二叉树的链式结构的实现

      目录  1.通过前序遍历构建二叉树 2. 二叉树的销毁  3.二叉树的遍历 4. 二叉树的节点个位和二叉树的叶子节点个位数 5. 二叉树的的k层节点数和查找值为x的节点 6. 判断二叉树是否为完全二叉树和求二叉树的高度h 二叉树的前序遍历 二叉树的中序遍历 二叉树的后序遍历

    2024年02月12日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包