@[TOC]
前言
思维图
建议
- 二叉树是一种
递归结构!!!!!!!!!,这一点一定要时刻牢记。- 递归利用
分而治之的思想 ，对于解决二叉树问题，很方便- 递归我们一般建议先判断
假的情况，这会很大层度方便解决问题。- 在使用递归时，如果不能一下完成所有代码，可以先完成大致的部分，之后慢慢补齐细节问题。
递归的3要素
- 递归函数返回值的使用问题
- 递归函数的参数设置问题
- 递归的结束条件的判断问题。
二叉树的创建
OJ题目
思路
树是一个递归结构，因此这里使用递归的思路构建二叉树。
- 函数返回值问题。构建完成的二叉树，必然需要根结点的地址。
函数形参问题：
root->left = BinaryTreeCreat(++str); root->right= BinaryTreeCreat(++str);如果这里使用
++str，当递推到本层后，对于右子树的构建，访问字符串可能就会是已访问的位置。因此这里可以使用 全局变量，或者一个指针i，通过改变i的指向内存中的数据，我们就可以正确控制访问字符串。
代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
//思路，二叉树是递归结构，为了构建二叉树，所以应该先构建好二叉树的左右子树，
//BTNode* BinaryTreeCreat(const char*str,int *i);//创建二叉树.
//但是对于字符串来说，单一的通过++str，是不行的---当回归时会发生意外的情况。
//因此这里使用 指针变量i来控制访问字符串。
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
void InOrder(BTNode* root)// 二叉树中序遍历
{
if (root==NULL)
{
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}
BTNode* BuyNode(BTDataType x)
{
BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));
if (tmp==NULL)
{
printf("tmp==NULL\n");
exit(-1);
}
tmp->data = x;
tmp->left = NULL;
tmp->right = NULL;
return tmp;
}
BTNode* BinaryTreeCreat(const char*str,int *i)//创建二叉树.
{
if (str[*i] == '\0'|| str[*i]== '#')
{
++(*i);
return NULL;
}
BTNode* root = BuyNode(str[*i]);
++(*i);
root->left = BinaryTreeCreat(str,i);
root->right= BinaryTreeCreat(str,i);
return root;
}
int main()
{
char arr[100]={0};
while(fgets(arr,100,stdin))
{
int i=0;
BTNode*root= BinaryTreeCreat(arr,&i);
InOrder(root);
}
}
二叉树的销毁
思路
要想销毁根结点，必然先销毁左右子树—递归分而治之。
代码
void BinaryTreeDestory(BTNode* root)// 二叉树销毁
{
if (root == NULL)
{
return;
}
BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);
free(root);
root = NULL;
}二叉树的深度
思路
代码
int BinaryTreeH(BTNode* root)//二叉树的深度
{
return root ? 0:1+fmax(BinaryTreeH(root->left),BinaryTreeH(root->right));
}二叉树节点个数
思路
因为二叉树也是由很多小二叉树构成，因此计算一个二叉树的结点个数，先 求小二叉树的节点个数，这就成了一个递归问题，
分而治之。递归结束条件是遇到空小二叉树。
代码
int BinaryTreeSize(BTNode* root)// 二叉树节点个数
{
return root ?0: BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
} 二叉树叶子节点个数
思路
当结点的left=right==NULL,才是叶节点同样也需要求左右子树—分而治之—递归实现。
代码
int BinaryTreeLeafSize(BTNode* root)// 二叉树叶子节点个数
{
if (root == NULL)//空树是没有叶结点
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}二叉树第k层节点个数
思路
- 这里认为第一层的下标是从1开始的。
- 因为递归是从二叉树的第一层开始的，而要想去到二叉树的第k层，需要一些判断，二叉树是由小二叉树构成的，去求第k层，也就是去看第k层有多少个二叉树根结点。通过--k，当k=1时，代表递归到达第k层
代码
int BinaryTreeLevelKSize(BTNode* root, int k)// 二叉树第k层节点个数// 二叉树第k层节点个数
{
assert(k >=1);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BinaryTreeLevelKSize(root->left,k-1) + BinaryTreeLevelKSize(root->right,k-1);
}二叉树查找值为x的第一个节点
思路
- 同样使用分而治之的思路
- 因为不确定x是否唯一，因此我们可以先遍历左子树，之后右子树。
同时通过一个变量去记录结点地址，防止没必要的重复递归.—这一步在很多递归题目中都有体现，记录结果可以防止没必要的函数栈帧的时间开销。- 判断是否找到的条件是：
我们可以发现，如果一直递归，必然要遇到空树.
如果在遇到空树前找到了，递归就结束了。
如果遇到空树，说明该路没找到.返回NULL
代码
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)// 二叉树查找值为x的第一个节点
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* leftroot = BinaryTreeFind(root->left, x);
if (leftroot != NULL)
{
return leftroot;
}
BTNode* rightroot = BinaryTreeFind(root->right, x);
if (rightroot != NULL)
{
return rightroot;
}
return NULL;
}判断二叉树是否是完全二叉树
思路：队列
如果以层序遍历一个二叉树，如果当队列头为NULL,之后都是NULL，那么为完全二叉树，反之为非完全二叉树。原因：
- 完全二叉树不可能在一层为满的情况下，在下一层有结点。
- 虽然我们可以通过去右子树存在，左子树不存在在一定层度判断是否为完全二叉树，但是这不严谨。如下图，虽然满足条件，但却不是完全二叉树。
代码
bool BinaryTreeComplete(BTNode* root)// 判断二叉树是否是完全二叉树
{
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueTop(&q);
QueuePop(&q);
if (front == NULL)
{
break;
}
else
{
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
}
// 遇到空了以后，检查队列中剩下的节点
// 1、剩下全是空给，则是完全二叉树
// 2、剩下存在非空，则不是完全二叉树
while (!QueueEmpty(&q))
{
BTNode* front = QueueTop(&q);
QueuePop(&q);
if (front)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}判断2个二叉树是否相等
思路
判断2个二叉树是否相等，必然要去判断左右子树是否相等。因此递归–分而自治
代码
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
//最小的树的左右孩子都为空，代表为真.
if(p==NULL&&q==NULL)
{
return true;
}
//p.q其中一个为空代表fasle.
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);
}