前言
上一篇博客给大家讲解了介绍了二叉树的相关概念及其堆的实现，今天为大家带来的内容是二叉树的各个接口函数的实现及其相关的OJ练习题。好了，我们话不多说直接进入今天的正题。(一) 二叉树的接口实现
首先我们来写一下二叉树的结构：
这里我们要实现的是链式二叉树，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。typedef char BTDataType;
typedef struct BinaryTree
{
BTDataType node;
struct BinaryTree* leftChild;
struct BinaryTree* rightChild;
}BTNode;
构建二叉树
在学习二叉树的各个接口之前我们需要自己先来构建一棵二叉树，这里我们以下图的二叉树为准：
//创建二叉树节点
BTNode* BTCreate(BTDataType x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (!newnode) {
perror("malloc fail::");
exit(-1);
}
else
{
newnode->node = x;
newnode->leftChild = newnode->rightChild = NULL;
}
return newnode;
}
//通过结点建树
BTNode* CreatNode()
{
BTNode* NodeA = BTCreate('A');
BTNode* NodeB = BTCreate('B');
BTNode* NodeC = BTCreate('C');
BTNode* NodeD = BTCreate('D');
BTNode* NodeE = BTCreate('E');
BTNode* NodeF = BTCreate('F');
BTNode* NodeG = BTCreate('G');
BTNode* NodeH = BTCreate('H');
NodeA->leftChild = NodeB;
NodeA->rightChild = NodeC;
NodeB->leftChild = NodeD;
NodeB->rightChild = NodeE;
NodeE->rightChild = NodeH;
NodeC->leftChild = NodeF;
NodeC->rightChild = NodeG;
return NodeA;
}
前序遍历
前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
前序遍历的本质是先访问根节点，再访问左子树，最后访问右子树
这里我们可以画一下递归展开图来帮助我们更好的理解前序遍历
通过递归展开图我们可以发现该二叉树前序遍历的结果为：
💕 代码实现
void BTPrevOrder(BTNode* root)
{
if (root == NULL) {
printf("NULL ");
return;
}
printf("%c ", root->node);
BTPrevOrder(root->leftChild);
BTPrevOrder(root->rightChild);
}
中序遍历
中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。
中序遍历的本质是先访问左子树，再访问根节点，最后访问右子树
当前二叉树的中序遍历结果为：
💕 代码实现
void BTInOrder(BTNode* root)
{
if (root == NULL) {
printf("NULL ");
return;
}
BTInOrder(root->leftChild);
printf("%c ", root->node);
BTInOrder(root->rightChild);
}
后序遍历
后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
后序遍历的本质是先遍历左子树，在遍历右子树，最后遍历根
当前二叉树的后序遍历结果为：
💕 代码实现
void BTPostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
BTPostOrder(root->leftChild);
BTPostOrder(root->rightChild);
printf("%c ", root->node);
}
层序遍历
层序遍历——从左到右一层一层的区遍历二叉树。
设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
💕 思路：
在这里我们的层序遍历需要借助一个队列来实现，由于C语言的库中没有队列，所以我们需要调用我们之前写好的队列来进行辅助。
我们分为两层while循环来实现这个过程，最外层的while循环来判断队列是否为空，内层的while循环来判断二叉树的每一层的所有节点是否已经全部出队
首先如果根节点不为空，首先将根节点入队列，创建一个变量levelSize来统计每一层的节点个数，在这里我们先将levelSize置为1，然后进入外层循环队列不为空的判断条件，紧接着进入内层循环，先将队头元素保存到一个BTNode*的指针中，然后打印队头元素，就这样每打印并将一个队头元素出队后，如果该队头元素的左右指针不为空，就将其左右孩子入队。
当二叉树的某一层的元素全部出队后，他的下一层的所有元素也就全部入队了，这是恰好跳出内层循环，再次用levelSize统计队列中的元素个数，外层循环是队列判空的条件，所以只要下一层不为空循环就不会结束，当最后一层数据全部出队后，由于没有元素入队，队列为空，跳出外层循环，最后把队列销毁即可。
💕 代码实现
void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
int levelSize = QueueSize(&q);
while (!QueueEmpty(&q))
{
while (levelSize--)
{
BTNode* front = QueueFront(&q);
printf("%c ", front->node);
QueuePop(&q);
if (front->leftChild)
QueuePush(&q, front->leftChild);
if (front->rightChild)
QueuePush(&q, front->rightChild);
}
printf("\n");
//出完一层以后在计算下一层进入队列中的元素个数
levelSize = QueueSize(&q);
}
printf("\n");
QueueDestroy(&q);
}
二叉树的节点个数
这里我们依旧用一种递归的思路来解决：
我们可以从根节点开始遍历，节点个数=根节点+左节点个数+右节点个数 的思想，将每一个节点都看成是一棵二叉树，如果左子树或右子树不为空，就继续递归遍历，如果遇到的根节点是空指针，则返回0，所以当遇到叶子节点时，递归调用结束，开始向上返回结果：以左节点个数+右节点个数+1的形式返回到最上层，最后就可以得到二叉树中节点的个数。
💕 代码实现
int BTSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return 1 + BTSize(root->leftChild) + BTSize(root->rightChild);
}
二叉树叶子节点个数
要求二叉树的叶子节点个数，我们需要做的就是判断节点是否为叶子节点
这里我们还是用递归遍历的思路：如果是叶子节点，那么他的左右指针都为空，并返回1，如果遍历到了叶子节点的左右指针，则返回0；如果不是叶子节点，那么就返回递归左右孩子的函数之和。
💕 代码实现
int BTLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->leftChild == NULL && root->rightChild == NULL)
{
return 1;
}
return BTLeafSize(root->leftChild) + BTLeafSize(root->rightChild);
}
二叉树第K层节点个数
计算二叉树第K层节点的个数对于第一层来说是第K层，如果对于第2层来说相当于计算第K-1层，以此走下去，对于第K层来说就是计算第1层的节点个数，也就是当前层的节点个数，所以我们利用递归的思路，当K不到1时就递归计算K-1层节点的个数之和，如果K大于树的高度，则说明第K层不存在，当K=1时的节点是一个空指针，返回0即可，如果K存在，K=1时，每个递归函数都返回1，最终就会返回第K层节点的个数。
💕 代码实现
int BTLevelKSize(BTNode* root, int k)
{
if (root == NULL)
return 0;
if (k != 1)
{
return BTLevelKSize(root->leftChild, k - 1) + BTLevelKSize(root->rightChild, k - 1);
}
else
{
return 1;
}
}
二叉树的高度
二叉树的高度的计算我们可以递归计算左右子树的高度来比较，如果哪一边更高，哪一边的高度+1就是这棵子树的高度，如果递归到了为空指针的节点，直接返回0即可。这里我们需要注意的是我们为了提高递归的效率，将每一次计算出来的左右子树的高度用两个整型变量保存，防止大量重复递归。
💕 代码实现
int BTHeight(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int leftHeight = BTHeight(root->leftChild);
int rightHeight = BTHeight(root->rightChild);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
查找指定节点
给定一个数据，如果该二叉树中存在某个节点的数据等于该数据，说明可以找到该节点并将他返回即可，如果二叉树没有目标节点，则返回一个空指针。大体思路：如果节点为空，直接返回空；如果节点的数据等于要查找的数据，则找到了并且直接返回该节点，如果不相等，则分别递归左子树和右子树去查找，如果递归左右子树也找不到的话就是这棵树中不存在该节点，直接返回空即可。
💕 代码实现
BTNode* BTFind(BTNode* root, char x)
{
if (root == NULL)
return NULL;
if (root->node == x)
return root;
//递归左子树
BTNode* leftOutcome = BTFind(root->leftChild, x);
if (leftOutcome)
return leftOutcome;
//递归遍历右子树
BTNode* rightOutcome = BTFind(root->rightChild, x);
if (rightOutcome)
return rightOutcome;
return NULL;
}
判断完全二叉树
这儿判断完全二叉树的思路和层序遍历差不多，先将根节点入队列，这里需要用到两次while循环，第一个while循环为找队列中的空指针元素，第二个while循环是为了寻找空指针元素后面的元素中是否存在非空元素。具体思路如下：
第一个while循环中的思路和层序遍历的思路类似，如果队列非空就继续执行，先将队头元素保存并出队，然后判断队头元素是否为空指针，如果不是空指针则将队头元素的左右孩子带入队列，否则跳出while循环。因为完全二叉树是连续的，如果出到了空指针说明队列中可能还存在非空元素，紧接着执行下一个while循环。
这时候队列还不为空，第二个while循环中判断队列中是否还存在非空元素，依次取队头元素判断即可，如果遇到非空元素直接销毁队列并返回false，否则继续出队并进行下一次判断。
💕 代码实现
bool BTComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q,root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL)
{
QueuePush(&q, front->leftChild);
QueuePush(&q, front->rightChild);
}
else
{
break;
}
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
if (front == NULL)
{
QueuePop(&q);
}
else
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
销毁二叉树
二叉树的销毁需要用到后序遍历的思路，对于每一棵子树，都必须先销毁其左右孩子再销毁他的根节点；如果先销毁根节点的话就找不到左右子树节点的地址了。这里我们需要注意的是在主函数中调用销毁二叉树后需要置空一下。
💕 代码实现
void BTDestroy(BTNode* root)
{
if (root == NULL)
return;
BTDestroy(root->leftChild);
BTDestroy(root->rightChild);
free(root);
}
(二) 二叉树基础OJ练习
单值二叉树
💖 思路：
我们需要判断这棵二叉树的每一个节点的值是否都相同，这里我们分为三部分来判断：
- 如果根节点为空指针则无需判断，直接返回true。
- 如果左子树或右子树都不为空并且其节点的值和根节点的值不相同，直接返回false。
- 如果左右子树都不为空并且节点的值等于根节点的值，则继续递归左右孩子的子树即可。
💕 代码实现：
bool isUnivalTree(struct TreeNode* root){
if(!root)
return true;
if(root->left!=NULL&&root->val!=root->left->val)
return false;
if(root->right!=NULL&&root->val!=root->right->val)
return false;
return isUnivalTree(root->left)&&isUnivalTree(root->right);
}
相同的树
💖 思路：
如果两棵树的节点都为空，则无需比较，直接返回true；如果一棵树的节点为空，另一棵不为空，说明两棵树不相同，直接返回false；如果节点都不为空并且他们的值不相等，则直接返回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);
}
另一棵树的子树
💖 思路：
这里我们复用一下上一个题目写过的判断两棵树是否相同的代码会让我们这个题目相对简单点。**1. 题目中告诉我们子树一定不为空，所以一旦root树为空，则说明一定不是子树关系。
- 判断以根节点的子树和subRoot是否相同，如果相同直接返回true。
- 如果跟节点的子树和subRoot不相等则递归判断左子树和右子树是否和subRoot相等，若相等，返回任意一个即可。**
💕 代码实现：
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);
}
二叉树的前序遍历
💖 思路：
因为这里的前序遍历是要将得到的结果储存在数组中的，所以我们需要将本题拆分成三个子函数来解决。**1. 首先我们不知道数组的大小开多大，所以需要写一个求二叉树节点的函数，将二叉树的节点个数返回。
- 第二个函数就是遍历二叉树的函数了，但这里我们需要传一个整型指针，改变数组的下标。
- 最后一个函数的作用就是调用遍历二叉树的那歌函数。并且将数组的内容返回。**
💕 代码实现：
int TreeSize(struct TreeNode*root){
if(root==NULL)
return 0;
return TreeSize(root->left)+TreeSize(root->right)+1;
}
void _preorder(struct TreeNode* root,int* array,int* pi){
if(root==NULL)
return;
array[(*pi)++]=root->val;
_preorder(root->left,array,pi);
_preorder(root->right,array,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
*returnSize=TreeSize(root);
int*TreeData=(int*)malloc(sizeof(int)*(*returnSize));
int i=0;
_preorder(root,TreeData,&i);
return TreeData;
}
二叉树的最大深度
💖 思路：
求二叉树的最大深度也就是求二叉树的高度，二叉树的高度=左右子树高的树+1，上面我们已经实现过，这里就不再细说。💕 代码实现：
int maxDepth(struct TreeNode* root){
if(root==NULL)
return 0;
int LDepth=maxDepth(root->left);
int RDepth=maxDepth(root->right);
return LDepth>RDepth?LDepth+1:RDepth+1;
}
翻转二叉树
💖 思路：
将一棵二叉树翻转我们可以递归翻转每一棵子树，先将二叉树的左子树的根节点和右子树的根节点交换，再分别翻转左子树和右子树，最后返回根节点，如果遇到叶子节点将两个空指针交换一下即可，遇到空节点则直接返回空。💕 代码实现：
struct TreeNode* invertTree(struct TreeNode* root){
if(root==NULL)
return NULL;
struct TreeNode*tmp=root->left;
root->left=root->right;
root->right=tmp;
invertTree(root->left);
invertTree(root->right);
return root;
}
对称二叉树
💖 思路：
**1. 我们需要先判断左右子树的根节点是否相同。
- 如果左子树和右子树的根节点相同，我们需要比较左子树的左节点是否和右子树的右节点相同，左子树的右节点是否和右子树的左节点相同。
- 如果二者都相同，我们在递归判断左子树的左右节点和右子树的左右节点。**
💕 代码实现：
bool _check(struct TreeNode*root1,struct TreeNode*root2)
{
if(!root1&&!root2)
return true;
if(!root1||!root2)
return false;
if(root1->val!=root2->val)
return false;
return _check(root1->left,root2->right)&&_check(root2->left,root1->right);
}
bool isSymmetric(struct TreeNode* root){
return _check(root->left,root->right);
}
平衡二叉树
💖 思路：
平衡二叉树的判定条件是每个节点左右子树的高度差不超过1，那么在这里我们可以借助一下之前的求树的高度的接口函数，和C语言中的求绝对值的函数fabs。
如果左右子树的高度差不超过1，就递归判断左右子树的左右子树，反之只要有一棵子树的左右高度差大于1就返回false。
💕 代码实现：
int maxDepth(struct TreeNode* root){
if(root==NULL)
return 0;
int LDepth=maxDepth(root->left);
int RDepth=maxDepth(root->right);
return LDepth>RDepth?LDepth+1:RDepth+1;
}
bool isBalanced(struct TreeNode* root){
if(root==NULL)
return true;
int flag=fabs(maxDepth(root->left)-maxDepth(root->right));
if(flag>1)
return false;
return isBalanced(root->left)&&isBalanced(root->right);
}
