1. AI技术聚合首页
  2. IT

数据结构：二叉树的链式结构

xiaoxingxing • • IT • 阅读 101

朋友们、伙计们，我们又见面了，本期来给大家解读一下链式二叉树的相关知识点，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

数据结构与算法专栏：数据结构与算法

个  人  主  页 ：stackY、

C 语 言 专 栏：C语言：从入门到精通

目录

前言：

链式存储：

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，难度也是逐次递增，我们会先从最简单的来学习。

前置说明：

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。所以我们先来手动创建一个最简单的二叉树，然后再来进行学习有关二叉树的一些操作，在后面我们也会带大家一起来真正的创建一个二叉树。一颗二叉树都会有一个初始根和两个分别指向左右孩子的节点的指针，因此需要定义一个结构，快速方便的来上手二叉树：我们依旧是来分模块来写二叉树，创建一个头文件Tree.h，两个源文件Tree.c、Test.c头文件：Tree.h
typedef int TreeDataType;

typedef struct BinaryTreeNode
{
	TreeDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

//快速创建一个二叉树
BTNode* CreatBinaryTree();

源文件：Tree.c

//快速创建一个二叉树
BTNode* BuyBTNode(TreeDataType 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 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);
	BTNode* node7 = BuyBTNode(7);

	//链接成树
	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	node3->left = node6;
	node3->right = node7;

	return node1;
}

注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式在后面会详解重点讲解。 再看二叉树基本操作前，再回顾下二叉树的概念，二叉树是： 1. 空树 2. 非空：根节点，根节点的左子树、根节点的右子树组成的。 从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

1.二叉树的遍历

二叉树的遍历有这几种方法：

1. 前序：先访问根节点，再访问左子树，最后访问右子树。

2. 中序：先访问左子树，在访问根节点，最后访问右子树。

3. 后序：先访问左子树，在访问右子树，最后访问根节点。

4. 层序：一层一层访问。（后面再讲）

那么用我们创建的这个二叉树使用前、中、后序遍历访问得到的会是什么呢？我们一起来画图看一看：

1.前序：

先访问1的根，再访问1的左子树的根2，然后再访问2的左子树的根然后再访问4的左子树的根为空，因此就要访问4的右子树的根还为4空，所以就要再走上一层2的右子树的根为5，然后再访问5的左子树为空，再访问5的右子树还为空，这时再走上一层，这时1的左支已经全部访问完毕，所以就要访问右子树3，依次类推…….直到全部访问结束

所以最后的遍历结果是：1 2 4 N N 5 N N 3 6 N N 7 N N

2.中序：

中序遍历是先访问左子树的，因此得一直往下面走先访问1的左子树，然后再在1的左子树中再找它的左子树，这样子依次类推，直到找到空，这时找到的就是4的左子树为空，这时就要先访问4，然后再访问4的右子树也为空，这时就走上一层，访问2，然后再访问2的右子树，再在2的右子树中再访问它的左子树，这时访问的5的左子树为空，这时就要访问5了，然后再访问5的右子树也为空，这时就要再走上一层了，这时就要访问1，然后再在1的右子树中继续重复之前的动作…….

所以最后的遍历结果是：N 4 N 2 N 5 N 1 N 6 N 3 N 7 N

3.后序：

后序遍历是先访问左子树，再访问右子树，最后才访问根先访问1的左子树，然后再访问1的左子树的左子树，依次类推，直到访问到空，这时就会返回上一层，再访问右子树，再访问根，依次类推，所以在访问到4的左子树时为空，然后再访问4的右子树也为空这时就会访问4，每个节点都是一样的……

所以最后的遍历结果是: N N 4 N N 5 2 N N 6 N N 7 3 1 

代码实现：

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历： 1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。 2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。 3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

头文件：Tree.h

//前序遍历
void PrevOrder(BTNode* root);

//中序遍历
void InOrder(BTNode* root);

//后序遍历
void PostOrder(BTNode* root);

源文件：Tree.c

//前序遍历
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	//先访问根节点
	printf("%d ", root->data);
	//再访问左子树
	PrevOrder(root->left);
	//最后访问右子树
	PrevOrder(root->right);
}

