1. 首页
  2. 文章中心
  3. C

C语言实现二叉树C语言实现二叉树

146 阅读 0 评论
我是靠谱客的博主 乐观手链，这篇文章主要介绍C语言实现二叉树C语言实现二叉树，现在分享给大家，希望可以做个参考。

C语言实现二叉树

今天我们来介绍一下二叉树，上一节说到堆的实现，即为一种二叉树的顺序结构的应用，通过顺序表来维护堆

二叉树也可以通过链式结构来实现，即二叉链，结构如下图所示。

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

例如下图这棵二叉树：

其二叉链存储表示如下：

下面具体通过代码来详细了解二叉链的实现过程：

  • 二叉树结构定义

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
typedef char BTDataType;
typedef struct BinaryTreeNode//二叉树节点
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

typedef struct BTree
{
	BTNode* _root;
}BTree;

  • 二叉树链表实现接口

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 创建二叉树，返回二叉树的根结点指针
BTNode* BinaryTreeCreate(BTDataType* arr, int idx);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
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);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

//二叉树高度，层数
int BinaryTreeHigh(BTNode* root);

  • 创建二叉树

在创建二叉树的过程中发现，注意：索引如果是局部变量。在递归过程中，索引无法更新
//解决方法：要么定义为全局变量，要么给指针存地址

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
BTNode* BinaryTreeCreate(BTDataType* arr, int *idx)
{
	if (arr[*idx] == '#')
	{
		(*idx)++;//索引后移
		return NULL;//为空返回null
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));//不为空创建节点,并根据当前索引赋数组值
	root->_data = arr[*idx];
	(*idx)++;//索引后移
	root->_left = BinaryTreeCreate(arr,idx);
	root->_right = BinaryTreeCreate(arr,idx);
	return root;
}

通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树，为#返回空，否则创建根结点赋值，然后递归遍历创建左子树和右子树，在回溯的过程中，注意索引需要随之变化，要么为全局变量，要么为指针变量（存地址）

  • 二叉树的销毁

复制代码
1
2
3
4
5
6
7
8
9
10
void BinaryTreeDestory(BTNode** root)
{
	if (*root)
	{
		BinaryTreeDestory(&((*root)->_left));
		BinaryTreeDestory(&((*root)->_right));
		free(*root);
		*root = NULL;
	}
}
复制代码
1
2
3
4
5
6
7
8
9
10
void BinaryTreeDestory(BTNode* root)
{
	if (root)
	{
		BinaryTreeDestory(root->_left);
		BinaryTreeDestory(root->_right);
		free(root);
		root = NULL;
	}
}

比较上述二者的区别，

代码1 参数为二级指针，指向存放root地址的地址，调用过程中，指针置空，无野指针，

代码2 参数为一级指针，指向root地址，调用过程中，指针没有置空，置空的为指针的拷贝，存在野指针

  • 二叉树的遍历

前序/中序/后序的递归结构遍历：是根据访问结点操作发生位置命名

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

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

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为 根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

在二叉树遍历过程中都是递归，回溯的过程：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root) 
{
	if (root == NULL)
	{
		return;
	}
	printf("%c ",root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c ", root->_data);
	
}

  • 层序遍历

借助队列或链表，先进先出的原则，通过尾插，头删进行遍历，通过在队列的结构实现层序遍历（按序遍历）

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	//通过队列尾插头删实现层序遍历
	//借助队列保存节点
	Queue q;
	initQueue(&q);
	//根节点存入队列
	if (root)
	{
		queuePush(&q,root);
	}
	//遍历队列中每一个节点
	while (!EmptyQueue(&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);
		}
	}
	printf("n");
}

  • 节点数计算（递归回溯）

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	//空树 为0
	if (root == NULL)
	{
		return 0;
	}
	//叶子节点 为1
	if (root->_left == NULL && root->_right == NULL)
		return 1;
	//非叶子  左子树叶子+右子树叶子
	return BinaryTreeLeafSize(root->_left)+BinaryTreeLeafSize(root->_right);
}
// 二叉树第k层节点个数
//第k层节点个数=左右子树第k-1层节点个数和
//假设根为第一层
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);
}

  • 二叉树高度

