本节复习二叉树的增删查改， 二叉树的知识相对于前面的循序表， 链表， 以及栈和队列都要多一些。 同时二叉树的增删查改理解起来相对来说要困难一些。 本节来好好复习一下二叉树的增删查改。
目录
准备文件
创建结构体蓝图
二叉树的前序遍历
二叉树的后序遍历
二叉树的中序遍历
二叉树的节点个数
二叉树的叶子节点个数
二叉树的深度
判断二叉树是否为平衡二叉树
二叉树节点销毁
准备文件
首先准备好三个文件：
一个文件用于main.c调试， 一个文件用于二叉树函数的声明， 还有一个.c文件用于二叉树函数的实现。
创建结构体蓝图
首先包含一下头文件和重新定义一下我们要保存的数据类型。 这样做是为了便于维护我们的代码
///二叉树的增删查改/ #include<stdio.h> #include<stdlib.h> #include"Queue.h" #include<assert.h> typedef int TNDataType;然后创建结构体
///二叉树的增删查改/ #include<stdio.h> #include<stdlib.h> #include"Queue.h" #include<assert.h> typedef int TNDataType; typedef struct TreeNode { struct TreeNode* left; struct TreeNode* right; TNDataType data; }TNode;
二叉树的前序遍历
.h函数声明
///二叉树的增删查改/
#include<stdio.h>
#include<stdlib.h>
#include"Queue.h"
#include<assert.h>
typedef int TNDataType;
typedef struct TreeNode
{
struct TreeNode* left;
struct TreeNode* right;
TNDataType data;
}TNode;
///接口函数的声明///
//二叉树的前序遍历
void PrevOrder(TNode* root);
.c函数实现
//前序遍历
void PrevOrder(TNode* root)
{
if (root == NULL)
{
return;
}
printf("%d ", root->data);//每一个根节点都有左子树和右子树，这三行代码的意思是先访问根节点。
//然后访问左子树， 再访问右子树。然后访问左右子树的时候， 又先访问根节点， 再访问该子树的左右子树
PrevOrder(root->left);
PrevOrder(root->right);
}
二叉树的后序遍历
.h函数声明
///二叉树的增删查改/
#include<stdio.h>
#include<stdlib.h>
#include"Queue.h"
#include<assert.h>
typedef int TNDataType;
typedef struct TreeNode
{
struct TreeNode* left;
struct TreeNode* right;
TNDataType data;
}TNode;
///接口函数的声明///
//二叉树的前序遍历
void PrevOrder(TNode* root);
//二叉树的后序遍历
void PostOrder(TNode* root);.c函数实现
//后序遍历
void PostOrder(TNode* root)
{
if (root == NULL)
{
return;
}
PostOrder(root->left); //每一个根节点都有左右子树， 这三行代码的意思是先访问左右子树， 最后在访问根节点， 然后
//在访问每一棵左右子树的时候又先访问该子树的左右子树， 然后层层递归
PostOrder(root->right);
printf("%d ", root->data);
}
二叉树的中序遍历
.h函数声明
///二叉树的增删查改/
#include<stdio.h>
#include<stdlib.h>
#include"Queue.h"
#include<assert.h>
typedef int TNDataType;
typedef struct TreeNode
{
struct TreeNode* left;
struct TreeNode* right;
TNDataType data;
}TNode;
///接口函数的声明///
//二叉树的前序遍历
void PrevOrder(TNode* root);
//二叉树的后序遍历
void PostOrder(TNode* root);
//二叉树的中序遍历
void MidOrder(TNode* root);.c函数实现
//中序遍历
void MidOrder(TNode* root)
{
if (root == NULL)
{
return;
}
MidOrder(root->left); //在每一个根节点都有左右子树， 这三行代码的意思是先访问左子树，
//再访问根节点， 最后再访问右子树， 然后， 当访问左子树的时候， 左子树又有左子树， 就又访问
// 该子树的左子树， 直到遇到子树为空。
printf("%d ", root->data);
MidOrder(root->right);
}
二叉树的节点个数
.h函数声明
///二叉树的增删查改/
#include<stdio.h>
#include<stdlib.h>
#include"Queue.h"
#include<assert.h>
typedef int TNDataType;
typedef struct TreeNode
{
struct TreeNode* left;
struct TreeNode* right;
TNDataType data;
}TNode;
///接口函数的声明///
//二叉树的前序遍历
void PrevOrder(TNode* root);
//二叉树的后序遍历
void PostOrder(TNode* root);
//二叉树的中序遍历
void MidOrder(TNode* root);
//二叉树的层序遍历层序遍历
void LevelOrder(TNode* root);
//二叉树计算节点个数
int SumTree(TNode* root);.c函数实现
//二叉树计算节点个数
int SumTree(TNode* root)
{
if (root == NULL)//空节点代表着0个节点， 所以返回0个节点
{
return 0;
}
//代码走到这， 说明不是空节点， 不是空节点那么节点就应该加一
return SumTree(root->left) + SumTree(root->right) + 1;//节点加1， 同时遍历左右两棵子树。
}二叉树的叶子节点个数
.h函数声明
///二叉树的增删查改/
#include<stdio.h>
#include<stdlib.h>
#include"Queue.h"
#include<assert.h>
typedef int TNDataType;
typedef struct TreeNode
{
struct TreeNode* left;
struct TreeNode* right;
TNDataType data;
}TNode;
///接口函数的声明///
//二叉树的前序遍历
void PrevOrder(TNode* root);
//二叉树的后序遍历
void PostOrder(TNode* root);
//二叉树的中序遍历
void MidOrder(TNode* root);
//二叉树的层序遍历层序遍历
void LevelOrder(TNode* root);
//二叉树计算节点个数
int SumTree(TNode* root);
//二叉树计算叶子个数
int LeafSumTree(TNode* root);.c函数实现
//二叉树计算叶子个数
int LeafSumTree(TNode* root)
{
if (root->left == NULL && root->right == NULL)
{
return 1;
}
int left = LeafSumTree(root->left);//查看左子树
int right = LeafSumTree(root->right);//查看右子树, 为什么要用right？因为返回值带着计算的节点个数， 如果这两个递归函数
//不接收返回值， 那么就相当于只有遍历到叶子节点的时候返回节点，接收到叶子节点返回值
//的节点不能继续将值返回给父节点。
return left + right;
}二叉树的深度
.h函数声明
///二叉树的增删查改/
#include<stdio.h>
#include<stdlib.h>
#include"Queue.h"
#include<assert.h>
typedef int TNDataType;
typedef struct TreeNode
{
struct TreeNode* left;
struct TreeNode* right;
TNDataType data;
}TNode;
///接口函数的声明///
//二叉树的前序遍历
void PrevOrder(TNode* root);
//二叉树的后序遍历
void PostOrder(TNode* root);
//二叉树的中序遍历
void MidOrder(TNode* root);
//二叉树的层序遍历层序遍历
void LevelOrder(TNode* root);
//二叉树计算节点个数
int SumTree(TNode* root);
//二叉树计算叶子个数
int LeafSumTree(TNode* root);
//二叉树的深度
int TallTree(TNode* root);.c函数实现
//计算树的深度
int TallTree(TNode* root) //计算树的深度的核心就是左右子树哪个高， 在他的基础上加1。
{
if (root == NULL)
{
return 0;
}
//
int left = TallTree(root->left);
int right = TallTree(root->right);
return (left > right) ? (left + 1) : (right + 1);
}
判断二叉树是否为平衡二叉树
.h函数声明
///二叉树的增删查改/
#include<stdio.h>
#include<stdlib.h>
#include"Queue.h"
#include<assert.h>
typedef int TNDataType;
typedef struct TreeNode
{
struct TreeNode* left;
struct TreeNode* right;
TNDataType data;
}TNode;
///接口函数的声明///
//二叉树的前序遍历
void PrevOrder(TNode* root);
//二叉树的后序遍历
void PostOrder(TNode* root);
//二叉树的中序遍历
void MidOrder(TNode* root);
//二叉树的层序遍历层序遍历
void LevelOrder(TNode* root);
//二叉树计算节点个数
int SumTree(TNode* root);
//二叉树计算叶子个数
int LeafSumTree(TNode* root);
//二叉树的深度
int TallTree(TNode* root);
//判断是否为平衡二叉树
bool TreeEqual(TNode* root);.c函数实现
//计算树的深度
int TallTree(TNode* root) //计算树的深度的核心就是左右子树哪个高， 在他的基础上加1。
{
if (root == NULL)
{
return 0;
}
//
int left = TallTree(root->left);
int right = TallTree(root->right);
return (left > right) ? (left + 1) : (right + 1);
}
二叉树节点销毁
.h函数声明
///二叉树的增删查改/
#include<stdio.h>
#include<stdlib.h>
#include"Queue.h"
#include<assert.h>
typedef int TNDataType;
typedef struct TreeNode
{
struct TreeNode* left;
struct TreeNode* right;
TNDataType data;
}TNode;
///接口函数的声明///
//二叉树的前序遍历
void PrevOrder(TNode* root);
//二叉树的后序遍历
void PostOrder(TNode* root);
//二叉树的中序遍历
void MidOrder(TNode* root);
//二叉树的层序遍历层序遍历
void LevelOrder(TNode* root);
//二叉树计算节点个数
int SumTree(TNode* root);
//二叉树计算叶子个数
int LeafSumTree(TNode* root);
//二叉树的深度
int TallTree(TNode* root);
//判断是否为平衡二叉树
bool TreeEqual(TNode* root);
//二叉树销毁
void TreeDestroy(TNode* root);.c函数实现
//二叉树的销毁
void TreeDestroy(TNode* root) //二叉树的销毁应该是一个后序遍历
{
if (root->left == NULL && root->right == NULL)
{
free(root);
root = NULL;
return;
}
else
{
if (root->left != NULL)
{
TreeDestroy(root->left);
}
else if (root->right != NULL)
{
TreeDestroy(root->right);
}
}
}