//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	//先访问左子树
	InOrder(root->left);
	//再访问根
	printf("%d ", root->data);
	//在访问右子树
	InOrder(root->right);
}

//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	//先访问左子树
	PostOrder(root->left);
	//再访问右子树
	PostOrder(root->right); 
	//最后访问根
	printf("%d ", root->data);
}

源文件：Test.c

#include "Tree.h"

int main()
{
	BTNode* root = CreatBinaryTree();
	//前序遍历
	PrevOrder(root);
	printf("\n");

	//中序遍历
	InOrder(root);
	printf("\n");

	//后序遍历
	PostOrder(root);
	printf("\n");

	return 0;
}

递归展开图： 

前序：

中序：

后序：

后序的递归展开图小编在这里就不画了，方法逻辑和前序、中序都是一模一样，只是访问时的顺序不一样，大家可以自己练习的画一下。

1.2二叉树的节点个数

求二叉树的节点的个数有两种方法：

1.遍历使用计数器统计。（不推荐）

2.使用递归来直接计算。

为什么不推荐使用第一种方法呢？

因为使用计数器的话需要把计数器定义为全局变量，并且，在使用完一次之后需要手动将其重置，比较麻烦。

在这里我们来使用第二种方法，使用递归来直接进行统计：

用递归来直接统计时需要注意的一点如果一个根节点的左子树和右子树都为空，返回的不是0，而是1，因为左、右子树都为空，但是根节点不为空，所以需要返回根节点本身和它的左右子树节点的和。

代码实现：

头文件：Tree.h

//二叉树的节点个数
int BTreeSize(BTNode* root);

源文件：Tree.c

//二叉树的节点个数
int BTreeSize(BTNode* root)
{
	//为空就返回0
	if (root == NULL)
	{
		return 0;
	}

	//不为空就返回根节点和它的左右子树节点的和
	return BTreeSize(root->left)
		+ BTreeSize(root->right)
		+ 1;
}

递归展开图：

1.3二叉树的叶子节点个数

二叉树的叶子节点就是它的左右子树都为空被叫做叶子节点，因此我们可以根据一个根节点的左右子树都为空来判断是否是叶子节点，依旧是采用递归的方法，但是如果它的根节点只有左右子树中的一个，那么它也不是叶子节点。

代码演示：

头文件：Tree.h

//求叶子节点的个数
int BTreeLeafSize(BTNode* root);

源文件：Tree.c

//求叶子节点的个数
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.4二叉树的高度 （深度）

要求二叉树的高度，我们同样的也是采用递归遍历的方法：求出左右子树的高度，然后比较哪个树的高度更大就返回哪个树。

要求1的高度，那么就得求它的左右子树2、3的高度，要求2和3的高度就得分别求它们左右子树的高度…依次类推，4的左右子树高度为0，这时4返回给2时返回的高度为0+1（0表示它的左右子树的高度为0，1表示它自己的高度为1），也就是说再返回时要加上自己本身的高度，所以2的左子树的高度为1，再来计算2的右子树5的高度，计算5的高度又得计算5的左右子树的高度，5的左子树高度为1，右子树高度为0，取较大的为1，5返回2时再加上自己本身的高度为2，所以取2的左右子树较高的高度为2，所以2返回1时再加上自己本身的高度为3…..依次类推，直到遍历完整个二叉树。所以最后整颗树的高度为4。


代码演示：

头文件：Tree.h

//二叉树的高度
int BTreeHight(BTNode* root);

源文件：Tree.c

//二叉树的高度
int BTreeHight(BTNode* root)
{
	//是否为空树
	if (root == NULL)
	{
		return 0;
	}
	//保存左右子树的高度
	BTNode* LeftTreeHight = BTreeHight(root->left);
	BTNode* RightTreeHight = BTreeHight(root->right);

	return LeftTreeHight > RightTreeHight ? LeftTreeHight + 1 : RightTreeHight + 1; //加上自己本身的高度1
}

注意：这里还有一种写法：不保存左右子树的高度，直接进行三目操作然后递归，这样也是可以的，但是当树的结点较多的时候，会造成大量的递归，会导致效率大大降低。

代码演示：

