[数据结构与算法]二叉树

一.什么是二叉树？

二叉树是一颗特殊的树，每个节点最多有两个孩子，以这两个孩子作为根的树也是二叉树。

吐槽一下，因为之前有同学在面试的时候被问到二叉树的标准定义，所以有必要将标准定义列出来。

标准定义（引用自百度百科)：
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点.

二.二叉树的性质

1.若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.

2.若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.

3.对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1
推导过程如下：
二叉树节点的个数 = 二叉树边的个数 + 1
节点个数 = n0 + n1 + n2
n0:度为0的节点个数
n1:度为1的节点个数
n2:度为2的 节点个数
边的个数 = 0 * n0 + 1 * n1 + 2 * n2
n0 + n1 + n2 = n1 + 2n2 + 1，则n0 = n2 + 1

4.若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=Log2(n+1). (ps：Log2(n+1)是log以2为
底，n+1为对数)

5.对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对
于序号为i的结点有：

1)若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点

2)若2i+1<n，左孩子序号：2i+1，2i+1>=n，否则无左孩子

3)若2i+2<n，右孩子序号：2i+2，2i+2>=n，否则无右孩子

三.完全二叉树和满二叉树

1.完全二叉树

一个有k层n个节点的二叉树，如果前k-1层是满的，并且第k层从左往右连续，则这棵树是完全二叉树
完全二叉树示意图：

2.满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。满二叉树是特殊的完全二叉树.
满二叉树示意图：

四.二叉树的实现

1.顺序存储—堆

堆的实现见博客：
https://blog.csdn.net/m0_51765966/article/details/120579694

2.链式存储

链式存储可以采用孩子兄弟表示法，左右孩子表示法，父亲左右孩子表示法等，此处采用左右孩子表示法

1)二叉树数据结构的定义

每个节点不仅要能存储自己的数据，还要有左右孩子的指针

//二叉树的定义
typedef char DataType;		//数据类型
typedef struct TreeNode
{
	DataType data;				//节点存储的数据
	struct TreeNode* left;		//左子树
	struct TreeNode* right;		//右子树
}TreeNode;

2)核心操作的实现思路

根据先序遍历的结果创建二叉树

一颗二叉树，即使是同一个先序遍历的结果，也可能会有多种结构，所以为了让这颗二叉树具有唯一性，用#表示空节点.
当遍历先序结果时，遇见#就返回一个空指针，表示此节点为空,否则就创建一个节点，并递归创建左右孩子

二叉树先序遍历结果及对应的二叉树示例如下图所示：

层序遍历

通过队列来实现层序遍历
a:将根节点存入队列；
b:统计当前队列中的元素个数curSz也就是这一层的节点个数,
让这curSz个元素出队并保存结果，每次出队时将队头元素的左孩子和右孩子按照顺序入队(前提是左孩子和右孩子非空);
c：重复b直到队列为空;

获取第k层的节点个数

这个实现起来难度不大，但对于递归的使用很灵活和巧妙,所以归到核心操作中，概括起来就一句话：第k层的节点个数就是左右孩子的第k-1层的节点个数之和

销毁二叉树

销毁二叉树时，通过递归的方法，先销毁左子树的节点，再销毁右子树的节点，最后销毁根节点。
最重要的是要传一个根节点指针的指针作为参数，不然释放完堆上的节点空间之后，无法将指针置为空。

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

通过层序遍历来判断
在层序遍历的过程中，遇见空节点，查看这一层后面的节点是否全为空节点，如果不全为空节点，则说明这一层节点非连续，不是完全二叉树；其他情况则说明是完全二叉树。

3）二叉树源码

因为要用到队列，所以也包含队列的源码
因为队列的节点中存储的数据为树节点指针,所以树的定义在队列的头文件中

Queue.h:

#pragma once

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


//二叉树的定义
typedef char DataType;		//数据类型
typedef struct TreeNode
{
	DataType data;				//节点存储的数据
	struct TreeNode* left;		//左子树
	struct TreeNode* right;		//右子树
}TreeNode;
///

typedef TreeNode* QDataType;	//队列中存放的是节点指针

//定义队列的成员
typedef struct Qnode
{
	struct Qnode* _next;
	QDataType _data;
}Qnode;

//定义队列：有一个头指针和一个尾指针
typedef struct Queue
{
	Qnode* _front;
	Qnode* _rear;
	int size;
}Queue;
//初始化
void queueInit(Queue* q);
//创建节点
Qnode* createNode(QDataType val);
//入队列
void queuePush(Queue* q, QDataType val);
//出队列
void queuePop(Queue* q);
//获取队列元素的个数
int queueSize(Queue* q);
//判断是否为空
int queueEmpty(Queue* q);
//销毁
void queueDestroy(Queue* q);
//获取队头元素
QDataType queueFront(Queue* q);
//获取队尾元素
QDataType queueBack(Queue* q);

