首页 > 其他分享 >数据结构：二叉树(链式结构)

数据结构：二叉树(链式结构)

时间：2024-08-02 11:28:45浏览次数：16  
标签：遍历 return BTNode 二叉树 链式 数据结构 root 节点

文章目录

1. 二叉树的链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成：数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，三叉链在结构上比二叉链多了一个指向父节点的指针域。

请添加图片描述
在这里先使用二叉链来实现二叉树

2. 二叉树的创建和实现相关功能

2.1 创建二叉树

用链表来实现二叉树，每个链表结点都由一个数据域和左右指针域组成

//定义二叉树的链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode {
	BTDataType data;//存储数据
	struct BinaryTreeNpde* left;//指向左孩子结点的指针
	struct BinaryTreeNode* right;//指向右孩子结点的指针
}BTNode;

接下来我们来实现创建节点的函数：

首先使用malloc函数创建一个节点大小的空间，如果创建失败就打印错误信息，创建成功则把数据存储在新节点的数据域中，再将新节点的左右孩子指针指向空，最后返回新节点即可

//创建二叉树新节点
BTNode* buyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}

下面我们来创建一棵如图所示的二叉树
在这里插入图片描述

BTNode* CreateTree()
{
	BTNode* node1 = buyNode(1);
	BTNode* node2 = buyNode(2);
	BTNode* node3 = buyNode(3);
	BTNode* node4 = buyNode(4);
	BTNode* node5 = buyNode(5);
	BTNode* node6 = buyNode(6);
	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	node3->left = node6;
	return node1;
}

2.2 二叉树的前，中，后序遍历

下面来简单介绍一下前，中，后序遍历的规则
在这里插入图片描述
请添加图片描述
下面来根据上面所示的二叉树进行前，中，后序遍历

2.2.1 前序遍历

前序遍历就是先打印根节点的值，再遍历根节点的左子树，最后遍历根节点的右子树，也就是根左右

//前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

根据以上代码：进入函数先打印根节点存储的值，再递归左子树，左子树递归完后再递归右子树。不要忘了，如果遇到空节点记得要返回。

前序遍历的步骤：

  1. 打印根节点的值为1
  2. 递归左子树，创建根节点左孩子节点2的函数栈帧
  3. 打印节点2的值为2，创建节点2的左孩子节点4的函数栈帧
  4. 打印节点4的值为4，创建节点4的左孩子节点的函数栈帧
  5. 节点4的左孩子节点为空，返回节点4的函数栈帧
  6. 创建节点4的右孩子节点的函数栈帧
  7. 节点4的右孩子节点为空，返回节点4的函数栈帧
  8. 节点4的函数栈帧被销毁，返回节点2的函数栈帧
  9. 创建节点2的右孩子节点5的函数栈帧
  10. 打印节点5的值为5，创建节点5的左孩子节点的函数栈帧
  11. 节点5的左孩子节点为空，返回节点5的函数栈帧
  12. 创建节点5的右孩子节点的函数栈帧
  13. 节点5的右孩子节点为空，返回节点5的函数栈帧
  14. 节点5的函数栈帧被销毁，返回节点2的函数栈帧
  15. 节点2的函数栈帧被销毁，返回根节点的函数栈帧
  16. 创建根节点的右孩子节点3的函数栈帧
  17. 打印节点3的值为3，创建节点3的左孩子节点6的函数栈帧
  18. 打印节点6的值为6，创建节点6的左孩子节点的函数栈帧
  19. 节点6的左孩子节点为空，返回节点6的函数栈帧
  20. 创建节点6的右孩子节点的函数栈帧
  21. 节点6的右孩子节点为空，返回节点6的函数栈帧
  22. 节点6的函数栈帧被销毁，返回节点3的函数栈帧
  23. 创建节点3的右孩子节点的函数栈帧
  24. 节点3的右孩子节点为空，返回节点3的函数栈帧
  25. 节点3的函数栈帧被销毁，返回根节点的函数栈帧
  26. 根节点的函数栈帧被销毁

所以前序遍历的结果为：1 2 4 5 3 6

中序遍历和后序遍历与前序遍历的思路一样，只是打印节点的值和递归左右子树的顺序不同而已

2.2.2 中序遍历

思路：先遍历根节点的左子树，再打印根节点的值，最后遍历根节点的右子树，也就是左根右

中序遍历的结果：4 2 5 1 6 3

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

2.2.3 后序遍历

思路：先遍历根节点的左子树，再遍历根节点的右子树，最后打印根节点的值，也就是左右根

后序遍历的结果：4 5 2 6 3 1

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

2.3 二叉树节点个数

思路：先递归根节点的左子树，再递归根节点的右子树，如果递归到空节点就返回0，最后返回左子树节点个数和右子树节点个数的和再加一

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

2.4 二叉树叶子结点个数