//不推荐的写法
//二叉树的高度
int BTreeHight(BTNode* root)
{
	//是否为空树
	if (root == NULL)
	{
		return 0;
	}

	//直接递归
	return BTreeHight(root->left) > BTreeHight(root->right) ? 
		BTreeHight(root->left) + 1 : BTreeHight(root->right) + 1; //加上自己本身的高度1
}

1.5第k层结点的个数

要求第k层结点的个数，在这里要找到第k层是个关键问题，所以我们要将它转化为多个子问题：要求第k层，那我们不妨求它的左、右子树的k-1层结点的个数，那么它的结束标志为：k==1时且结点不为空才算一个结点，还有一种特殊的情况，为空树表示一个结点都没有，另外还需要对k进行检测，k是大于0的。

我们可以将这个树倒过来，将原本的第一层看作第3层，那么就需要求它的左右子树的第2层的结点个数，然后又可以转化为求它的左右子树的第1层，这时求出的结点个数就是第3层的结点个数为3。

代码演示：

 头文件：Tree.h

//第k层节点的个数
int  BTreeLeafKSize(BTNode* root, int k);

源文件：Tree.c

//第k层节点的个数
int  BTreeLeafKSize(BTNode* root, int k)
{
	//判断k的合理性
	assert(k > 0);
	//树为空
	if (root == NULL)
	{
		return 0;
	}
	//树不为空，且k==1
	if (k == 1 )
	{
		//算一个有效结点
		return 1;
	}
	//树既不为空，k也不为1，继续向下走
	return BTreeLeafKSize(root->left, k - 1) + 
		BTreeLeafKSize(root->right, k - 1);
}

 递归展开图：

  

1.6查找二叉树中值为x的结点

查找结点的位置我们也可以转化为子问题，去它的左右子树中查找值为x的结点，也就是一个前序遍历的过程，先找根，再找左右子树，如果这个结点中的data为x，就返回这个结点的地址，找不到就返回NULL。

前序遍历:
先找根，再找左右子树。
1不为6，再去1的左右子树找，左子树2也不为6，再去2的左子树找，4也不为6，再去4的左右子树找，发现没有左右子树，就返回上一层，再去2的右了树找，5也不为6，再去5的左右子树找，也没有左右子树，再返回上一层，去1的右子树找，3不为6，再去3的左子树找，发现6刚好等于6，那么就要返回6的结点的地址。

代码演示：

头文件：Tree.h

//查找值为x的结点
BTNode* BTreeFind(BTNode* root, TreeDataType x);

源文件：Tree.c

//查找值为x的结点
BTNode* BTreeFind(BTNode* root, TreeDataType x)
{
	//判断是否为空树
	if (root == NULL)
	{
		return NULL;
	}
	//找到了就返回地址
	if (root->data == x)
	{
		return root;
	}
	//先去左树找，找到了就返回
	BTNode* left = BTreeFind(root->left, x);
	if (left)
	{
		return left;
	}
	//再去右树找，找到了就返回
	BTNode* right = BTreeFind(root->right, x);
	if (right)
	{
		return right;
	}
	//如果左右树都没有找到就返回NULL
	return NULL;
}

递归展开图：

2.二叉树的层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层 上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。层序遍历需要用到的工具就是我们之前写的队列，因此队列具有先进先出的特点，因此我们可以将二叉树的第一层先查入队列，然后将1层出列，同时再将第一层的左右子树再插入队列，简单的理解就是在这个队列中，出去一个根节点就会带进来它的两个左右子树，这样子就是实现了层序遍历。

代码演示：

头文件：Queue.h

#pragma once

//       队列

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.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);

//检测队列是否为空
bool QueueEmpty(Queue* pq);

//对头出队列
void QueuePop(Queue* pq);

//获取队头的元素
QDataType QueueFront(Queue* pq);

//获取队尾的元素
QDataType QueueBack(Queue* pq);

//获取队列有效元素的个数
int QueueSize(Queue* pq);

源文件：Queue.c

#define _CRT_SECURE_NO_WARNINGS 1