复制代码
1
2
3
4
5
6
7
8
9
//二叉树高度，层数
int BinaryTreeHigh(BTNode* root)
{
	if (root == NULL)
		return 0;
	int left = BinaryTreeHigh(root->_left);
	int right = BinaryTreeHigh(root->_right);
	return left > right ? left + 1 : right + 1;
}

  • 二叉树查找指定节点

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root)
	{
		if (root->_data == x)
		{
			return root;
		}
		if (BinaryTreeFind(root->_left, x))
		{
			return BinaryTreeFind(root->_left, x);
		}
		else
			return BinaryTreeFind(root->_right, x);
	}

  • 判断是否为完全二叉树

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	//借助队列保存节点
	Queue q;
	initQueue(&q);
	//根节点存入队列
	if (root)
	{
		queuePush(&q, root);
	}
	//遍历队列中每一个节点
	while (!EmptyQueue(&q))
	{
		//获取队头元素
		BTNode* front = queueFront(&q);
		//出队
		queuePop(&q);
		//此时无需判断左右孩子是否存在，只要当前节点存在，直接入，即使为空节点  作为后续判断依据
		if (front)
		{
			queuePush(&q, front->_left);
			queuePush(&q, front->_right);
		}
		else
			break;
	}
	//剩余元素中，是否存在非空节点
	while (!EmptyQueue(&q))
	{
		BTNode* front = queueFront(&q);
		queuePop(&q);
		if (front)
		{
			//如果剩余节点中存在非空节点  则说明该节点不连续
			return 0;
		}
	}
	return 1;
}

基于层序遍历的思想，当遍历到空节点时停止，遍历剩余元素，如果剩余元素中存在非空节点，说明节点不连续，为非完全二叉树。

  • 测试代码

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<stdio.h>
#include"BinaryTree.h"
#include"queue.h"

void test()
{
	char arr[] = "ABD##E#H##CF##G##";
	int idx = 0;
	//创建二叉树
	BTNode* root = BinaryTreeCreate(arr,&idx);
	//前序遍历
	printf("前序遍历: ");
	BinaryTreePrevOrder(root);
	printf("n");
	//中序遍历
	printf("中序遍历: ");
	BinaryTreeInOrder(root);
	printf("n");
	//后序遍历
	printf("后序遍历: ");
	BinaryTreePostOrder(root);
	printf("n");
	printf("层序遍历：");
	BinaryTreeLevelOrder(root);
	printf("n");
	printf("树高: %dn", BinaryTreeHigh(root));
	printf("树节点数: %dn",BinaryTreeSize(root));
	printf("叶子节点数: %dn", BinaryTreeLeafSize(root));
	printf("第%d层子节点数: %dn",3, BinaryTreeLevelKSize(root,3));
	int k = BinaryTreeComplete(root);
	printf("%d ",k);
	if (k)
		printf("完全二叉树n");
	else
		printf("非完全二叉树n");
}

int main()
{
	test();
	return 0;
}

  • 测试结果

 

 

最后

以上就是乐观手链最近收集整理的关于C语言实现二叉树C语言实现二叉树的全部内容，更多相关C语言实现二叉树C语言实现二叉树内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(97)

相关文章

C语言编写程序（输出最大值+转换变量值+大小写转换+反序数）
C语言编写程序（输出最大值+转换变量值+大小写转换+反序数）
初识c语言
初识c语言
C语言---二叉树(详解)---数据结构
C语言---二叉树(详解)---数据结构
二叉搜索树基本原理与C语言实现
二叉搜索树基本原理与C语言实现
C语言实现二叉树C语言实现二叉树
C语言实现二叉树C语言实现二叉树
C语言数据结构之树超全详解基础知识操作部分树和森林赫夫曼树及其应用
C语言数据结构之树超全详解基础知识操作部分树和森林赫夫曼树及其应用
数据结构--C语言实现链式二叉树--详解二叉树基本知识二叉树基本操作
数据结构--C语言实现链式二叉树--详解二叉树基本知识二叉树基本操作
Kubernetes、C语言小白变怪兽、C++ Primer Plus、TCP/IP网络编程、JavaScript高级程序设计
Kubernetes、C语言小白变怪兽、C++ Primer Plus、TCP/IP网络编程、JavaScript高级程序设计

评论列表共有 0 条评论

立即
投稿
返回
顶部