Queue.c：

#include "Queue.h"

//初始化
void queueInit(Queue* q)
{
	q->_front = q->_rear = NULL;
	q->size = 0;
}

//创建节点
Qnode* createNode(QDataType val)
{
	Qnode* node = (Qnode*)malloc(sizeof(Qnode));
	node->_data = val;
	node->_next = NULL;
	return node;
}

//入队列
void queuePush(Queue* q, QDataType val)
{
	Qnode* node = createNode(val);
	if (q->_front == NULL)
		q->_front = q->_rear = node;
	else
	{
		q->_rear->_next = node;
		q->_rear = node;
	}
	q->size++;
}
//出队列
void queuePop(Queue* q)
{
	if (q->_front)
	{
		Qnode* next = q->_front->_next;
		free(q->_front);
		q->_front = next;
		//删除后是否为空表
		if (q->_front == NULL)
			q->_rear = NULL;
		q->size--;
	}

}

//获取队列元素的个数
int queueSize(Queue* q)
{
	/*
	int num = 0;
	Qnode* cur = q->_front;
	while (cur)
	{
	num++;
	cur = cur->_next;
	}
	return num;
	*/
	return q->size;
}
//获取队头元素
QDataType queueFront(Queue* q)
{
	return q->_front->_data;
}
//获取队尾元素
QDataType queueBack(Queue* q)
{
	return q->_rear->_data;
}
//判断是否为空
int queueEmpty(Queue* q)
{
	if (q->_front == NULL)
		return 1;
	return 0;
}
//销毁
void queueDestroy(Queue* q)
{
	Qnode* cur = q->_front;
	while (cur)
	{
		Qnode* next = cur->_next;
		free(cur);
		cur = next;
	}
	q->_front = q->_rear = NULL;
	q->size = 0;
}

BinaryTree.h:

#pragma once

//不知道为啥，有时候VS2013可以识别typedef，有时候却不行
//定义的结构体类型重定义之后还需要加上struct
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include "Queue.h"

/*
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	因为需要用到队列进行层序遍历，所以队列中的元素类型要设置为树的节点类型
	因此将二叉树节点的定义放到了队列的头文件中
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
*/

//根据先序遍历的结果创建一颗二叉树
//先序遍历结果用#表示空节点
//形如右边的格式：ABD##E#H##CF##G##
TreeNode* CreateTree(DataType* PreOrderRes, int* curIdx)
{
	if (PreOrderRes[*curIdx] == '#')
	{
		++(*curIdx);
		return NULL;
	}
	else
	{
		TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
		root->data = PreOrderRes[*curIdx];
		++(*curIdx);

		root->left = CreateTree(PreOrderRes, curIdx);
		root->right = CreateTree(PreOrderRes, curIdx);
		return root;
	}
}

//前序遍历
void PreOrder(TreeNode* root)
{
	if (root)
	{
		printf("%c ", root->data);
		PreOrder(root->left);
		PreOrder(root->right);
	}
}

//中序遍历
void InOrder(TreeNode* root)
{
	if (root)
	{
		InOrder(root->left);
		printf("%c ", root->data);
		InOrder(root->right);
	}
}

//后序遍历
void PostOrder(TreeNode* root)
{
	if (root)
	{
		PostOrder(root->left);
		PostOrder(root->right);
		printf("%c ", root->data);
	}
}

//层序遍历
void LevelOrder(TreeNode* root)
{
	if (root == NULL)
		return;

	struct Queue q;
	queueInit(&q);
	queuePush(&q, root);
	while (!queueEmpty(&q))
	{
		int sz = queueSize(&q);
		while (sz--)
		{
			TreeNode* front = queueFront(&q);
			printf("%c ", front->data);
			queuePop(&q);

			if (front->left)
				queuePush(&q, front->left);
			if (front->right)
				queuePush(&q, front->right);
		}
	}
	printf("\n");
	queueDestroy(&q);
}

//获取二叉树节点个数
int GetTreeNodeSize(TreeNode* root)
{
	if (root == NULL)
		return 0;

	int left = GetTreeNodeSize(root->left);
	int right = GetTreeNodeSize(root->right);
	return left + right + 1;
}

//获取二叉树节点个数-----方法2
//sum是一个输出型参数，通过sum将节点个数传出去
void GetTreeNodeSize2(TreeNode* root, int* sum)
{
	if (root)
	{
		++(*sum);
		GetTreeNodeSize2(root->left, sum);
		GetTreeNodeSize2(root->right, sum);
	}
}

