投稿
  1. 首页
  2. C

【二叉树】单值、最大深度、构建、节点（叶子）个数、前、中、后序遍历、层序遍历、判断是否完全（纯C）

code • 2022-4-14 • C • 阅读 30

【二叉树】单值、最大深度、构建、节点（叶子）个数、前、中、后序遍历、层序遍历、判断是否完全（纯C）,第1张

做的时候总感觉自己掌握的不够深，所以在这里写一篇博客来加深理解。


---------

单值二叉树

965. 单值二叉树 - 力扣（LeetCode） (leetcode-cn.com)

 二叉树肯定是递归的，但原函数给我们的却是：

这个函数的参数却只有一个root，我们判断是否为单值还需要其中一个节点的值，如果这个值跟其他值不一样，那我们就返回false，如果节点为空、或者是值一样，我们返回真

那我们就自己建一个函数，然后递归这个创建的函数即可


//递归判断
bool fun(struct TreeNode* root,size_t val)
{
    if(root == NULL)
    {
        return true;
    }
    if(root->val != val)
    {
        return false;
    }
    return fun(root->left,val)&&fun(root->right,val);
}


bool isUnivalTree(struct TreeNode* root){
    if(root == NULL)
    {
        return true;
    }
    size_t val = root->val;

    return fun(root,val);
}

二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode） (leetcode-cn.com)

我们先看题目给我们的条件： 

已知根节点，求最大深度

我们拿两个值，一个记录左节点深度，一个记录右节点深度，然后我们比较返回大的那个

int maxDepth(struct TreeNode* root){
    if(root == NULL)
    {
        return 0;
    }

    /如果不为空，这里就要返回1
    size_t left = maxDepth(root->left)+1;
    size_t right = maxDepth(root->right)+1;

    return left>right?left:right;
}

 --------

二叉树的前序构造：

我们先来创建一个二叉树的结构体，再定义里面的数据类型：

typedef char BTDataType;
 
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

前序，我们知道是：根 左节点、右节点，我们拿到一串数据，就可以按照这样的顺序递归下去

   //一个参数是我们要放进去的数据，另一个指针记录放了几个，每放一个就++
BTNode* BinaryTreeCreate(BTDataType* a, int* n)
{
    //如果这个地方是'#'，就说明这里是空指针，我们让指针++，返回空
	if (a[*n] == '#')
	{
		++(*n);
		return NULL;
	}
	else
	{
        //先开辟节点，这个就是根
		BTNode* root = (BTNode*)malloc(sizeof(BTNode));
        //放数据
		root->data = a[*n];
        让指针++
		++(*n);
        先左节点
		root->left = BinaryTreeCreate(a, n);
        //右节点
		root->right = BinaryTreeCreate(a, n);
        
        //返回这个的地址
		return root;
	}
}

--------------- 

 销毁二叉树

如果理解了如何构造，那这个应该不难

我们拿到一个节点，开始判断这个节点是不是空，如果是空，那我们就直接返回，如果不是空，那我们就继续找这个节点的子节点，直到我们找到叶子，然后free

// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
    //判断节点
	if (root == NULL)
	{
		return;
	}
	else
	{
        //往下找
		BinaryTreeDestory(root->left);
		BinaryTreeDestory(root->right);
        //释放
		free(root);
	}
	return;
}

---------

二叉树的节点（叶子）个数

思路跟销毁二叉树差不多，我们拿到根节点，然后判断它是否为空，为空就返回0，不为空就继续往下找，找到根节点后开始返回1

如果是判断叶子节点，那我们就把判断条件改一下，如果这个节点的左右节点指针都为空，返回1，然后我们返回值调用这个函数，把根的左指针和右指针给它即可

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

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

我们找K层，实际是找K-1层，因为只有它可以拿到K层的地址，如果我们找第3层，那实际上我们找的是第2层，我们拿到第二层根的节点，，然后把它的左右指针传进去，如果 k == 1（我们每次传进去k都-1），如果传进去的节点为空，就返回0，如K==1，那就说明是这一层，我们返回1，把两个值加起来

// 二叉树第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的节点

结束两件有两个：

1、找到了，返回这个节点

2、没找到，返回空

其他情况下继续递归即可

 //二叉树查找值为x的节点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return ;
	}
	if (root->data == x)
	{
		return root;
	}
    //创建临时指针开始找左边
	BTNode* tmp = BinaryTreeFind(root->left, x);
    //为空就是没找到，找右边
	if (tmp == NULL)
	{
		tmp = BinaryTreeFind(root->right, x);
	}
    //不为空就是找到了，返回
	if (tmp != NULL)
	{
		return tmp;
	}
    //右边找完也为空那就返回空
	return NULL;
}

--------- 

二叉树的前、中、后序遍历

如果这个节点是空，我们可以打印出来，或者是直接返回

一开始传进来的是根节点，然后我们打印根节点，再打印左节点，同时左节点又作为子树的根，所以用递归，左边递归完再递归右边：

改变顺序即可改变遍历方式

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

