文章目录
前言
今天五一假期，学习了数据结构的二叉树相关内容，所以写这一篇博客来记录自己的学习内容，主要就是重点知识的梳理。
一、二叉树的链式存储
结构示意图：
逻辑结构：
二叉链和三叉链的结构设计：
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* left; // 指向当前节点左孩子
struct BinTreeNode* right; // 指向当前节点右孩子
BTDataType data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* parent; // 指向当前节点的双亲
struct BinTreeNode* left; // 指向当前节点左孩子
struct BinTreeNode* right; // 指向当前节点右孩子
BTDataType data; // 当前节点值域
}；
二、二叉树链式结构的实现
在学习二叉树的基本操作前，需要创建一棵二叉树，然后才能学习其相关的基本操作。为了降低学习成本，我们直接手动创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
而对于增删查改等功能，对于我们当前学习的二叉树并没有价值，所以我们的学习主要围绕遍历二叉树，或者计算节点或高度来进行。
二叉树的结构设计
此处我们使用的结构为 二叉链 的结构
typedef int BTDataType;
//二叉链
struct BinaryTreeNode
{
struct BinaryTreeNode* left; //指向当前节点的左孩子
struct BinaryTreeNode* right; //指向当前节点的右孩子
BTDataType data; //当前节点的值
}
手动构建二叉树
本篇博客 我构建了一颗简单的二叉树，如下图所示：
//创建节点
BTNode* BuyBTNode(BTDataType x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
void Test1()
{
// 构建二叉树
BTNode* n1 = BuyBTNode(1);
BTNode* n2 = BuyBTNode(2);
BTNode* n3 = BuyBTNode(3);
BTNode* n4 = BuyBTNode(4);
BTNode* n5 = BuyBTNode(5);
BTNode* n6 = BuyBTNode(6);
n1->left = n2;
n1->right = n4;
n2->left = n3;
n4->left = n5;
n4->right = n6;
}
二叉树的前序遍历
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。所以 前序遍历 又可以被称为 NLR。
前序遍历图解：
前序遍历的访问次序是 先访问根节点，再访问左子树，再访问右子树。
那么当前树的遍历结果为：1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL
前序遍历的代码实现：
void PreOrder(BTNode* root)
{
if(root == NULL)
{
printf("NULL ");
return;
}
printf("%d ",root->data);
PreOrder(root->left);
PreOrder(root->right);
}
二叉树的中序遍历
中序遍历 又可以被称为 LNR。
中序遍历的访问次序是 先访问左子树，再访问根节点，再访问右子树。
那么当前树的遍历结果为：NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL
中序遍历的代码实现：
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ",root->data);
InOrder(root->right);
}
二叉树的后序遍历
后序遍历 又可以被称为 LRN。
后序遍历的访问次序是 先访问左子树，再访问右子树，再访问根节点。
那么当前树的遍历结果为：NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1
后序遍历的代码实现：
void PostOrder(BTNode* root)
{
if(root==NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ",root->data);
}
二叉树的层序遍历
那么当前树的遍历结果为：1 2 4 3 5 6
计算二叉树大小
计算二叉树的大小，其实就是计算二叉树中 节点的个数
思路1的实现：
当size是局部变量的时候，显然是不可以的！我们遍历的过程还是递归，当每次递归的时候，都会建立新的函数栈帧，递归当中的size不是同一个size，每次递归时的size一开始都是0，无法成功计算出大小。
所以这时候，我们需要设置一个全局变量的size，但是size不会被销毁，所以每一次计算二叉树大小的时候，就要重新初始化size的大小为0，避免计算错误。
思路一的代码实现：
int size=0;
int TreeSize1(BTNode* root)
{
if (root==NULL)
{
return 0;
}
size++;
TreeSize1(root->left);
TreeSize1(root->right);
return size;
}
显然思路2正能解决这两个缺陷
如果访问节点为空，则返回0；如果访问节点不为空，则 +1返回，就这样分别递归左子树和右子树，最后的返回结果就是节点个数。
思路二的代码实现：
int TreeSize2(BTNode* root)
{
return root == NULL ? 0 : TreeSize2(root->left) + TreeSize2(root->right) + 1;
}
计算叶子节点个数
叶子节点，就是没有左右孩子的节点。
如果节点为空，那么不是叶子结点，返回0；如果左右孩子都为空，那么就是叶子结点，返回1。
最后分别递归计算左右子树的叶子结点。
int TreeLeafSize(BTNode* root)
{
if(root == NULL)
return 0;
if(root->left==NULL && root->right == NULL)
return 1;
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
计算二叉树高度
我们可以分别递归到左右子树的最后一层，如果当前节点为空，返回0；不为空则比较当前左右子树的高度，+1返回高度较高的一边。
在递归过程中使用 leftHeight 和 rightHeight 分别记录当前高度，防止重复递归调用。
计算二叉树高度代码的实现：
int TreeHeight(BTNode* root)
{
if(root==NULL)
{
return 0;
}
int leftHeight = TreeHeight(root->left);
int rightHeight = TreeHeight(root->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
计算第K层的节点个数
假设 k 足够大：
那么有了这个思路，我们就可以解决当前这个接口：
如果 当前节点为空，则返回0；
如果 节点不为空，且 k == 1，那么说明已经到达第 k 层，返回1；
如果 节点不为空，且 k > 1，那么说明需要继续递归，分别递归左右子树的 第 k - 1 层。
计算第K层的节点个数代码实现：
int TreeLevalSize(BTNode* root, int k)
{
if (root == NULL) return 0;
if (k == 1) return 1;
return TreeLevalSize(root->left, k - 1) + TreeLevalSize(root->right, k - 1);
}
查找某个值对应的节点
如果查找节点为空，则返回空；如果找到了则返回当前节点。
否则就分别递归查找左右子树，在查找过程中可以用变量来保存查找的值，如果查找返回的结果非空，那么说明找到了，就返回结果；如果左右子树都没有找到，则返回空。
BTNode* TreeFind(BTNode* root, int x)
{
// 如果 root 为空，则返回空
if (root == NULL)
{
return NULL;
}
// 找到了
if (root->data == x)
{
return root;
}
// 递归左右子树
BTNode* ret1 = TreeFind(root->left, x);
// 如果左子树非空，则找到了，返回
if (ret1 != NULL)
return ret1;
BTNode* ret2 = TreeFind(root->right, x);
if (ret2 != NULL)
return ret2;
// 到这里没找到，就得返回NULL
return NULL;
}
二叉树的销毁
销毁二叉树，我们使用 后序遍历 的思想销毁。
遍历到最后一层，先销毁左子树，再销毁右子树，如果遇到空指针，那么直接返回。
void TreeDestroy(BTNode* root)
{
if (root == NULL)
{
return;
}
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
}
这里我们需要注意一下，由于传的是一级指针，所以改变形参并不影响实参。在调用处销毁后需要 置空，防止误用。
三、完整代码
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
#include "Queue.h"
BTNode* BuyBTNode(BTDataType x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
// 前序遍历
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
// 二叉树中序遍历
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
// 二叉树后序遍历
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
// 计算二叉树大小
int size = 0;
int TreeSize1(BTNode* root)
{
if (root == NULL)
{
return 0;
}
size++;
TreeSize1(root->left);
TreeSize1(root->right);
return size;
}
int TreeSize2(BTNode* root)
{
return root == NULL ? 0 : TreeSize2(root->left) + TreeSize2(root->right) + 1;
}
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
int TreeHeight(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int leftHeight = TreeHeight(root->left);
int rightHeight = TreeHeight(root->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
// 层序遍历
//void LevelOrder(BTNode* root)
//{
// Queue q;
// QueueInit(&q);
//
// // 如果根非空，则入队列
// if (root != NULL)
// {
// QueuePush(&q, root);
// }
//
// // 队列非空则进行遍历
// while (!QueueEmpty(&q))
// {
// BTNode* front = QueueFront(&q);
// printf("%d ", front->data);
// QueuePop(&q);
//
// // 非空入队列
// if (front->left)
// {
// QueuePush(&q, front->left);
// }
//
// if (front->right)
// {
// QueuePush(&q, front->right);
// }
// }
//
// printf("\n");
// QueueDestroy(&q);
//}
// 控制一下层序遍历一层一层出
void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
// 如果根非空，则入队列
if (root != NULL)
{
QueuePush(&q, root);
}
// 算出每层的大小
int levelSize = QueueSize(&q);
// 不为空，则继续
while (!QueueEmpty(&q))
{
// 如果一层不为空，则继续出
while (levelSize--)
{
BTNode* front = QueueFront(&q);
printf("%d ", front->data);
QueuePop(&q);
// 非空入队列
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
printf("\n");
levelSize = QueueSize(&q);
}
printf("\n");
QueueDestroy(&q);
}
int TreeKLevelSize(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
if (k > 1)
{
return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1);
}
}
BTNode* TreeFind(BTNode* root, int x)
{
// 如果 root 为空，则返回空
if (root == NULL)
{
return NULL;
}
// 找到了
if (root->data == x)
{
return root;
}
// 否则递归左右子树
BTNode* ret1 = TreeFind(root->left, x);
// 如果左子树非空，则找到了，返回
if (ret1 != NULL)
return ret1;
BTNode* ret2 = TreeFind(root->right, x);
if (ret2 != NULL)
return ret2;
// 到这里没找到，就得返回NULL
return NULL;
}
// 判断二叉树是否是完全二叉树
bool TreeComplete(BTNode* root)
{
// 使用层序遍历思想
Queue q;
QueueInit(&q);
// 如果非空，则入队列
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
// 一旦出队列到空，就出去判断
if (front == NULL)
{
break;
}
else
{
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
if (front != NULL)
{
QueueDestroy(&q);
return false;
}
else
{
QueuePop(&q);
}
}
QueueDestroy(&q);
return true;
}
// 销毁
void TreeDestroy(BTNode* root)
{
if (root == NULL)
{
return;
}
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
}
void TestBTree1()
{
// 构建二叉树
BTNode* n1 = BuyBTNode(1);
BTNode* n2 = BuyBTNode(2);
BTNode* n3 = BuyBTNode(3);
BTNode* n4 = BuyBTNode(4);
BTNode* n5 = BuyBTNode(5);
BTNode* n6 = BuyBTNode(6);
n1->left = n2;
n1->right = n4;
n2->left = n3;
n4->left = n5;
n4->right = n6;
PreOrder(n1);
printf("\n");
InOrder(n1);
printf("\n");
PostOrder(n1);
printf("\n");
}
void TestBTree2()
{
// 构建二叉树
BTNode* n1 = BuyBTNode(1);
BTNode* n2 = BuyBTNode(2);
BTNode* n3 = BuyBTNode(3);
BTNode* n4 = BuyBTNode(4);
BTNode* n5 = BuyBTNode(5);
BTNode* n6 = BuyBTNode(6);
BTNode* n7 = BuyBTNode(7);
n1->left = n2;
n1->right = n4;
n2->left = n3;
n4->left = n5;
n4->right = n6;
n2->right = n7;
/*size = 0;
printf("%d\n", TreeSize1(n1));
size = 0;
printf("%d\n", TreeSize1(n1));
size = 0;
printf("%d\n", TreeSize1(n1));
printf("%d\n", TreeSize2(n1));
printf("%d\n", TreeLeafSize(n1));
printf("%d\n", TreeHeight(n1));
printf("%d\n", TreeKLevelSize(n1, 3));*/
printf("%d\n", TreeComplete(n1));
LevelOrder(n1);
TreeDestroy(n1);
n1 = NULL;
}
int main()
{
//TestBTree1();
TestBTree2();
return 0;
}