#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");
		return;
	}
	newnode->next = NULL;
	newnode->data = x;

	//第一次尾插
	if (pq->ptail == NULL)
	{
		assert(pq->phead == NULL);

		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	//有效元素++
	pq->size++;
}

//检测队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	//1.判断头、尾指针
	/*
	return pq->phead == NULL
		&& pq->ptail == NULL;
	*/

	//2.判断有效元素个数
	return pq->size == 0;
}

//队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	//判空
	assert(!QueueEmpty(pq));

	//一个结点
	if (pq->phead->next == NULL)
	{
		//直接释放
		free(pq->phead);
		pq->phead = 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;
}

头文件：Tree.h

//层序遍历
void LevelOrder(BTNode* root);

源文件：Tree.c

#include "Queue.h"
#include "Tree.h"

//层序遍历
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);
}

3.二叉树的创建与销毁

之前我们用到的二叉树都是快速创建出来的，这并不是二叉树的真正创建方法，那么接下来我们就来学习一下二叉树的真正创建方式。

3.1二叉树的创建

关于二叉树的创建我们先来看一道OJ题：

二叉树的创建：https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking

这道题描述的意思就是通过前序遍历数组创建二叉树，然后再使用二叉树的中序遍历打印，我们可以来分析一下通过前序遍历数组来创建一个二叉树是怎样的效果，在这里我们就用测试用例来演示：ABC##DE#G##F### 

二叉树的前序遍历是先访问根，在访问左子树，再访问右子树，那么只要一棵树的左右子树都不为空，那么就可以继续向下分解为左子树和右子树，那么ABC##DE#G##F### 通过前序遍历就是这样子：

 

解题思路：

遍历数组，如果是’#’，那么就不需要创建节点，只需要继续访问数组的下一个元素即可，如果不是’#’，就可以创建节点，创建完成之后继续访问下一个数组的元素即可，创建一个节点之后需要继续创建它的左子树，左子树创建完之后再创建它的右子树，这时就需要递归完成一个节点的左右子树节点的创建，然后再使用中序遍历（左子树、根、右子树）即可完成。

代码演示：

#include <stdio.h>
#include <stdlib.h>

typedef int TreeDataType;

