数据结构—二叉树的模拟实现（c语言）

目录

一.前言

二.模拟实现链式结构的二叉树

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 ;//一开始就是 xif (root->data == x){return root;}//前序遍历寻找xnode = 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);
}