// 二叉树中序遍历
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;
	}
	BinaryTreeInOrder(root->left);
	BinaryTreeInOrder(root->right);
	printf("%c ", root->data);
	return;
}

--------

层序遍历

这可能是最难的一部分，我们需要用到之前的队列

具体 *** 作如下：

 假设我们现在的队列是这样的，那我们层序打印的时候就应该是：

A B C D E F G

如何用队列实现？

我们创建一个队列并初始化：

这里有两种实现队列的方式

第一种用数组，这种方式简单、好理解，但缺点是不能合适的开辟空间

先定义结构体并将其初始化：

typedef struct Queue
{
	struct BinaryTreeNode* arr[MaxSize];
	int head;
	int end;
}Queue;


void QueueInit(Queue* q)
{
	q->end = q->head = 0;
	return;
}

然后我们就要考虑插入数据了：

我们先将A插进去并打印出来，之后判断：如果队列不为空（此时队列应该有A），我们就继续插入数据，插入的是A的子节点（B、C）

我们再删除A的数据，因为删除了A的数据，而如果刚刚插入成功的话，那下一个到的就是B，再将B的子节点放进去，打印B的节点，再删除，循环

这是我们会用到的四个关于队列的函数（如果看不懂的话可以点开专栏看看我以前写的顺序表和队列）：

//初始化
void QueueInit(Queue* q)
{
	assert(q);
	q->end = q->head = 0;
	return;
}


//插入元素
void QueuePush(Queue* q, struct BinaryTreeNode* x)
{
	assert(q);
	q->arr[q->end++] = x;
}


//删除元素并返回元素
struct BinaryTreeNode* QueuePop(Queue* q)
{
	assert(q);
	struct BinaryTreeNode* tmp = q->arr[q->head];
	q->head++;
	return tmp;
}

//判断队列是否为空
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->end == q->head;
}

写完了队列的 *** 作，那我们就可以正式开始写层序了：

void BinaryTreeLevelOrder(BTNode* root)
{
    //创建并初始化
	Queue q;
	QueueInit(&q);
    //插入
	QueuePush(&q, root);
    //开始走
	while (!QueueEmpty(&q))
	{
        //当前节点数据方便我们使用
		BTNode* node = QueueFront(&q);
        //打印
		printf("%c ", node->data);
        //如果它有子节点就插入
		if (node->left)
		{
			QueuePush(&q, node->left);
		}
		if (node->right)
		{
			QueuePush(&q, node->right);
		}
        //记得删除
		QueuePop(&q);
	}
}

-------

如果能明白层序遍历，那判断是不是就很简单了，把打印条件改一下，改成：

判断完全二叉树

如果这个节点只有一边节点，那它就不是完全二叉树

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* node = QueueFront(&q);
		if (node->left != NULL && node->right == NULL || root->left == NULL&&root->right != NULL)
		{
			return false;
		}
		if (node->left)
		{
			QueuePush(&q, node->left);
		}
		if (node->right)
		{
			QueuePush(&q, node->right);
		}
		QueuePop(&q);
	}
	return true;
}

--------

附上全部代码，有需要可直接复制使用：

#include
#include
#include
#include

#define MaxSize 100
typedef char BTDataType;

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

typedef struct Queue
{
	struct BinaryTreeNode* arr[MaxSize];
	int head;
	int end;
}Queue;


void QueueInit(Queue* q)
{
	assert(q);
	q->end = q->head = 0;
	return;
}

void QueuePush(Queue* q, struct BinaryTreeNode* x)
{
	assert(q);
	q->arr[q->end++] = x;
}


BTNode* QueueFront(Queue* q)
{
	assert(q);
	return q->arr[q->head];
}
void  QueuePop(Queue* q)
{
	assert(q);
	q->head++;
}



bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->end == q->head;
}

BTNode* BinaryTreeCreate(BTDataType* a, int* n)
{
	if (a[*n] == '#')
	{
		++(*n);
		return NULL;
	}
	else
	{
		BTNode* root = (BTNode*)malloc(sizeof(BTNode));
		root->data = a[*n];
		++(*n);
		root->left = BinaryTreeCreate(a, n);
		root->right = BinaryTreeCreate(a, n);
		return root;
	}
}


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

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

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	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 ;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* tmp = BinaryTreeFind(root->left, x);
	if (tmp == NULL)
	{
		tmp = BinaryTreeFind(root->right, x);
	}
	if (tmp != NULL)
	{
		return tmp;
	}
	return NULL;
}

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

// 二叉树中序遍历
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;
	}
	BinaryTreeInOrder(root->left);
	BinaryTreeInOrder(root->right);
	printf("%c ", root->data);
	return;
}

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

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* node = QueueFront(&q);
		if (node->left != NULL && node->right == NULL || root->left == NULL&&root->right != NULL)
		{
			return false;
		}
		if (node->left)
		{
			QueuePush(&q, node->left);
		}
		if (node->right)
		{
			QueuePush(&q, node->right);
		}
		QueuePop(&q);
	}
	return true;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/607168.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-14
下一篇 2022-04-14

发表评论

登录后才能评论

评论列表（0条）

保存