数据结构 二叉树篇之链式存储结构（二）

���录

（）

前言

一、链式存储结构

（）

二、链式二叉树的基本功能

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);}

---

总结

        本章数据结构二叉树的内容已经完结了，下一章会讲到数据结构的各种排序，以及排序的基础概念，感谢大家看到这里喔。