欢迎各位大佬光临本文章！！！

还请各位大佬提出宝贵的意见，如发现文章错误请联系冰冰，冰冰一定会虚心接受，及时改正。

本系列文章为冰冰学习编程的学习笔记，如果对您也有帮助，还请各位大佬、帅哥、美女点点支持，您的每一分关心都是我坚持的动力。

我的博客地址：bingbing~bang的博客_CSDN博客https://blog.csdn.net/bingbing_bang?type=bloghttps://blog.csdn.net/bingbing_bang?type=blog

我的gitee：冰冰棒 (bingbingsupercool) - Gitee.https://gitee.com/bingbingsurercool

---

系列文章推荐

冰冰学习笔记：这些链表练习题，你会吗？（中）

冰冰学习笔记：这些链表练习题，你会吗？（下）

冰冰学习笔记：这些栈与队列练习题你会吗？

---

目录

系列文章推荐

前言

一、二叉树的结构与功能函数

1.1二叉树的遍历

1.2二叉树的结点个数

1.3二叉树的叶子个数

1.4二叉树第K层的结点个数

1.5二叉树的查找

1.6二叉树的深度

1.7判断是否为完全二叉树

1.8二叉树销毁

二、二叉树的OJ初阶练习题

2.1二叉树的构建与中序遍历

2.2单值二叉树

2.3相同的树

2.4对称二叉树

2.5另一棵树的子树

---

前言

        二叉树的搭建与前面线性表，栈，队列等都不相同，二叉树的增删查改没有意义，二叉树实现的更多是二叉树中的一些功能函数，例如求结点个数，叶子个数等。本文章将讲解二叉树的部分初阶OJ题与二叉树常用的一些功能函数。

一、二叉树的结构与功能函数

        二叉树的结构在前面的章节中提到过，二叉树使用链表结构搭建一般有两种搭建方式：二叉链和三叉链。二叉链结构中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。三叉链结构中比二叉链多了一个指向父亲结点的前趋指针。三叉链一般使用在高级的数据结构中，二叉链则是通常使用和学习的结构。

二叉链结构：

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;//指向左孩子结点
	struct BinaryTreeNode* right;//指向右孩子结点
}BTNode;

三叉链结构：

typedef struct BinaryTreeNode_Three
{
	BTDataType data;
	struct BinaryTreeNode_Three* parent;//指向父亲结点
	struct BinaryTreeNode_Three* left;//指向左孩子结点
	struct BinaryTreeNode_Three* right;//指向右孩子结点
}BTTNode;

1.1二叉树的遍历

        二叉树的功能函数中，遍历是不可缺少的。二叉树的遍历有多种方式，前序遍历，后序遍历，中序遍历以及层次遍历。由于二叉树是一种天然递归的结构，因此二叉树的功能函数中最常用的书写方式就是递归形式。前序遍历，中序遍历以及后序遍历方式的区分是通过遍历根结点顺序的前后来区分的。

（1）前序遍历

        前序遍历就是先访问二叉树的根节点，在访问二叉树的左子树，在访问右子树。具体访问递归图如下所示：

        因此构建成代码就是先判断当前节点是否为空，为空则打印＃号并返回，不为空则打印当前结点数值；然后递归去调用当前结点的左子树，等左子树返回后，再去调用当前结点的右子树。

函数代码：

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

（2）中序遍历

        中序遍历就是先访问左子树，在访问当前结点，最后访问右子树。 也就是说访问到非空结点后，函数并不会对该结点进行打印，而是先去访问当前结点的左子树，等左子树访问结束后再回来打印当前结点的具体内容然后再去访问右子树。

函数代码：

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

        与前序遍历只有打印当前结点数值的代码位置不同。代码分析如下所示：

 （3）后序遍历

        后序遍历就是先访问当前结点的左子树在访问当前结点的右子树最后在访问当前结点。

函数代码：

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

（4）层次遍历

        层次遍历是一层一层的遍历二叉树，从上到下从左到右一次打印每一个结点。这里我们需要使用队列来辅助完成。首先将根节点入队列，如果队列不为空那么就开始出队列，当根节点出队列之后，会将不为空的孩子结点带入队列 。然后循环继续，直到队列为空停止循环全部打印完毕。这里应用的就是队列先进先出的性质，只有上一层的全部出完，才会弹出下一层进行打印。