typedef struct BinaryTreeNode
{
	TreeDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

//节点的创建
BTNode* BuyBTNode(TreeDataType 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(char* a, int* pi)
{
    //判断是否为'#'
    if(a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    //不为'#'就创建
    BTNode* root = BuyBTNode(a[*pi]);
    //继续访问下一个元素
    (*pi)++;

    //递归创建它的左子树
    root->left = CreatBinaryTree(a,pi);
    //递归创建它的右子树
    root->right = CreatBinaryTree(a,pi);
    return root;
}

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

int main() {
    char a[100];
    scanf("%s",a);
    int i = 0;
    //传递下标
    BTNode* root = CreatBinaryTree(a, &i);
    InOrder(root);
    return 0;
}

那么正常的二叉树的创建过程就是类似于这个OJ题一样，使用前序遍历来创建二叉树，那么在这里好多人都会有一个疑问：为什么要传下标？

如果不传下标，直接在函数中设置下标，那么每一次函数调用下标都会是一个初始值，因为函数递归在创建函数栈帧时每一个栈帧都是独立的，因此每一个栈帧中都有一个下标，那么我们在一个栈帧中操作这个下标，其他的栈帧中的下标并不会受影响，那么我们在函数外面设置一个下标，将这个下标的地址传递给函数，那么每一次的函数调用都会去这块地址找这个下标，我们通过解引用可以改变下这个下标，这样就做到了多个栈帧可以使用一个下标。

创建二叉树：

头文件：Tree.h

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* CreatBinaryTree(char* a, int* pi);

源文件：Tree.c

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
//#代表空树
//创建二叉树
BTNode* CreatBinaryTree(char* a, int* pi)
{
	//判断是否为'#'
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	//不为'#'就创建
	BTNode* root = BuyBTNode(a[*pi]);
	//继续访问下一个元素
	(*pi)++;

	//递归创建它的左子树
	root->left = CreatBinaryTree(a, pi);
	//递归创建它的右子树
	root->right = CreatBinaryTree(a, pi);
	return root;
}

3.2二叉树的销毁 

销毁二叉树最适合的方法就是后序遍历销毁二叉树，后序遍历是：先访问左子树，再访问右子树，最后访问根，这样就可以很好的将整个二叉树销毁掉。

代码演示：

头文件：Tree.h

//销毁二叉树
void BTDestroy(BTNode* root);

源文件：Tree.c

//销毁二叉树
void BTDestroy(BTNode* root)
{
	//后序遍历销毁
	//为空就返回
	if (root == NULL)
		return;

	//先走左树再走右树
	BTDestroy(root->left);
	BTDestroy(root->right);

	//释放
	free(root);
}

4.判断二叉树是否为完全二叉树

完全二叉树的特点：假设树的高度为h，那么前h-1层必须全满，最后一层可以不满，但是必须连续。那么想到这里有许多老铁想到用二叉树的的节点的个数来判断，这种思路是可以的，但是呢？如果最后一层如果不连续，那这就比较坑了，因此我们需要通过它的连续性入手，完全二叉树是一种连续的结构，那么完全二叉树使用层序遍历就是一种连续的结构，因此判断完全二叉树需要用到层序遍历：

使用层序遍历这个二叉树，如果发现队头的数据是空，那么就要进行判断，如果后面的数据都是空，那么就证明这棵二叉树是完全二叉树，如果不为空，那么就不是完全二叉树，我们可以通过画图来验证一下：

 那么我们就可以来入手，先进行层序遍历，出列时遇到空就先跳出，然后对队列中剩下的值进行判断，如果遍历完整个队列还存在非空的值，那么就表示为非完全二叉树，如果遍历完整个队列都是空，那么证明就是完全二叉树。

代码演示：

头文件：Tree.h

//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

源文件：Tree.c

//判断二叉树是否为完全二叉树
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)
			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;
}

5.链式二叉树全部测试代码  

在这里就不展示队列的代码，需要的小伙伴可以去篇文章自取 数据结构：栈和队列

头文件：Tree.h

#pragma once


//        二叉树 

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


typedef int TreeDataType;

typedef struct BinaryTreeNode
{
	TreeDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

//快速创建一个二叉树
BTNode* BinaryTreeCreat();

//前序遍历
void PrevOrder(BTNode* root);

//中序遍历
void InOrder(BTNode* root);

//后序遍历
void PostOrder(BTNode* root);

//二叉树的节点个数
int BTreeSize(BTNode* root);

//求叶子节点的个数
int BTreeLeafSize(BTNode* root);

//二叉树的高度
int BTreeHight(BTNode* root);

//第k层节点的个数
int  BTreeLeafKSize(BTNode* root, int k);

//查找值为x的结点
BTNode* BTreeFind(BTNode* root, TreeDataType x);

//层序遍历
void LevelOrder(BTNode* root);

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* CreatBinaryTree(char* a, int* pi);

//销毁二叉树
void BTDestroy(BTNode* root);

//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

源文件：Tree.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Tree.h"
#include "Queue.h"

//快速创建一个二叉树

BTNode* BuyBTNode(TreeDataType 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* BinaryTreeCreat()
{
	//创建节点
	BTNode* node1 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);
	BTNode* node7 = BuyBTNode(7);

	//链接成树
	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	node3->left = node6;
	node3->right = node7;

	return node1;
}


//前序遍历
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	//先访问根节点
	printf("%d ", root->data);
	//再访问左子树
	PrevOrder(root->left);
	//最后访问右子树
	PrevOrder(root->right);
}

//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	//先访问左子树
	InOrder(root->left);
	//再访问根
	printf("%d ", root->data);
	//在访问右子树
	InOrder(root->right);
}

//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	//先访问左子树
	PostOrder(root->left);
	//再访问右子树
	PostOrder(root->right); 
	//最后访问根
	printf("%d ", root->data);
}