//获取叶子节点个数
int GetLeafSize(TreeNode* root)
{
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
		return 1;

	return GetLeafSize(root->left) + GetLeafSize(root->right);
}

//获取第K层节点的个数
//递归解决问题简直太简洁了
int GetKLevelSize(TreeNode* root, int k)
{
	//递归出口
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;

	//左右子树的第k-1层节点之和
	//一层一层向下递归,直到 k = 1
	return GetKLevelSize(root->left, k - 1) +
		GetKLevelSize(root->right, k - 1);
}

//获取二叉树的层数
int GetHeight(TreeNode* root)
{
	if (root == NULL)
		return 0;

	int lDepth = GetHeight(root->left);
	int rDepth = GetHeight(root->right);
	return lDepth > rDepth ? lDepth + 1 : rDepth + 1;
}

//二叉树中查找值为target的元素对应的节点
TreeNode* FindNode(TreeNode* root, DataType target)
{
	if (root == NULL)
		return NULL;

	if (root->data == target)
		return root;

	struct TreeNode* res = FindNode(root->left, target);
	if (res)
		return res;
	return FindNode(root->right, target);
}

/*
	销毁二叉树的典型错误
	一级指针传进去只能达到释放堆空间的目的，
	而函数传参传进去的因为是实参的拷贝，
	所以实参也就是指针的指向不会发生任何改变
	void DestroyTree(TreeNode* root)
	{
	if (root)
	{
	DestroyTree(root->left);
	DestroyTree(root->right);
	free(root);
	root = NULL;
	}
	}
*/

/*
	销毁二叉树的正确做法，传入指针的指针
	函数传参时传入指向节点指针的指针，通过这个二级指针
	就可以操作节点指针和节点指针指向的堆空间
*/

void DestroyTree2(TreeNode** root)
{
	if (*root)
	{
		DestroyTree2(&((*root)->left));
		DestroyTree2(&((*root)->right));
		free(*root);
		*root = NULL;
	}
}

判断是否为完全二叉树---通过层序遍历来验证
因为对于完全二叉树的结构理解的不到位，虽然功能没问题
但是想出来的判断方法有些复杂
//bool IsCompleteBinaryTree(TreeNode* root)
//{
//	if (root == NULL)
//		return true;
//
//	struct Queue q;
//	queueInit(&q);
//	queuePush(&q, root);
//	while (!queueEmpty(&q))
//	{
//		int curSz = queueSize(&q);
//		while (curSz > 0)
//		{
//			QDataType front = queueFront(&q);
//			queuePop(&q);
//			--curSz;
//
//			if (front->left)
//				queuePush(&q, front->left);
//			if (front->right)
//				queuePush(&q, front->right);
//
//			//左孩子不存在、右孩子存在，说明节点不连续，不满足完全二叉树的定义
//			if (front->left == NULL && front->right != NULL)
//				return false;
//			//如果左孩子存在、右孩子不存在，但是下一层还有其他元素
//			//则说明不连续，不满足完全二叉树的定义
//			else if (front->left != NULL && front->right == NULL)
//			{
//				while (curSz > 0)
//				{
//					//获取到该层的下一个节点,判断下一个节点是否为空
//					front = queueFront(&q);
//					queuePop(&q);
//					--curSz;
//
//					if (front->left)
//						queuePush(&q, front->left);
//					if (front->right)
//						queuePush(&q, front->right);
//					//如果当前层的节点还有左右孩子说明不是完全二叉树
//					if (front->left || front->right)
//						return false;
//				}
//			}
//		}
//	}
//	queueDestroy(&q);
//
//	return true;
//}

//判断二叉树是否为完全二叉树
//通过层序遍历判断，每一层的节点从左到右都是连续且非空的
//除了最后一层可能是不满的，其它层都是满的
bool IsCompleteBinaryTree(TreeNode* root)
{
	if (root == NULL)
		return true;

	struct Queue q;
	queueInit(&q);
	queuePush(&q, root);

	while (!queueEmpty(&q))
	{
		QDataType front = queueFront(&q);
		queuePop(&q);

		if (front)
		{
			//如果一个节点存在，让它的左右孩子入队
			//无论此时左右孩子是否为空
			queuePush(&q, front->left);
			queuePush(&q, front->right);
		}
		else
		{
			//队列中有空节点就退出
			break;
		}
	}

	//上一个循环结束，如果此时队列中有元素，判断此时的元素是不是全为空节点
	//如果全为空节点，说明是完全二叉树
	//如果有一个非空节点，说明不是完全二叉树
	while (!queueEmpty(&q))
	{
		QDataType front = queueFront(&q);
		queuePop(&q);
		if (front)
			return false;
	}

	queueDestroy(&q);

	return true;
}