函数代码：

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if ( root )
	{
		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);
		}
	}
	printf("\n");
	QueueDestroy(&q);
}

1.2二叉树的结点个数

        计算二叉树结点个数时我们首先想到的就是采用计数器的方式来进行计数。遍历二叉树，遇到不为空的结点计数器就加一，当遍历结束后，计数器中的数值即为结点个数。但是，遍历二叉树需要采用递归调用，如果计数变量创建在函数内部，那么每次递归调用时都会从新创建该变量，并且函数递归时内部的变量增加并不会影响上一层中变量的大小。因此我们的变量需要创建为全局变量，这样数值才会保存。但是还要注意一点，再一次的调用前需要将全局变量count进行归零处理，否则计数会叠加在一起。

最终我们实现的函数代码如下所示：

int count = 0;
void TreeSize(BTNode* root)
{
	if ( root == NULL )
	{
		return;
	}
	count++;
	TreeSize(root->left);
	TreeSize(root->right);
}
int main()
{
    BTNode* root=CreatBinaryTree();
    TreeSize(root);
    printf("%d",count);
    count=0;//先归零处理在调用
    TreeSize(root);
    printf("%d",count);
    return 0;
}

        上述方式虽然容易想到，但是实现起来太过于麻烦，并且全局变量的使用可能会造成一些潜在的危险。能不能使用递归来实现呢？答案是肯定的，我们可以这样实现。访问每一个结点，如果当前结点为空指针，那么该位置没有结点，返回0；如果当前结点不为空，那么结点个数为当前结点的左子树中结点的个数加上右子树中结点的个数再加上1（1代表当前不为空的结点）。

函数代码：

int TreeSize(BTNode* root)
{
	if ( root == NULL )
	{
		return 0;
	}
	return 1 + TreeSize(root->left) + TreeSize(root->right);
}

1.3二叉树的叶子个数

        求解二叉树的叶子个数也是经常需要的一个功能函数。叶子即为二叉树中左右孩子结点都为NULL的结点，采用的方式也是递归计算。具体方法为：判断当前结点是否为空，如果为空则说明该节点没有左右孩子，因此不为叶子结点，返回0。如果结点不为空，则判断该节点的左右孩子是否为空，如果都为空则为叶子结点，返回1。若都不满足，则叶子结点个数为左子树中的叶子结点加上右子树中的叶子结点个数。

        如上图所示，蓝色圈框出来的为返回1的结点，橙色框出来的为返回0的结点，最终根节点1左子树返回1，右子树返回2，所以最终结果为3。 

函数代码：