//二叉树的节点个数
int BTreeSize(BTNode* root)
{
	//为空就返回0
	if (root == NULL)
	{
		return 0;
	}

	//不为空就返回根节点和它的左右子树节点的和
	return BTreeSize(root->left)
		+ BTreeSize(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 BTreeHight(BTNode* root)
{
	//是否为空树
	if (root == NULL)
	{
		return 0;
	}
	//保存左右子树的高度
	int LeftTreeHight = BTreeHight(root->left);
	int RightTreeHight = BTreeHight(root->right);

	return LeftTreeHight > RightTreeHight ? LeftTreeHight + 1 : RightTreeHight + 1; //加上自己本身的高度1
}

//不推荐的写法
//二叉树的高度
//int BTreeHight(BTNode* root)
//{
//	//是否为空树
//	if (root == NULL)
//	{
//		return 0;
//	}
//
//	//直接递归
//	return BTreeHight(root->left) > BTreeHight(root->right) ? 
//		BTreeHight(root->left) + 1 : BTreeHight(root->right) + 1; //加上自己本身的高度1
//}


//第k层节点的个数
int  BTreeLeafKSize(BTNode* root, int k)
{
	//判断k的合理性
	assert(k > 0);
	//树为空
	if (root == NULL)
	{
		return 0;
	}
	//树不为空，且k==1
	if (k == 1 )
	{
		//算一个有效结点
		return 1;
	}
	//树既不为空，k也不为1，继续向下走
	return BTreeLeafKSize(root->left, k - 1) + 
		BTreeLeafKSize(root->right, k - 1);
}

//查找值为x的结点
BTNode* BTreeFind(BTNode* root, TreeDataType x)
{
	//判断是否为空树
	if (root == NULL)
	{
		return NULL;
	}
	//找到了就返回地址
	if (root->data == x)
	{
		return root;
	}
	//先去左树找，找到了就返回
	BTNode* left = BTreeFind(root->left, x);
	if (left)
	{
		return left;
	}
	//再去右树找，找到了就返回
	BTNode* right = BTreeFind(root->right, x);
	if (right)
	{
		return right;
	}
	//如果左右树都没有找到就返回NULL
	return NULL;
}

//层序遍历
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);
}

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
//#代表空树
//创建二叉树
BTNode* CreatBinaryTree(char* a, int* pi)
{
	//判断是否为'#'
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	//不为'#'就创建
	BTNode* root = BuyBTNode(a[*pi]);
	//继续访问下一个元素
	(*pi)++;

	//递归创建它的左子树
	root->left = CreatBinaryTree(a, pi);
	//递归创建它的右子树
	root->right = CreatBinaryTree(a, pi);
	return root;
}

//销毁二叉树
void BTDestroy(BTNode* root)
{
	//后序遍历销毁
	//为空就返回
	if (root == NULL)
		return;

	//先走左树再走右树
	BTDestroy(root->left);
	BTDestroy(root->right);

	//释放
	free(root);
}

//判断二叉树是否为完全二叉树
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)
			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

#define _CRT_SECURE_NO_WARNINGS 1

#include "Tree.h"
#include "Queue.h"

void TestTree1()
{
	BTNode* root = BinaryTreeCreat();
	//前序遍历
	PrevOrder(root);
	printf("\n");

	//中序遍历
	InOrder(root);
	printf("\n");

	//后序遍历
	PostOrder(root);
	printf("\n");

	//
	printf("BTreeSize:%d\n", BTreeSize(root));

	printf("BTreeLeafSize:%d\n", BTreeLeafSize(root));

	printf("BTreeHight:%d\n", BTreeHight(root));

	LevelOrder(root);

	printf("BinaryTreeComplete:%d\n", BinaryTreeComplete(root));

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

void TestTree2()
{
	char a[] = { "abc##de#g##f###" };
	int i = 0;
	BTNode* root = CreatBinaryTree(a, &i);

	//中序遍历
	InOrder1(root);
	printf("\n");
	printf("BinaryTreeComplete:%d\n", BinaryTreeComplete(root));

	BTDestroy(root);
	root = NULL;
}

int main()
{
	TestTree1();
	//
	//TestTree2();
	return 0;
}

今天的博客就分享到这里，喜欢的老铁留下你的三连，感谢感谢！我们下期再见！！ 

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
xiaoxingxing的头像xiaoxingxing管理团队
0
上一篇 2023年12月12日
下一篇 2023年12月12日

相关推荐

此站出售，如需请站内私信或者邮箱！