思路：第一种情况：如果递归到的当前节点为空就返回0，第二种情况：如果节点的左右子树为空时说明该节点为叶子节点则返回1，第三种情况：如果递归到的节点既不是空又不是叶子节点，则继续递归该节点的左右子树，即返回该节点左右子树的叶子节点 return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(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);
}

2.5 二叉树第k层结点个数

思路：因为根节点是第一层，所以每次向下遍历时将k减一，当k=1时当前节点就是在第k层，返回1即可，所以只需一直递归节点的左右子树，每次递归节点的左右子树时还要让k减一。当递归到的节点为空时，只需返回0即可，要先判断节点为不为空，如果不为空再判断当前节点是不是在第k层。

//二叉树第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);
}

2.6 二叉树的深度/高度

思路：因为二叉树的左右子树的高度可能不一样，所以要分开递归二叉树的左右子树，然后再取最大值即可。当递归到空节点时返回0，否则继续递归当前节点的左右子树，最后返回左右子树深度的最大值再加一(因为当前的根节点也是一层)

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

2.7 二叉树查找值为x的结点

思路：先遍历根节点的左子树，如果找到了值为x的节点就返回该节点的地址，右子树也无需再遍历了，如果没有找到再遍历右子树，如果找到了就返回该节点的地址，没有找到则返回空。再遍历的过程中，先判断节点是否为空，如果为空就返回空，不为空的话再判断该节点的值是不是x，如果是就返回该节点的地址，如果不是就继续遍历该节点的左右子树。

//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftfind = BinaryTreeFind(root->left, x);
	if (leftfind)
	{
		return leftfind;
	}
	BTNode* rightfind = BinaryTreeFind(root->right, x);
	if (rightfind)
	{
		return rightfind;
	}
	return NULL;
}

2.8 层序遍历

这里需要借助队列，不熟悉的可以看一下数据结构—队列

层序遍历是指从根节点开始一层一层遍历二叉树，从上至下，从左至右，依次访问节点，如下图，该二叉树的层序遍历结果为：1 2 3 4 5 6

请添加图片描述
使用队列这个数据结构来实现层序遍历，队列的特点是先进先出。首先将根节点放入队列中，再将根节点出队，最后将根节点的左右孩子节点入队。将根节点的左孩子2出队，然后将根节点的左孩子2的左右孩子节点入队，以此类推……一直到队列为空

在这里插入图片描述

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

2.9 判断二叉树是否为完全二叉树

思路：同样还是借助队列这个数据结构，与层序遍历不同的是，当节点的左右孩子节点为空时也要进行入队操作，当队头为空时，就退出循环，然后还需要判断队列里有没有不为空的节点，如果有说明二叉树不为完全二叉树，如果没有说明二叉树为完全二叉树

//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	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)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

2.10 二叉树的销毁

思路：因为要销毁整个二叉树包括根节点，所以这里传递的是二级指针去接收一级指针的地址，这样就实现了形参改变实参。先销毁根节点的左子树和右子树，也就是递归到叶子节点开始销毁，然后往上一层一层地进行销毁，最后再销毁根节点。

//二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}

3. 源代码

Tree.h头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//定义二叉树的链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode {
	BTDataType data;//存储数据
	struct BinaryTreeNpde* left;//指向左孩子结点的指针
	struct BinaryTreeNode* right;//指向右孩子结点的指针
}BTNode;

//创建二叉树新节点
BTNode* buyNode(BTDataType x);
//创建一个二叉树
BTNode* CreateTree();
//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//二叉树结点个数
int BinaryTreeSize(BTNode* root);
//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
//二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);
//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
//二叉树销毁
void BinaryTreeDestory(BTNode** root);
//层序遍历
void LevelOrder(BTNode* root);
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

Tree.c源文件

#include "Tree.h"
#include "Queue.h"
//创建二叉树新节点
BTNode* buyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}
//前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}
//二叉树结点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + 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);
}
//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftfind = BinaryTreeFind(root->left, x);
	if (leftfind)
	{
		return leftfind;
	}
	BTNode* rightfind = BinaryTreeFind(root->right, x);
	if (rightfind)
	{
		return rightfind;
	}
	return NULL;
}
//二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}
//层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);
		QueuePop(&q);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	QueueDestroy(&q);
}
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	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)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

test.c源文件

#include "Tree.h"

BTNode* CreateTree()
{
	BTNode* node1 = buyNode(1);
	BTNode* node2 = buyNode(2);
	BTNode* node3 = buyNode(3);
	BTNode* node4 = buyNode(4);
	BTNode* node5 = buyNode(5);
	BTNode* node6 = buyNode(6);
	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	node3->left = node6;
	return node1;
}