int TreeLeafSize(BTNode* root)
{
	if ( root == NULL )
	{
		return 0;
	}
	if ( root->left == NULL && root->right == NULL )
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

1.4二叉树第K层的结点个数

        二叉树K层结点个数计算是相对比较复杂递归计算。这里有一个前提，K需要大于等于1。那如何用递归来计算呢？我们将问题拆分，在计算当前结点第K层的节点个数时先判断当前节点是否为空，如果为空则返回0；然后在判断此时K是否为1，如果K为1计算的就是该结点所在层数的节点个数，因此此节点即为需要查找的结点，那么我们就返回1。如果既不是空K也不为1，那么对于根结点来说的第K层相对于根节点左子树和右子树的第K-1层。此时问题转化为计算该节点左子树中第K-1层结点的个数与右子树中第K-1层结点个数的和即为二叉树第K层结点个数。

例如计算下图中二叉树第3层结点个数：

函数代码：

int TreeKlevel(BTNode* root, int k)
{
	assert(k >= 1);
	if ( root == NULL )
	{
		return 0;
	}
	if ( k == 1 )
	{
		return 1;
	}
	return TreeKlevel(root->left, k - 1) + TreeKlevel(root->right, k - 1);
}

1.5二叉树的查找

        二叉树的查找采用的是拆分思想，遍历整个二叉树去寻找查找的结点。我们可以先查找当前结点是否为查找的结点，如果是返回，如果不是那就去当前结点的左子树中查找，找到就返回，找不到我们就去当前结点的右子树中查找，找到返回，找不到则代表二叉树中并没有该查找结点，此时返回空。当然，当遇到空结点时也需要返回空。为了避免重复查找，我们需要将从左子树和右子树中带回的结点都要保存，然后验证是否为空，不为空代表找到了，为空代表找不到。例如在下面的二叉树中找寻3。

函数代码：

BTNode* TreeFind(BTNode* root,BTDataType x)
{
	if ( root == NULL )
	{
		return NULL;
	}
	if ( root->data == x )//找到返回
	{
		return root;
	}
	//查找左树
	BTNode* ret1 = TreeFind(root->left, x);
	if ( ret1 != NULL )//找到返回
	{
		return ret1;
	}
	//查找右树
	BTNode* ret2 = TreeFind(root->right, x);
	if ( ret2 != NULL )//找到返回
	{
		return ret2;
	}
	//找不到
	return NULL;
}

1.6二叉树的深度

        二叉树的深度计算也可以使用拆分思想来做，求解一颗二叉树的最大深度我们可以分解为该树的左子树与右子树中的最大深度加当前根结点深度1来计算。

函数代码：

使用size来保存左右子树递归的数值，避免重复递归。

int TreeDepth(BTNode* root)
{
	if ( root == NULL )
	{
		return 0;
	}
	int size1 = TreeDepth(root->left) + 1;
	int size2 = TreeDepth(root->right) + 1;
	return size1 > size2 ? size1 : size2;
}

1.7判断是否为完全二叉树

        完全二叉树的性质就是前h-1层都是满二叉树，第h层的结点都是从左到右连续的结点。那么如何判断是否为完全二叉树呢？这里采用的也是层次遍历的方式，我们将每一个结点利用层次打印的原理将其入队列，只不过为空也要放进队列，当队列出数据遇到空的时候进行判断，如果后面数据全是空那么就是完全二叉树，如果后面存在不为空的数据，那么就不是完全二叉树。

函数代码：

bool TreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if ( root )
	{
		QueuePush(&q, root);
	}
	while ( !QueueEmpty(&q) )
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//无论孩子是否为空都要入队列
		if ( front )
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
		else//遇到空跳出
		{
			break;
		}
	}
	while ( !QueueEmpty(&q) )
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//如果后面全是空则为完全二叉树如果不是则为不完全二叉树
		if ( front )
		{
			QueueDestroy(&q);
 
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

1.8二叉树销毁

        二叉树的销毁采用后序遍历效率比较高。如果采用其他遍历方式，当根节点被释放后就无法找到根节点的孩子进行释放，而采用后续遍历是将每一个结点的孩子释放完毕后才会释放该节点本身。 

函数代码：

void BinaryTreeDestroy(BTNode* root)
{
	if ( root == NULL )
	{
		return;
	}
	BinaryTreeDestroy(root->left);
	BinaryTreeDestroy(root->right);
	free(root);
}

二、二叉树的OJ初阶练习题

2.1二叉树的构建与中序遍历

题目链接：二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

题目描述：编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

        该题目中的二叉树是使用字符串进行搭建的，遍历字符串并且以前序的方式进行二叉树的搭建，先搭建根，然后是左子树，最后是右子树，遇到 # 说明该树构建完毕。例如字符串ABC##DE##GF###使用前序构建二叉树的流程图如下所示。

        那我们就需要将字符数组中的内容一一取出来，根据内容来构建二叉树。首先取出数组内容检查是不是 # 如果是，则说明遇到子树结束的字符，应当返回NULL并且字符内容向后移动。如果不是，那我们需要先创建一个根节点，根节点的数值内容即为此数组此时对应的字符，构建完毕后字符需要向后移动一位，指向新的字符内容。构建完根节点需要构建左子树，使用递归，将左子树分解为构建根，左子树，右子树的过程。左子树构建完毕，再去构建右子树，同样使用递归，分解成构建根，左子树，右子树的过程。

        需要注意一点，指向字符数组下标的变量在传参的时候应使用指针传递，然后对其使用解引用操作来控制自增。这样才能保证在每层递归自增时，增加的是同一个变量。如果为传值调用，变量在每层递归时都会创建临时变量，临时变量的自增并不会影响上一层中的变量。

        使用前序构建完成后，调用中序打印函数输出即可。

函数代码：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef char BTDataType;
typedef struct BTNode
{
    BTDataType data;
    struct BTNode*left;
    struct BTNode*right;
}BTNode;
//创建结点函数
BTNode* BuyNode(BTDataType x)
{
    BTNode*node=(BTNode*)malloc(sizeof(BTNode));
    assert(node);
    node->left=NULL;
    node->right=NULL;
    node->data=x;
    return node;
}
//前序遍历数组构建二叉树
BTNode* createbinarytree(char* ch,int* pi)
{
    if(ch[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root=BuyNode(ch[(*pi)++]);
    root->left=createbinarytree(ch,pi);
    root->right=createbinarytree(ch,pi);
    return root;
}
//中序打印输出函数
void PreOrder(struct BTNode*root)
{
    if(root==NULL)
    {
        return;
    }
    PreOrder(root->left);
    printf("%c ",root->data);
    PreOrder(root->right);
}
int main()
{
    char ch[100]={0};
    scanf("%s",ch);
    int i=0;
    BTNode* root=createbinarytree(ch,&i);
    PreOrder(root);
    return 0;
}

2.2单值二叉树

题目链接：965. 单值二叉树 - 力扣（LeetCode）

题目描述：如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

        该题目就是让我们去判断一颗二叉树中每个结点的数值是不是都相等，如果全部相等则为真，不相等则为假。空树也符合真。我们可以使用递归来进行比较，每一棵二叉树都可以看出判断跟与他的左子树和右子树是否相等，如果不相等就返回false相等则继续去递归调用判断。

例如判断下面二叉树是否为单值二叉树。

函数代码：

bool isUnivalTree(struct TreeNode* root)
{
    if(root==NULL)
    {
        return true;
    }
    if(root->left&&root->val!=root->left->val)
    {
        return false;
    }
    if(root->right&&root->val!=root->right->val)
    {
        return false;
    }
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

2.3相同的树

题目链接：100. 相同的树 - 力扣（LeetCode）

题目描述：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

        注意，该题目在判断两棵树相同的时候是要确保两棵树在结构上，数值上都要相同。这里我们也可以采用分治思想。判断两棵树是否相等，在拿到两棵树的根节点的时候可以判断两棵树的根节点是否相等，如果相等则继续判断两棵树的左右子树是否相等，如果都相等则证明两棵树相等，但凡有一个地方不相同，那么就返回false 。

        但是我们还要排除一些特殊情况，如果两棵树上来就是空树，那么直接就可以返回true，如果一颗为空树，一颗不为空树，那么就直接返回false。

分析：

函数代码：

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if(p==NULL&&q==NULL)
    {
        return true;
    }
    if(p==NULL||q==NULL)
    {
        return false;
    }
    if(p->val!=q->val)
    {
        return false;
    }
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

2.4对称二叉树

题目链接：101. 对称二叉树 - 力扣（LeetCode）

题目描述：给你一个二叉树的根节点 root ， 检查它是否轴对称。

        对称二叉树又称为镜像二叉树，我们要判断一颗二叉树是否为镜像二叉树，那么该二叉树的左子树中的每一个左孩子都与右子树中的每一个右孩子相等，左子树中每一个右孩子都得和右子树中的每一个左孩子相等。例如下图即为一颗对称二叉树。

        那我们就可以在拿到根节点后，直接将左子树与子树套用判断相等的函数即可，只不过递归条件是root->left与root->right比较。

函数代码：

bool iscompare(struct TreeNode*p,struct TreeNode*q)
{
    if(p==NULL&&q==NULL)
    {
        return true;
    }
    if(p==NULL||q==NULL)
    {
        return false;
    }
    if(p->val!=q->val)
    {
        return false;
    }
    return iscompare(p->left,q->right)&&iscompare(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root){
if(root==NULL)
{
    return true;
}
return iscompare(root->left,root->right);
}

2.5另一棵树的子树

题目链接：572. 另一棵树的子树 - 力扣（LeetCode）

题目描述：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

        判断是否为子树，我们需要先说明哪种情况下是子树。例如下图中，左图符合子树，右图却不符合

        因此我们可以采用递归方式进行拆分求解，判断subroot是否为root的子树，我们首先判断root的当前结点是否与subroot满足相等，如果不是，我们就去root的左子树和右子树分别寻找。找到了就返回true，找不到就返回false。判断是否相等可以继续套用相等函数。

函数代码：

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(p==NULL&&q==NULL)
    {
        return true;
    }
    if(p==NULL||q==NULL)
    {
        return false;
    }
    if(p->val!=q->val)
    {
        return false;
    }
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root==NULL)
    {
        return false;
    }
   if( isSameTree(root,subRoot))
   {
       return true;
   }
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}