数据结构(初阶6)---二叉树(遍历——递归的艺术)(详解)
二叉树的遍历与练习
- 一.二叉树的基本遍历形式
- 1.前序遍历(深度优先遍历)
- 2.中序遍历(深度优先遍历)
- 3.后序遍历(深度优先遍历)
- 4.层序遍历！！(广度优先遍历)
- 二.二叉树的leetcode小练习
- 1.判断平衡二叉树
- 1）正常解法
- 2）优化解法
- 2.对称二叉树
通过上一篇文章，我们初识了我们的二叉树
二叉树初识
那么接下来我们就要深入去理解二叉树的部分知识了，显然这只是在二叉树家族中迈出的一小步qwq，入门。
一.二叉树的基本遍历形式
我们先建立一棵伪树,方便我们后续的使用：
int main()
{
BinaryTree p1;
BinaryTree p2;
BinaryTree p3;
BinaryTree p4;
BinaryTree p5;
BinaryTree p6;
p1.left = &p2;
p1.right = &p3;
p2.left = NULL;
p2.right = &p4;
p3.left = &p5;
p3.right = NULL;
p4.left = NULL;
p4.right = &p6;
p6.left = NULL;
p6.right = NULL;
p5.left = NULL;
p5.right = NULL;
p1.val = 'A';
p2.val = 'B';
p3.val = 'C';
p4.val = 'D';
p5.val = 'E';
p6.val = 'F';
}
1.前序遍历(深度优先遍历)
前序遍历的本质，就是根节点->左孩子->右孩子。并且通过递归调用的方式去实现。
如
void treefront(BinaryTree* p)//前序遍历
{
if (p == NULL)
{
printf("NULL ");
return;
}
printf("%c ", p->val);
treefront(p->left);
treefront(p->right);
}
2.中序遍历(深度优先遍历)
同理，中序遍历的本质就是左孩子->根节点->右孩子
如：
void treemid(BinaryTree* p)//中序遍历
{
if (p == NULL)
{
printf("NULL ");
return;
}
treemid(p->left);
printf("%c ", p->val);
treemid(p->right);
}
3.后序遍历(深度优先遍历)
同理，后序遍历的本质就是：左孩子->右孩子->根节点
如：
void treebehind(BinaryTree* p)//后序遍历
{
if (p == NULL)
{
printf("NULL ");
return;
}
treebehind(p->left);
treebehind(p->right);
printf("%c ", p->val);
}
4.层序遍历！！(广度优先遍历)
层序遍历与以上三种遍历方式完全不同，他没有使用递归的思想，而是去使用了迭代的方法：
这里我们将使用我们先前学到的循环队列的数据结构去完成二叉树的层序遍历
逻辑如下：
运用队列的先进先出的特点
1.我们先塞入第一个根节点，
2.我们取出队列排头的节点的时候，自动往队列里面添加两个他的儿子节点
3.当队列里面为空的时候，我们就完成了一次层序遍历
接下来我们进行代码实现：
1.伪树
int main()
{
BinaryTree p1;
BinaryTree p2;
BinaryTree p3;
BinaryTree p4;
BinaryTree p5;
BinaryTree p6;
p1.left = &p2;
p1.right = &p3;
p2.left = NULL;
p2.right = &p4;
p3.left = &p5;
p3.right = NULL;
p4.left = NULL;
p4.right = &p6;
p6.left = NULL;
p6.right = NULL;
p5.left = NULL;
p5.right = NULL;
p1.val = 'A';
p2.val = 'B';
p3.val = 'C';
p4.val = 'D';
p5.val = 'E';
p6.val = 'F';
}
2.层序遍历
#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef BinaryTree* QueueDataType;
typedef struct CirQueue
{
QueueDataType* q;
int front;
int rear;
int capacity;
}CirQueue;
QueueDataType Cirqueuefront(CirQueue* p1)
{
return *((p1->q)+(p1->front));
}
CirQueue* CirQueueCreate(CirQueue* p,size_t x)
{
p = (CirQueue*)malloc(sizeof(CirQueue));
p->q = (QueueDataType*)(malloc(sizeof(QueueDataType) * x));
p->capacity = x;
p->front = 0;
p->rear = 0;
}
int isCirQueueEmpty(CirQueue* p)
{
if (p->front == p->rear)
{
return 1;
}
else
{
return 0;
}
}
int isCirQueueFull(CirQueue* p)
{
if ((p->rear+1) % p->capacity == p->front)
{
return 1;
}
else
{
return 0;
}
}
void CirQueuePop(CirQueue* p)
{
if (!isCirQueueEmpty(p))
{
p->front=(p->front+1)%p->capacity;
}
else
{
return;
}
}
void CirQueuePush(CirQueue* p,QueueDataType x)
{
if (isCirQueueFull(p))
{
return;
}
else
{
*(p->q + p->rear) = x;
p->rear = (p->rear + 1) % p->capacity;
}
}
void treeseq(BinaryTree* p)//层序遍历
{
CirQueue* que=NULL;
que = CirQueueCreate(que, 20);
CirQueuePush(que, p);
while (!isCirQueueEmpty(que))
{
if (Cirqueuefront(que) != NULL)
{
printf("%c ", Cirqueuefront(que)->val);
CirQueuePush(que, Cirqueuefront(que)->left);
CirQueuePush(que, Cirqueuefront(que)->right);
}
else
{
printf("NULL ");
}
CirQueuePop(que);
}
}
二.二叉树的leetcode小练习
1.判断平衡二叉树
平衡二叉树：当二叉树的每一个节点的两个子树的深度的差的绝对值小于1，则称为平衡二叉树。
1）正常解法
1.先创造求深度函数
int depthtree(struct TreeNode* root)
{
if(root==NULL)
{
return 0;
}
int leftdepth=depthtree(root->left);
int rightdepth=depthtree(root->right);
return 1+(leftdepth>rightdepth?leftdepth:rightdepth);
}
再通过分解子问题
求大树是否为平衡二叉树，我们先求解两个子树是不是平衡二叉树
bool isBalanced(struct TreeNode* root) {
if(root==NULL)
{
return true;
}
int left=depthtree(root->left);
int right=depthtree(root->right);
bool x=(left-right<=1)&&(left-right>=-1);
if(!x)
{
return false;
}
return isBalanced(root->left)&&isBalanced(root->right);
}
2）优化解法
刚刚的那种解法是一种低效的解法，通过前序遍历我们进行了很多次重复的计算。
所以我们考虑一下，是否可以使用后序遍历，
先快速来到底部，从底部向上走，而每一次的树的深度就可以直接将当前子树的高度++即可
bool _isBalanced(struct TreeNode* root,int* pdepth)
{
if(root==NULL)
{
return true;
}
int depth_left=0;
int depth_right=0;
if(!_isBalanced(root->left,&depth_left))
{
return false;
}
if(!_isBalanced(root->right,&depth_right))
{
return false;
}
if(abs(depth_right-depth_left)>1)
{
return false;
}
*pdepth=1+(depth_right>depth_left?depth_right:depth_left);
return true;
}
bool isBalanced(struct TreeNode* root) {
int depth=0;
return _isBalanced(root,&depth);
}
这样子我们只需要遍历n次，时间复杂度O(n)即可解决问题
2.对称二叉树
通过相反的遍历比较，可以得出是否为二叉树
bool issame(struct TreeNode* p1,struct TreeNode* p2)
{
if(p1==NULL&&p2==NULL)
{
return true;
}
else if((p1==NULL&&p2!=NULL)||(p1!=NULL&&p2==NULL))
{
return false;
}
return (p1->val==p2->val)&&issame(p1->left,p2->right)&&issame(p2->left,p1->right);
}
bool isSymmetric(struct TreeNode* root) {
if(root==NULL)
{
return true;
}
return issame(root->left,root->right);
}
ps：创作不易，恳请留一个赞吧