【数据结构第十六节】实现链式结构二叉树（详细递归图解—呕心沥血版！）

必须有为成功付出代价的决心，然后想办法付出这个代价。云边有个稻草人-CSDN博客

这节课挺抽象（苦笑），没事，我会帮你！干就完了！

（目录在路上）

正文开始——

引言

用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点有三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在链结点的存储地址，结构见下：

//创建链式结构二叉树的结构->二叉链
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType* data;struct BinaryTreeNode* left;//指定当前结点的左孩子struct BinaryTreeNode* right;//指定当前结点的右孩子
}BTNode;

二叉树的创建方式比较复杂，为了更好地步入到二叉树内容中，我们先手动创建一棵链式二叉树。

//申请结点
BTNode* BuyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc faile!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}BTNode* CreateTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);//改变指针指向，使其成为一棵链式二叉树node1->left = node2;node1->right = node3;node2->left = node4;return node1;}

回顾二叉树的概念，二叉树分为空树和非空二叉树，非空二叉树由根节点、根节点的左子树和根节点的右子树组成的。

根节点的左子树和右子树分别又是由子树节点、子树结点的左子树和子树结点的右子树组成的，因此二叉树是递归式的，后序链式二叉树的操作基本都是按照概念实现的。

一、前中后序遍历

1.1 遍历规则

按照规则，二叉树的遍历有：前序 /中序/ 后序的遍历结构：

前序遍历（Preorder Traversal 亦称先序遍历）：访问根结点的操作发生在遍历其左右子树之前，访问的顺序：根节点、左子树、右子树
中序遍历（Inorder Traversal）：访问根节点的操作发生在遍历其左右子树之间，访问顺序：左子树、根节点、右子树
后序遍历（Postorder Traversal）：访问根节点的操作发生在遍历其左右子树之后，访问顺序：左子树、右子树、根节点

1.2 代码实现

（1）前序遍历

//前序遍历
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}

该图里面，前序遍历结果为：1 2 4 3

（2）中序遍历

//中序遍历--左根右
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

中序遍历结果为：4 2 1 3

（3）后序遍历

//后序遍历--左右根
void PosOrder(BTNode* root)
{if (root == NULL){return;}PosOrder(root->left);PosOrder(root->right);printf("%d ", root->data);
}

二、结点个数以及高度等

2.1 二叉树结点个数

//求二叉树节点的个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

2.2 二叉树叶子结点的个数

//二叉树叶子结点个数
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.3 二叉树第K层结点的个数

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

2.4 求二叉树的高度/深度

//求二叉树高度/深度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}

2.5 二叉树查找值为x的节点

//二叉树找值为x的结点
BTNode* BinaryFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryFind(root->right, x);if (rightFind){return rightFind;}return NULL;
}

2.6 二叉树的销毁

//二叉树的销毁
void BinaryTreeDestroy(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestroy(&((*root)->left));//注意这里的传参，传的是地址BinaryTreeDestroy(&((*root)->right));free(*root);*root = NULL;
}

三、层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对⼆叉树进行层序遍历。设⼆叉树的根结点所在层数为1，层序遍历就是从所在⼆叉树的根结点出发，⾸先访问第⼀层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点， 以此类推，⾃上⽽下，⾃左⾄右逐层访问树的结点的过程就是层序遍历。

我们要提前实现一个队列的结构，（1）在下面的函数里面我们创建一个队列，并且别忘记队列的初始化和销毁，（2）同时要注意，我们前面学习的队列里面的数据是整型类型，这次我们要将结点插入到队列里面，所以我们要将队列里面的数据类型改为二叉树节点的类型，并且我们不能直接写二叉树节点的缩写那样，我们要写成 struct BinaryTreeNode* / struct BTNode* ，反正都不能少 struct，不然会报错。（3）还有一点，在我们的层序遍历代码里面当while循环结束的时候队列为NULL，下一步再进行队列的销毁的时候就会报错，因为我们前面实现的队列的销毁里面队列为空时不能销毁，所以assert会报错，所以我们可以把队列的销毁里面判断队列是否为空的那一步给注释掉。

提及到的代码需要注意的点都在下面，多看看！

//创建节点的结构
typedef struct BinaryTreeNode* QUDatatype;//这里需要注意
typedef struct QueueNode
{QUDatatype data;struct QueueNode* next;
}QueueNode;

//销毁
void QueueDestroy(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));//往这看，注释掉这里也没事，就算队列为空也没关系//此时pcur为NULL，进不去循环QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

//层序遍历
void LevelBinaryTree(BTNode* root)
{//先创建一个队列Queue q;QueueInit(&q);//取根节点入队列QueuePush(&q, root);while (!QueueEmpty(&q)){//打印队头数据BTNode* Front = QueueFront(&q);printf("%d ", Front->data);QueuePop(&Front);if (Front->left){QueuePush(&q, Front->left);}if (Front->right){QueuePush(&q, Front->right);}}QueueDestroy(&q);
}

四、判断是否是完全二叉树

//判断是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q,root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);//保证下次是最新的队头if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}//队列不一定为空while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

【图解】

五、本节课代码汇总

Queue.h

