目录
一.前言
二.模拟实现链式结构的二叉树
2.1二叉树的底层结构
2.2通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
2.3二叉树的销毁
2.4二叉树查找值为x的节点
2.5二叉树节点个数
2.6二叉树叶子节点个数
2.7二叉树第k层节点个数
三.二叉树的遍历
3.1前序遍历
3.2中序遍历
3.3后序遍历
3.4层序遍历
一.前言
详解—数据结构《树和二叉树》-CSDN博客
上一节课我们详解了树和二叉树，这一篇博客我来带领大家来模拟实现二叉树
二.模拟实现链式结构的二叉树
2.1二叉树的底层结构
首先，有一个数据域
然后有俩个二叉树指针，分别指向他们的左孩子和右孩子
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;2.2通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
1、按照前序遍历（先走根，再走左子树，再走右子树）的方法，我们首先了解大概思路
2、数组里面的#就相当于为空，所以，我们先判断if 我们的数组为#，就返回空
3、然后我们创建一个节点，如果开辟失败，返回空，我们进行判断
4、然后放入数据，
5、再然后递归开始走左子树，右子树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int * pi)
{
if ('#' == a[*pi])
{
++(*pi);
return NULL;
}
BTNode * root = (BTNode *)malloc (sizeof(BTNode));
if (root == NULL)
{
perror("malloc");
return;
}
root->data = a[(*pi)++];
root->left = BinaryTreeCreate(a, n, pi);
root->right = BinaryTreeCreate(a, n, pi);
return root;
}
2.3二叉树的销毁
销毁一颗二叉树
1.首先判断如果是空树，直接返回
2.利用递归从最左边的树开始进行一个节点一个节点的删除
void BinaryTreeDestory(BTNode** root)
{
if (*root == NULL)
return;
BinaryTreeDestory((*root)->left);
BinaryTreeDestory((*root)->right);
free(*root);
*root = NULL;
}
2.4二叉树查找值为x的节点
二叉树的查找在这里我用的前序遍历递归
1.先确定递归的退出条件，root等于空就返回
2.然后进行前序遍历
3.判断一下当前节点是不是x
4.在开始走左子树
5.开始走右子树
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
BTNode* node;
if (root == NULL)
return NULL ;
//一开始就是 x
if (root->data == x)
{
return root;
}
//前序遍历寻找x
node = BinaryTreeFind(root->left, x);
if (node)
return node;
node =BinaryTreeFind(root->right, x);
if (node)
return node;
//遍历完找不到返回空
return NULL;
}
2.5二叉树节点个数
二叉树的节点个数就是二叉树，左子树加上右子树加上根
这里我用的也是递归的方法，同学们可以看一下
int BinaryTreeSize(BTNode* root)
{
return root == NULL ? 0 : BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right) + 1;
}2.6二叉树叶子节点个数
叶节点或终端节点：度为0的节点称为叶节点；
可以观看上一篇文章取了解叶子节点
详解—数据结构《树和二叉树》-CSDN博客
查找叶子节点，也是用的递归方法，
首先，增加递归退出条件root==0
然后，如果所在的节点他的左右子树都为空，那么他就是叶子节点，返回1
最后递归遍历所有的叶子节点进行相加
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);
}2.7二叉树第k层节点个数
在二叉树中我们想知道，每一层有多少个节点
1.确定递归退出条件
2.如果k=1，返回1，代表找到了这一层的一个节点
3.进行递归，每一层k-1，当k=1是找到所在k层，返回一，进行相加查找当前层数据
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BinaryTreeLevelKSize(root->left, k - 1) +
BinaryTreeLevelKSize(root->right, k - 1);
}三.二叉树的遍历
3.1前序遍历
二叉树的遍历了解可以详细看看上一章节
详解—数据结构《树和二叉树》-CSDN博客
前序遍历的遍历方法，就是先走根然后左子树，右子树
我们这里还是用的递归
1.先确定递归条件
2.打印当前节点
3.走左子树
4.走右子树
void BinaryTreePrevOrder(BTNode * root)
{
if (root == NULL)
{
return;
}
printf("%c ", root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}3.2中序遍历
中序遍历的顺序是先走左子树，再走根，再走右子树
我们的实现方法如下：
1.确定递归条件
2.走左子树
3.打印当前节点
4.走右子树
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreeInOrder(root->left);
printf("%c ", root->data);
BinaryTreeInOrder(root->right);
}3.3后序遍历
后序遍历的顺序是先走左子树，再走右子树，再走根
我们的实现方法如下：
1.确定递归条件
2.走左子树
3.走右子树
4.打印当前节点
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%c ", root->data);
}3.4层序遍历
首先，我们层序遍历，需要用到队列，我们先添加前几章写的队列到当前项目中，然后进行调用
1.创建并初始化一个队列
2.当根不为空时，将根节点入队，
3.保存根节点地址，访问其数据域，之后出队；
4.若根节点的左子树不为空，入队左子树，
5.判断根节点的右子树不为空，入队右子树，
6.保存队头节点地址，访问其数据域，之后出队；
8.重复上述过程的条件是队列不为空
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
//初始化队列
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
printf("%c ", front->data);
QueuePop(&q);
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
printf("\n");
//销毁队列
QueueDestroy(&q);
}