void BinaryTreeTest01()
{
	BTNode* node1 = CreateTree();
	PreOrder(node1);
	printf("\n");
	InOrder(node1);
	printf("\n");
	PostOrder(node1);
	printf("\n");
	printf("%d\n", BinaryTreeSize(node1));
	printf("%d\n", BinaryTreeLeafSize(node1));
	printf("第%d层结点个数为：%d\n", 3, BinaryTreeLevelKSize(node1, 3));
	printf("%d\n", BinaryTreeDepth(node1));
	if (BinaryTreeFind(node1, 10) == NULL)
	{
		printf("没有找到\n");
	}
	else
	{
		printf("找到了\n");
	}
	LevelOrder(node1);
	printf("\n");
	printf("%s\n", BinaryTreeComplete(node1) == true ? "是完全二叉树" : "不是完全二叉树");
	BinaryTreeDestory(&node1);
}
int main()
{
	BinaryTreeTest01();
	return 0;
}

对以上内容有不同看法的欢迎来讨论，希望对大家的学习有帮助，多多支持哦！

标签：遍历,return,BTNode,二叉树,链式,数据结构,root,节点
From： https://blog.csdn.net/2301_79601095/article/details/140822613

相关文章

  • 数据结构C语言---文件的加密和解密
    本篇的主要目的是利用所学的数据结构的知识对一个任意文件进行加密和解密。在文件加密过程中，常用的数据结构包括哈希表、树结构（如二叉搜索树、哈夫曼树）、堆、链表等。选择合适的数据结构取决于加密算法的需求和特性。选择合适的加密算法和数据结构对保障数据安全至关重要。常......
  • 图解平衡二叉树
    平衡二叉树平衡二叉树的背景由于一些众所周知的原因,我们选择了平衡二叉树,好吧,其实就是因为对二叉搜索树的限制太少了,导致在一些特殊的情况下,二叉搜索树不太听话,查找,插入与删除的时间均变成了\(O(n)\)也可以认为,熵增就会更加有序,熵减就会更加自由,这里我们......
  • 数据结构实验----邻接表和拓扑排序
    一.实验目的1.理解拓扑排序的特性和算法；2.通过构造图的邻接表，掌握拓扑排序算法。二.实验内容1.建立邻接表存储的图；2.对图进行拓扑排序；3.输出拓扑排序序列。三.代码#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMAXSIZE10#defineOK1#......
  • 数据结构实验---散列表
    一.实验目的1.理解散列表的存储结构；2.掌握常用散列函数构造方法和处理冲突方法；3.在散列表上实现查找的算法。二.实验内容为小于n个关键字设计一个散列表，使得查找成功时平均查找长度<2.0，要求完成相应的散列表建立和查找。假设关键字为整型数据，散列函数用除留余数法，采用开放......
  • 【数据结构】排序
    目录1.前言2.排序的概念及引用2.1排序的概念2.2常见的排序算法 3.常见排序算法的实现3.1插入排序3.1.1基本思想 3.1.2直接插入排序 3.1.3希尔排序(缩小增量排序)3.2选择排序3.2.1基本思想3.2.2直接选择排序3.2.3堆排序3.3交换排序3.3.1基本思想3.3.2冒泡排......
  • 数据结构经典测试题5
    1.intmain(){chararr[2][4];strcpy(arr[0],"you");strcpy(arr[1],"me");arr[0][3]='&';printf("%s\n",arr);return0;}上述代码输出结果是什么呢？A:you&meB:youC:meD:err答案为A因为arr是一个2行4列的二维数组，每一行可以存放最多三个......
  • DAY 15 二叉树part03
      110.平衡二叉树（优先掌握递归）题目链接/文章讲解/视频讲解：https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91.html 独立完成，感觉还比较好理解12classSolution{13public:14boolisBalanced(TreeNode*root){15if(......
  • 4.Redis数据结构&通用命令
    Redis数据结构Redis是一个键值对的数据库。key：大多都是Stringvalue:类型多种多样 Redis通用命令keys:查看所有的key不建议在生产环境上使用keys命令，因为redis是单线程的，keys命令会搜索很长一段时间，搜索的期间redis无法执行其他的命令，等于服务被阻塞了，影响redis的性......
  • 【每日一题 | 数据结构】时间复杂度计算
    题目解题方法对于二重循环求时间复杂度：写出外层i的变化值写出内层循环语句执行次数（看j）对次数求和找到频度和n的关系笔记视频跳转：【每日一题|数据结构】时间复杂度计算......
  • 数据结构----树，二叉树，哈夫曼树相关概念及其实现
    树形结构概述1分层逻辑结构所谓的分层逻辑结构，也称为树形逻辑结构关系，是数据结构中的一种逻辑关系结构，在该逻辑结构关系中的数据元素之间满足一对多的逻辑结构关系：起始数据节点有且仅有一个，没有直接前驱，可以有多个直接后继；末尾数据节点可以多个，有且仅有一个直接前驱，......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99