#pragma once
#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//创建节点的结构
typedef struct BinaryTreeNode* QUDatatype;
typedef struct QueueNode
{QUDatatype data;struct QueueNode* next;
}QueueNode;//创建队列的结构
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);//入队列
void QueuePush(Queue* pq,QUDatatype x);//判空
bool QueueEmpty(Queue* pq);//出队列
void QueuePop(Queue* pq);//取队头数据
QUDatatype QueueTop(Queue* pq);//去队尾数据
QUDatatype QueueBack(Queue* pq);//去队列中有效数据的个数
int QueueSize(Queue* pq);//销毁
void QueueDestroy(Queue* pq);

Queue.c

#include"Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//入队列
void QueuePush(Queue* pq, QUDatatype x)
{assert(pq);//现申请新的结点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//如果为空if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* pcur = pq->phead->next;free(pq->phead);pq->phead = pcur;}pq->size--;
}//取队头数据
QUDatatype QueueTop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;}//去队尾数据
QUDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}int QueueSize(Queue* pq)
{assert(pq);/*QueueNode* pcur = pq->phead;int count = 0;while (pcur){count++;QueuePop(pq);pcur = pq->phead;}*//*return count;*/return pq->size;
}//销毁
void QueueDestroy(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

Tree.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//创建链式结构二叉树的结构->二叉链
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;//指定当前节点的左孩子struct BinaryTreeNode* right;//指定当前节点的右孩子
}BTNode;//申请节点
BTNode* BuyNode(BTDataType x);//前序遍历
void PreOrder(BTNode* root);//中序遍历
void InOrder(BTNode* root);//后序遍历
void PosOrder(BTNode* root);//求二叉树节点的个数
int BinaryTreeSize(BTNode* root);//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);//第K层节点个数
int BinaryTreeLevelKSize(BTNode* root,int k);//求二叉树高度/深度
int BinaryTreeDepth(BTNode* root);//找X的结点
BTNode* BinaryFind(BTNode* root, BTDataType x);//二叉树的销毁
void BinaryTreeDestroy(BTNode** root);//层序遍历
void LevelBinaryTree(BTNode* root);//判断是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);

Tree.c

#include"Tree.h"
#include"Queue.h"//申请节点
BTNode* BuyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc faile!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}//前序遍历-
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}//中序遍历--左根右
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
} //后序遍历--左右根
void PosOrder(BTNode* root)
{if (root == NULL){return;}PosOrder(root->left);PosOrder(root->right);printf("%d ", root->data);
}//求二叉树节点的个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}//二叉树叶子结点个数
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);
}//第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);
}//求二叉树高度/深度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}//二叉树找值为x的结点
BTNode* BinaryFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryFind(root->right, x);if (rightFind){return rightFind;}return NULL;
}//二叉树的销毁
void BinaryTreeDestroy(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestroy(&((*root)->left));BinaryTreeDestroy(&((*root)->right));free(*root);*root = NULL;
}//层序遍历
void LevelBinaryTree(BTNode* root)
{//先创建一个队列Queue q;QueueInit(&q);//取根节点入队列QueuePush(&q, root);while (!QueueEmpty(&q)){//打印队头数据BTNode* Front = QueueFront(&q);printf("%d ", Front->data);QueuePop(&Front);if (Front->left){QueuePush(&q, Front->left);}if (Front->right){QueuePush(&q, Front->right);}}QueueDestroy(&q);
}//判断是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q,root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}//队列不为空while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

test.c

#include"Tree.h"BTNode* CreateTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);node1->left = node2;node1->right = node3;node2->left = node4;return node1;}int main()
{BTNode* node = CreateTree();/*PreOrder(node);printf("\n");InOrder(node);printf("\n");PosOrder(node);*/printf("NodeSize:%d\n", BinaryTreeSize(node));printf("NodeSize:%d\n", BinaryTreeSize(node));printf("NodeSize:%d\n", BinaryTreeSize(node));printf("LeafSize：%d\n", BinaryTreeLeafSize(node));printf("%d\n", BinaryTreeLevelKSize(node, 3));printf("%d\n", BinaryTreeDepth(node));BTNode* find = BinaryFind(node, 22);printf("%s\n", find == NULL ? "没找到\n" : "找到了！\n");LevelBinaryTree(node);bool ret = BinaryTreeComplete(node);printf("%s\n", ret == false ? "不是完全二叉树\n" : "是完全二叉树\n");BinaryTreeDestroy(&node);return 0;
}

我感觉这节递归还是挺难理解的，感觉函数递归进行的过程不好想象，层层递归就比较难以理解透彻，我会忘记自己递归到那个地方了绕不回去了就很烧脑筋，难想的时候呢我就得画出函数进行栈帧的创建与销毁，这样一步一步来还是比较好的。对了，我画的红箭头还有绿箭头可以看成是函数栈帧的创建与销毁。把详细的函数的栈帧的创建与销毁多想几遍函数的递归应该就会好想象一点了。这节课我啃了两天了，后续还得多回顾理解多敲代码，告诉自己，别畏难，很难，但也得一步一步走下去，总不能放弃吧，那就坚定不移的前进！（这节课的博客真难写呀啊啊啊——）

知识点有不对的地方还请多多指教（抱拳）

完——