二叉树+oj
什么是链式结构？
二叉树我之前阐述过了，有两种储存方式，具体的可以在我这篇博客了解：二叉树入门详解
链式结构中一个节点内有数值和左孩子以及右孩子的指针，我目前创建二叉树还是直接手动创建的，这篇博客主要讲的是我对二叉树的的具体操作！
我将构造这个二叉树，下面除oj题外所有操作都是基于我构造的这个二叉树的
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType val;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTN;
BTN* BuyBinaryTreeNode(BTDataType x)//申请一个节点的空间
{
BTN* tam = (BTN*)malloc(sizeof(BTN));
if (tam == NULL)
{
printf("malloc fail\n");
exit(-1);
}
tam->val = x;
tam->left = NULL;
tam->right = NULL;
}
BTN* CreatBinaryTree()
{
BTN* node1 = BuyBinaryTreeNode(1);
BTN* node2 = BuyBinaryTreeNode(2);
BTN* node3 = BuyBinaryTreeNode(3);
BTN* node4 = BuyBinaryTreeNode(4);
BTN* node5 = BuyBinaryTreeNode(5);
BTN* node6 = BuyBinaryTreeNode(6);
BTN* node7 = BuyBinaryTreeNode(7);
node1->left = node2;
node1->right = node3;
node2->left = node4;
node2->right = node5;
node3->left = node6;
node3->right = node7;
return node1;
}
int main()
{
BTN* tree = CreatBinaryTree();
return 0;
}
二叉树操作的思路
二叉树的结构我们思考一下，大致是一个根节点然后带两个子树，子树又可以分为一个根节点加两个子树（子树有可能是空节点）
根据结构我们可以发现解决有关二叉树的问题时，我们可以用递归来解决，我们都可以从：根节点+左子树+右子树出发，一直递归，并且递归的终止条件就是遇到空节点
二叉树的前/后/中序遍历
相同点：都是把整个二叉树遍历一遍
不同点：遍历的顺序不同
前序：根节点+左子树+右子树
中序：左子树+根节点+右子树
后序：左子树+右子树+根节点
注意前面三个遍历指的是每个结点都是这样的
层序：设根节点为第一层，然后从上到下访问每一层的所有结点。
注：我们下面的操作都是以上面直接构造的二叉树为例的
我在这边画一下谦虚遍历的情况，中序以及后序遍历思想都是一样的
下面是前序遍历的数字顺序：
要点：我们将每个结点都看作是一个根节点，然后根据前序遍历的规则：跟+左+右遍历整个二叉树
void PrevOrder(BTN* root)//前序遍历
{
if (root == NULL)//首先判断一下该节点是否为空结点
{
printf("NULL ");
return;
}
//不是NULL
printf("%d ", root->val);//根节点
PrevOrder(root->left);//左子树
PrevOrder(root->right);//右子树
}
void InOrder(BTN* root)//中序遍历
{
if (root == NULL)//首先判断一下该节点是否为空结点
{
printf("NULL ");
return;
}
//不是NULL
InOrder(root->left);//左子树
printf("%d ", root->val);//根节点
InOrder(root->right);//右子树
}
void PostOrder(BTN* root)//后序遍历
{
if (root == NULL)//首先判断一下该节点是否为空结点
{
printf("NULL ");
return;
}
//不是NULL
PostOrder(root->left);//左子树
PostOrder(root->right);//右子树
printf("%d ", root->val);//根节点
}
前面画了一张前序数字的遍历图，下面画一张中序遍历的函数栈帧！
**注：**由于是递归，我们先判断递归的结束条件，防止栈溢出无限递归的出现。
二叉树的层序遍历
层序：设根节点为第一层，然后从上到下访问每一层的所有结点。
思路：
层序遍历不能用递归的思想，而是用得借用队列先进先出的性质。
1，头结点入队
2.上一个结点入队的时候，下一结点出队
3，注意：入队的时候必须是非空
注意：因为用的是C语言，所以我们还要自己构造队列
其实跟我们之前写的队列差不多，只需要改这个tyepedef
struct BinaryTreeNode*QDataType表示此时队列的元素是指针
Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef struct BinaryTreeNode* QDataType;//注意这个时候队列的元素变成了结构体指针
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
QueueNode* front;
QueueNode* rear;
}Queue;
void QueueInit(Queue* ps);//队列的初始化
void QueueDestory(Queue* ps);//队列的销毁
void QueuePush(Queue* ps, QDataType x);//入队
void QueuePop(Queue* ps);//出队
bool QueueEmpty(Queue* ps);//判断队列是否为空
size_t QueueSize(Queue* ps);//返回队列中元素的个数
QDataType QueueFront(Queue* ps);//返回队头元素
QDataType QueueRear(Queue* ps);//返回队尾元素
Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"QUeue.h"
void QueueInit(Queue* ps)//队列的初始化
{
assert(ps);//如果储存指针的地址都为空的话，肯定是错误的
//刚开始的头指针与尾指针肯定是相等的，并且都是NULL
ps->front = ps->rear = NULL;
}
void QueueDestory(Queue* ps)//队列的销毁
{
assert(ps);
QueueNode* cur = ps->front;
while (cur)
{
QueueNode* ret = cur->next;
free(cur);
cur = ret;
}
ps->front = ps->rear = NULL;
}
void QueuePush(Queue* ps, QDataType x)//入队
{
assert(ps);//入队肯定是与尾指针rear有关的 先申请一个空间
QueueNode* cur = (QueueNode*)malloc(sizeof(QueueNode));
if (cur == NULL)
{
printf("malloc fail\n");
exit(-1);
}
cur->data = x;
cur->next = NULL;
/* QueueNode* ret = ps->rear->next;
ps->rear = cur;这样写的话很有问题，没有判断当两个指针都为空指针的情况
ps->rear = ret;*/
if (ps->rear == NULL)
{
assert(ps->front == NULL);//当尾指针为空的时候，头指针不可能不为空
ps->front = ps->rear = cur;
}
else
{
ps->rear->next = cur;
ps->rear = cur;
}
}
void QueuePop(Queue* ps)//出队
{
assert(ps);//出队也是头删
assert(ps->front != NULL);//如果头指针为空的话肯定是错误的
//队列中只有一个结点
if (ps->front == ps->rear)
ps->front = ps->rear = NULL;
else
{
//ps->front = ps->front->next;这样写的话涉及到内存泄露
QueueNode* ret = ps->front->next;
free(ps->front);
ps->front = ret;//这样写的话就不会涉及到什么内存泄露啦
}
}
bool QueueEmpty(Queue* ps)//判断队列是否为空
{
assert(ps);
//当头指针为空的时候，队列就是空的
return ps->front == NULL;
}
size_t QueueSize(Queue* ps)//返回队列中元素的个数
{
assert(ps);
int sum = 0;
QueueNode* cur = ps->front;
while (cur)
{
sum++;
cur = cur->next;
}
return sum;
}
QDataType QueueFront(Queue* ps)//返回队头元素
{
assert(ps);
assert(ps->front != NULL);
return ps->front->data;
}
QDataType QueueRear(Queue* ps)//返回队尾元素
{
assert(ps);
assert(ps->rear != NULL);
return ps->rear->data;
}
层序遍历：
void LevelOrder(BTN* root)
{
Queue st;
QueueInit(&st);//此时队列中元素表示的是指针
QueuePush(&st, root);
while (!QueueEmpty(&st))//当队列非空的时候
{
//上一个节点出队的时候，该节点的子节点入队（但是要求子节点非空）
BTN* cur = QueueFront(&st);
QueuePop(&st);//弹出该节点
if (cur == NULL)
break;
printf("%d ", cur->val);
if (cur->left != NULL)
QueuePush(&st, cur->left);
if (cur->right != NULL)
QueuePush(&st, cur->right);
}
}
二叉树的节点个数
思路：
节点个数 = 根节点+左子树节点个数+右子树节点个数
int BinaryTreeSize(BTN* root)//二叉树的节点个数
{
if (root == NULL)
return 0;
return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
二叉树叶子节点的个数
思路:返回左子树叶子节点以及右子树叶子节点
int BinaryTreeLeafSize(BTN* root)//叶子节点必须保证左子树为NULL 右子树为NULL
{
if (root == NULL)//空节点直接返回
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
二叉树第k层节点的个数
思路：
查找第k层的节点个数
假设k = 1层，直接返回第一层的节点个数
k = 2时，返回的是以第二层的节点为根节点的第一层的节点个数
(这个思路可能没解释清楚）
结合下面的代码思考一下，当k = 2的时候，返回的不就是第一个节点的左右子树的结点数嘛?
注：我们的参数就是一个指针，只能返回1，但是最终的返回值是左右两边的和
意思是两个参数，当k的那个参数为1的时候，返回该层的个数即可
int BinaryTreeLevelKSize(BTN* root, int k)
{
if (root == NULL)
return 0;
//当k = 1的时候，返回1即可
if(k==1)
return 1;
//当k不等于1的时候
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
//返回的是k = 1的时候左右子树的节点个数
}
查找二叉树中值为X的节点
思路：
查询根节点，若根节点不符合，查询左子树，查询右子树
递归即可！
BTN* BinaryTreeFind(BTN* root, BTDataType x)
{
if (root == NULL)//当指针为空指针的时候
return NULL;
if (root->val == x)
return root;
BTN* tal = BinaryTreeFind(root->left, x);
if (tal)//当查询左子树的返回值不为空的时候，直接返回即可，就不用区查询右子树
return tal;
/*BTN* tar = BinaryTreeFind(root->right, x);
if (tar)
return tar;*/
//还可以这样写
return BinaryTreeFind(root->right, x);
}
判断二叉树是否是完全二叉树
思路：其实和层序遍历类似，也是要先写一个队列结构，然后上一个元素出队列的时候，其子节点入队，然后当出队的元素是NULL时，跳出循环，然后遍历剩余队列，如果队列后面还有数字，那么就不是完全二叉树
**注意：此时不上一个节点只要出队了，其子节点就要入队，不用管其子节点是否为空节点
bool BinaryTreeComplete(BTN* root)//判断二叉树是否为完全二叉树
{
if (root == NULL)
return false;
Queue st;
QueueInit(&st);
QueuePush(&st, root);
while (!QueueEmpty(&st))
{
BTN* cur = QueueFront(&st);//因为要出队，所以我们要记录此时的队列首元素
QueuePop(&st);
if (cur == NULL)
break;//如果元素是NULL便跳出循环 否则入队
//此时入队与层序遍历不同，不论是否为NULL都得入
QueuePush(&st, cur->left);
QueuePush(&st, cur->right);
}
while (!QueueEmpty(&st))//此时依次遍历队列，观察每个队列中是否有数字
{
BTN* cur = QueueFront(&st);//因为要出队，所以我们要记录此时的队列首元素
QueuePop(&st);
if (cur != NULL)
return false;
}
//此时说明队列全部出完了，此时证明为完全二叉树
return true;
}
二叉树的高度
思路：
二叉树的高度 = max（左子树的高度，右子树的高度）+1（根节点）
int BrnaryTreeHigh(BTN* root)//计算树的高度
{
if (root == NULL)//递归到空节点时返回0
return 0;
return max(1 + BrnaryTreeHigh(root->left), 1 + BrnaryTreeHigh(root->right));
}
二叉树的销毁
思路：我们直到，二叉树的构建是从上到下的，但是二叉树的销毁不能也是这样，因为如果我们先销毁根节点的话，那么我们的子节点就找不到了，所以我们应该先销毁左子树，再销毁右子树，最后销毁根节点的顺序来实施
oj
思路：只要父节点的值不等于孩子的值就返回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);
}
相同的树
思路直接写在代码里
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
//如果两个节点都为空节点，那么返回true
if(p==NULL&&q==NULL)
return true;
//如果只有一个节点为空节点，返回false
if(p==NULL||q==NULL)
return false;
//现在两个节点都不是空节点了，判断一下值是否相等
//如果不相等直接返回false
if(p->val!=q->val)
return false;
//该节点判断完毕，然后判断一下左右子树
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
另一棵树的子树
思路：
依次遍历树的每一个节点，然后以该节点为根节点，跟另一棵树比较是否相等，就是套用一下上一题的代码，easy
bool checksame(struct TreeNode*p1,struct TreeNode*p2)
{ //这个函数判断的就是两个树是否相等
if(p1==NULL&&p2==NULL)//两棵树都为空的时候
return true;
if(p1==NULL||p2==NULL)//一棵为空，另外一颗不为空的时候
return false;
if(p1->val!=p2->val)
return false;
//接下来判断树的左右两颗子树是否相等
return checksame(p1->left,p2->left)
&&checksame(p1->right,p2->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(root==NULL)
return false;
//遍历每个以每个节点为根的子树
if(checksame(root,subRoot))
return true;
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}
二叉树遍历
思路：
还是递归：
先判断该节点是否为空，如果不为空，赋值，然后判断左右子树
#include<stdio.h>
#include<stdlib.h>
typedef char BTDataType;
typedef struct TreeNode {
BTDataType val;
struct TreeNode* left;
struct TreeNode* right;
}BTN;
BTN* CreatBinaryTree(BTDataType *a,int*pi)
{
//当字符是'#'的时候，是空指针
if(a[*pi]=='#')
{
(*pi)++;
return NULL;
}
//此时字符不是'#'的时
BTN*tam = (BTN*)malloc(sizeof(BTN));
if(tam==NULL)
{
printf("malloc fail\n");
exit(-1);
}
tam->val = a[(*pi)++];//开辟了根节点之后
tam->left = CreatBinaryTree(a,pi);//理解这个。此时是以该节点的左孩子为根节点
//递归创造！
tam->right = CreatBinaryTree(a,pi);
return tam;
}
void InOrder(BTN*root)
{
if(root==NULL)
return ;
InOrder(root->left);
printf("%c ",root->val);
InOrder(root->right);
}
int main()
{
char arr[100] = {0};
scanf("%s",arr);
int i = 0;
BTN*tree = CreatBinaryTree(arr,&i);
//这边一定记得是传地址，因为需要改变i的值
InOrder(tree);
return 0;
}
欢迎三连！！！多谢铁子支持！！！
