数据结构 二叉树篇之链式存储结构（二）
���录
（）前言
一、链式存储结构
（）二、链式二叉树的基本功能
1.通过前序建立一个链式二叉树
2.二叉树前中后序遍历
2.1前序遍历
2.2中序遍历
2.3后序遍历
3.求二叉树的节点个数
4.求二叉树叶子节点个数
5.求二叉树第k层节点个数
6.求二叉树的高度
7.二叉树的层序遍历
8.判断二叉树是否是完全二叉树
三、源代码
总结
前言
上一章我们讲了二叉树的顺序存储的结构，接下来本章会将二叉树链式存储的结构和功能全部讲解完，这样二叉树的章节就完结啦，希望大家能学会以及理解喔。
一、链式存储结构
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。那么链式的二叉树的结构体是什么样子的呢？具体代码如下：
typedef char BTDatatype;
typedef struct BinaryTreeNode {
BTDatatype val;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
之前我们就讲了二叉树是由左右孩子节点结合而成的一颗二叉树，所有在创建结构体时，我们要准备好两个节点，方便连接起来。
二、链式二叉树的基本功能
1.通过前序建立一个链式二叉树
我们创建好之后就要建立一个二叉树了，那么该如何建立呢？这里需要先学习了前序遍历才能理解前序建立二叉树，这里就大概讲解，我们有一个前序遍历然后生成一颗二叉树，节点内容用字母表示，空节点用 # 表示：
char arr[] = "ABD##E#H##CF##G##";
准备好一个数组之后，就开始遍历生成了，具体步骤因为需要遍历，所有我们要想好终止条件，1.当 arr 数组遍历完后或为空时我们就要返回结束该遍历，2.当遇到 # 时，表示该节点为空节点我们要返回空，继续后面的代码，具体如下：
BTNode* BinaryTreeCreate(BTDatatype* arr, int arr_size, int* start) {
if (arr == NULL || arr_size val = arr[*start];
(*start)++;
newnode->left = BinaryTreeCreate(arr, arr_size, start);
newnode->right = BinaryTreeCreate(arr, arr_size, start);
return newnode;
}
这里的 *start 是用来控制数组的插入位置，因为如果在函数里创建一个变量控制数组位置，进入下一个函数时，虽然变量带进去了也发生改变了，但是当他返回时，变量的数据是上一个空间的数据，不符合我们的需求，所以得使用外部传进来的 *start 进行改变。
2.二叉树前中后序遍历
二叉树的遍历分别由前中后序，每种遍历都有不同的要求，下面会给大家讲解三个不同的遍历。
2.1前序遍历
首先是前序遍历，也叫先序遍历，该遍历是中左右的顺序进行遍历，什么意思呢？就是头节点->左节点->右节点的顺序进行遍历生成：
void BinaryTreePrevOrder(BTNode* pheap) {
if (!pheap) {
printf("# ");
return;
}
printf("%c ", pheap->val);
BinaryTreePrevOrder(pheap->left);
BinaryTreePrevOrder(pheap->right);
}
2.2中序遍历
中序遍历跟前序遍历的思路大致一样，区别在于是左中右的循序遍历：
void BinaryTreeInOrder(BTNode* pheap) {
if (!pheap) {
printf("# ");
return;
}
BinaryTreeInOrder(pheap->left);
printf("%c ", pheap->val);
BinaryTreeInOrder(pheap->right);
}
2.3后序遍历
后序遍历的顺序是左右中循序遍历：
void BinaryTreePostOrder(BTNode* pheap) {
if (!pheap) {
printf("# ");
return;
}
BinaryTreePostOrder(pheap->left);
BinaryTreePostOrder(pheap->right);
printf("%c ", pheap->val);
}
三个遍历会发现，只是打印的位置有些调整就发生了三种不同的遍历顺序，所以要控制好代码的位置，不然就实现不出想要的功能了。
3.求二叉树的节点个数
求二叉树的节点个数方式很多，这是其中一种快捷的方法，还是要思考一下，就能理解了。
int BinaryTreeSize(BTNode* pheap) {
if (pheap == NULL)
return 0;
return BinaryTreeSize(pheap->left) + BinaryTreeSize(pheap->right) + 1;
}
4.求二叉树叶子节点个数
求二叉树的叶子节点个数就稍微要转变一下了，要当左节点为空右节点也为空时，才能说明该节点是空节点，才能返回1回去。
int BinaryTreeLeafSize(BTNode* pheap) {
if (pheap == NULL)
return 0;
if (!pheap->left && !pheap->right)
return 1;
return BinaryTreeLeafSize(pheap->left) + BinaryTreeLeafSize(pheap->right);
}
5.求二叉树第k层节点个数
求二叉树第k层的节点个数，就需要想到第k层的最后一层就是我们需要的节点个数，那么只需要将k的数减到k为1时，就是第k层的节点个数了，具体代码如下：
int BinaryTreeLevelKSize(BTNode* pheap, int k) {
assert(k > 0);
if (pheap == NULL)
return 0;
if (k == 1)
return 1;
return BinaryTreeLevelKSize(pheap->left, k - 1) + BinaryTreeLevelKSize(pheap->right, k - 1);
}
6.求二叉树的高度
求二叉树的高度时，我们需要判断一下，左子树高还是右子树高，哪个子树高我们就返回哪个子树的高度，这里要记得 +1 因为也要算是根节点。
int BinaryTreeHeight(BTNode* pheap) {
int left_h = 0, right_h = 0;
if (pheap == NULL)
return 0;
left_h = BinaryTreeHeight(pheap->left);
right_h = BinaryTreeHeight(pheap->right);
return left_h > right_h ? left_h + 1 : right_h + 1;
}
7.二叉树的层序遍历
我们需要求二叉树的层序遍历的时候我们要用是 栈或者队列去实现这功能，这里我用的是队列去实现，具体步骤思路是，先将跟节点 push 进去，当队列不为空时，我们创建一个节点用于保存即将pop的节点，在将保存的节点的左右孩子节点都push进队列，重复以上步骤即可。
void BinaryTreeLevelOrder(BTNode* root) {
Queue p;
QListInit(&p);
printf("\n");
if (root)
QListPush(&p, root);
int LeaveSize = 1;
while (!(QueueEmpty(&p))) {
while (LeaveSize--) {
BTNode* front = QueueFront(&p);
QListPop(&p);
printf("%c ", front->val);
if (front->left)
QListPush(&p, front->left);
if (front->right)
QListPush(&p, front->right);
}
printf("\n");
LeaveSize = QueueSize(&p);
}
QListDestory(&p);
}
8.判断二叉树是否是完全二叉树
当我们要判断一颗二叉树是否为完全二叉树时，我们可以用上刚刚的层序遍历去实现，当传进了一个NULL节点，但是后面还有元素，说明该树不是完全二叉树了，这样就可以完成判断了。
bool BinaryTreeComplete(BTNode* root) {
Queue p;
QListInit(&p);
printf("\n");
if (root)
QListPush(&p, root);
while (!(QueueEmpty(&p))) {
BTNode* front = QueueFront(&p);
QListPop(&p);
if (front == NULL)
break;
QListPush(&p, front->left);
QListPush(&p, front->right);
}
while (!QueueEmpty(&p)) {
BTNode* front = QueueFront(&p);
QListPop(&p);
if (front) {
QListDestory(&p);
return false;
}
}
QListDestory(&p);
return true;
}
三、源代码
BinaryTree.h
#pragma once
#include
#include
#include
#include
typedef char BTDatatype;
typedef struct BinaryTreeNode {
BTDatatype val;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
//通过前序遍历数组数据生成二叉树
BTNode* BinaryTreeCreate(BTDatatype* arr, int arr_size ,int *p);
//二叉树节点个数
int BinaryTreeSize(BTNode* pheap);
//二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* pheap);
//二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* pheap, int k);
//二叉树的高度
int BinaryTreeHeight(BTNode* pheap);
//查找值为x的节点
BTNode* BinaryTreeFindNode(BTNode* pheap, BTDatatype x);
//二叉树前序遍历
void BinaryTreePrevOrder(BTNode* pheap);
//二叉树中序遍历
void BinaryTreeInOrder(BTNode* pheap);
//二叉树后序遍历
void BinaryTreePostOrder(BTNode* pheap);
//层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
//销毁二叉树
void BinaryTreeDestory(BTNode** pheap);
BinaryTree.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
#include "BinaryTree.h"
//通过前序遍历数据生成二叉树
BTNode* BinaryTreeCreate(BTDatatype* arr, int arr_size, int* start) {
if (arr == NULL || arr_size val = arr[*start];
(*start)++;
newnode->left = BinaryTreeCreate(arr, arr_size, start);
newnode->right = BinaryTreeCreate(arr, arr_size, start);
return newnode;
}
//二叉树节点个数
int BinaryTreeSize(BTNode* pheap) {
if (pheap == NULL)
return 0;
return BinaryTreeSize(pheap->left) + BinaryTreeSize(pheap->right) + 1;
}
//二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* pheap) {
if (pheap == NULL)
return 0;
if (!pheap->left && !pheap->right)
return 1;
return BinaryTreeLeafSize(pheap->left) + BinaryTreeLeafSize(pheap->right);
}
//二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* pheap, int k) {
assert(k > 0);
if (pheap == NULL)
return 0;
if (k == 1)
return 1;
return BinaryTreeLevelKSize(pheap->left, k - 1) + BinaryTreeLevelKSize(pheap->right, k - 1);
}
//二叉树的高度
int BinaryTreeHeight(BTNode* pheap) {
int left_h = 0, right_h = 0;
if (pheap == NULL)
return 0;
left_h = BinaryTreeHeight(pheap->left);
right_h = BinaryTreeHeight(pheap->right);
return left_h > right_h ? left_h + 1 : right_h + 1;
}
//查找值为x的节点
BTNode* BinaryTreeFindNode(BTNode* pheap, BTDatatype x) {
BTNode* p = NULL;
if (pheap == NULL)
return NULL;
if (pheap->val == x)
return pheap;
p = BinaryTreeFindNode(pheap -> left, x);
if (p != NULL)
return p;
p = BinaryTreeFindNode(pheap->right, x);
if (p != NULL)
return p;
}
//二叉树前序遍历
void BinaryTreePrevOrder(BTNode* pheap) {
if (!pheap) {
printf("# ");
return;
}
printf("%c ", pheap->val);
BinaryTreePrevOrder(pheap->left);
BinaryTreePrevOrder(pheap->right);
}
//二叉树中序遍历
void BinaryTreeInOrder(BTNode* pheap) {
if (!pheap) {
printf("# ");
return;
}
BinaryTreeInOrder(pheap->left);
printf("%c ", pheap->val);
BinaryTreeInOrder(pheap->right);
}
//二叉树后序遍历
void BinaryTreePostOrder(BTNode* pheap) {
if (!pheap) {
printf("# ");
return;
}
BinaryTreePostOrder(pheap->left);
BinaryTreePostOrder(pheap->right);
printf("%c ", pheap->val);
}
//层序遍历
void BinaryTreeLevelOrder(BTNode* root) {
Queue p;
QListInit(&p);
printf("\n");
if (root)
QListPush(&p, root);
int LeaveSize = 1;
while (!(QueueEmpty(&p))) {
while (LeaveSize--) {
BTNode* front = QueueFront(&p);
QListPop(&p);
printf("%c ", front->val);
if (front->left)
QListPush(&p, front->left);
if (front->right)
QListPush(&p, front->right);
}
printf("\n");
LeaveSize = QueueSize(&p);
}
QListDestory(&p);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root) {
Queue p;
QListInit(&p);
printf("\n");
if (root)
QListPush(&p, root);
while (!(QueueEmpty(&p))) {
BTNode* front = QueueFront(&p);
QListPop(&p);
if (front == NULL)
break;
QListPush(&p, front->left);
QListPush(&p, front->right);
}
while (!QueueEmpty(&p)) {
BTNode* front = QueueFront(&p);
QListPop(&p);
if (front) {
QListDestory(&p);
return false;
}
}
QListDestory(&p);
return true;
}
//销毁二叉树
void BinaryTreeDestory(BTNode** pheap) {
if ((*pheap) == NULL) {
return;
}
BinaryTreeDestory(&(*pheap)->left);
BinaryTreeDestory(&(*pheap)->right);
free(*pheap);
*pheap = NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
#include "BinaryTree.h"
int main() {
char arr[] = "ABD##E#H##CF##G##";
int start = 0;
BTNode* phead = BinaryTreeCreate(arr, sizeof(arr) / sizeof(arr[0]),&start);
printf("TreeSize = %d\n", BinaryTreeSize(phead));
printf("TreeLeafSize = %d\n", BinaryTreeLeafSize(phead));
printf("TreeLevelKSize = %d\n", BinaryTreeLevelKSize(phead, 2));
printf("TreeHeight = %d\n", BinaryTreeHeight(phead));
BTNode* FineNode = BinaryTreeFindNode(phead, 'C');
assert(FineNode);
printf("FineNode : %p \n", FineNode);
printf("TreePrevOrder:");
BinaryTreePrevOrder(phead);
printf("\n");
printf("TreeINOrder:");
BinaryTreeInOrder(phead);
printf("\n");
printf("TreePostOrder:");
BinaryTreePostOrder(phead);
printf("\n");
printf("TreeLevelOrder:");
BinaryTreeLevelOrder(phead);
printf("TreeComplete:%d", BinaryTreeComplete(phead));
printf("\n");
BinaryTreeDestory(&phead);
}
总结
本章数据结构二叉树的内容已经完结了，下一章会讲到数据结构的各种排序，以及排序的基础概念，感谢大家看到这里喔。
The End