【C语言】二叉树的实现

前言

在学习二叉树实现时，我们首先要对二叉树基本认识有一定的了解，下面我总结了以下几点有关二叉树的性质以及特点：
🎈每一个节点最多有两棵子树，不存在度大于2的节点。
🎈左右子树是有顺序的，其次序不能颠倒。
🎈二叉树一般有四种形态，分别为：空二叉树，只有一个根节点，根结点只有左子树和根节点只有右子树。
🎈二叉树常用的三种性质：1)二叉树的第 i 层上最多有2 ^ (i - 1)个节点；
2)深度为K的二叉树最多有2 ^ (k - 1)个节点。
3)度为0的节点个数比度为2的节点个数多一个。

⭐一、二叉树的定义

二叉树通常以结构体的形式定义，其结构体内容包括三部分：本节点所存储的值、左孩子节点的指针以及右孩子节点的指针。这里需要注意，子节点必须使用指针，就像我们定义结构体链表一样，下一个节点必须使用地址的方式存在在结构体当中。

typedef int BTDateType;typedef struct BinaryTreeNode
{BTDateType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

🚲二、创建二叉树

当我们对二叉树的掌握还不够深入时，我们也可以创建一棵简单的二叉树，减少时间成本。

// 手搓一个二叉树
BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;
}BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}

而真正的二叉树创建的过程是这样的：首先给出一个数组，将要创建的元素放在数组里。然后通过遍历（前 或 中 或 后序遍历）的顺序访问并创建二叉树每个节点，最后返回根节点的地址即创建完成。
我们假设通过前序序列的方式访问并创建二叉树：

// 创建树,按前序遍历的顺序
BTNode* BinaryTreeCreate(BTDateType* a, int* pi) {if (a[*pi] != '#') // '#'代表叶子结点{BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->data = a[*pi];(*pi)++;root->left = BinaryTreeCreate(a, pi);(*pi)++;root->right = BinaryTreeCreate(a, pi);return root;}else {return NULL;}
}

🎡三、二叉树的销毁

// 销毁
void BinaryTreeDestory(BTNode* root)
{if (root){BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);root = NULL;}
}

🎉四、遍历二叉树

前序遍历，中序遍历和后序遍历，实际上就是指根节点在子节点的先中后的顺序不同。以上图为例：
前序序列：A、B、D、E、H、C、F、G

中序遍历：D、B、H、E、A、F、C、G

后序遍历：D、H、E、B、F、G、C、A

这三种遍历方式，在代码上面还是非常相似的，只不过递归的顺序不同。

1. 前序遍历

先遍历根结点，再遍历左子树，最后遍历右子树。

// 前序遍历
void PrevOrder(BTNode* root)
{if (root == NULL){printf("N "); //打印空节点数据return;}printf("%d ", root->data); // 输出节点数据PrevOrder(root->left); //递归遍历左子树节点的数据PrevOrder(root->right); //递归遍历右子树节点的数据
}

2. 中序遍历

先遍历左子树，再遍历根结点，最后遍历右子树。

// 中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("N "); //打印空节点数据return;}InOrder(root->left); //递归遍历左子树节点的数据printf("%d ", root->data); //输出节点数据InOrder(root->right); //递归遍历右子树节点的数据
}

3. 后序遍历

先遍历左子树，再遍历右子树，最后遍历根结点。

// 后序遍历
void EndingepilogueOrder(BTNode* root)
{if (root == NULL){printf("N "); //打印空节点数据return;}EndingepiloguePrevOrder(root->left); //递归遍历左子树节点的数据EndingepiloguePrevOrder(root->right); //递归遍历右子树节点的数据printf("%d ", root->data); //输出节点数据
}

4. 层序遍历

层序遍历的做法和上述遍历做法不同，不能简单的调用递归来遍历，而是要借用到队列来辅助实现。队列的实现我就不在叙述了，层序遍历代码所示：

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Quene q;QueneInit(&q);if (root){QuenePush(&q, root); //存入根节点}while (!QueneEmpty(&q)) //队列不为空就循环{BTNode* front = QueneFront(&q); //取出队列中的第一个节点QuenePop(&q); //删除第一个节点printf("%d ", front->data); //打印取出来第一个节点的数据if (front->left){QuenePush(&q, front->left); //如果左子树不为空，就将左子树存入队列}if (front->right){QuenePush(&q, front->right); //如果右子树不为空，就将右子树存入队列}}QueneDesTroy(&q);
}

🌲五、二叉树的计算

1. 计算二叉树结点个数

计算二叉树的结点个数，只需要将左子树的结点个数加上右子树的结点个数，最后再加上根结点就完成了。

int TreeSide(BTNode* root)
{return root == NULL ? 0 : TreeSide(root->left) + TreeSide(root->right) + 1; //运用条件表达式，如果根结点为空就返回0，否则就递归调用遍历左子树和右子树的结点个数，两者相加，最后再加一个最上面的根结点。
}

2. 计算二叉树叶子结点的个数

首先要明白什么是叶子结点，实际上就是度为0的结点即孩子结点。

如上图，D、H、F、G都为叶子结点。代码展示：

int TreeLeafSize(BTNode* root)
{if (root == NULL){return 0; //空树返回0}else if (TreeLeafSize(root->left)== NULL && TreeLeafSize(root->right) == NULL){return 1; //只含有根节点就返回1}return TreeLeafSize(root->left) + TreeLeafSize(root->right); ///递归调用遍历左子树和右子树的叶子数，两者相加
}

3. 计算二叉树的深度

什么是二叉树的深度呢？简单的来说就是左子树或者右子树的深度+1。

// 求树的深度
int TreeHight(BTNode* root)
{if (root == NULL){return 0;}int highleft = TreeHight(root->left); //获取左子树的深度int highright = TreeHight(root->right); //获得右子树的深度return highleft > highright ? highleft + 1 : highright + 1; //运用条件表达式，返回左子树和右子树中较大的深度+1
}

4. 计算二叉树第k层的结点个数

实现这一操作的核心思路，就是要知道：求当前树的第k层结点个数 = 左子树的第k - 1层的结点个数 + 右子树的第k-1层的结点个数。

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0; // 空树返回0}if (k == 1){return 1; //第一层为根节点返回1}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

5. 查找二叉树中值为x的结点

这里需要注意的是，我们要记录查找到的结点，否则当我们想要返回所找到的结点数据，却发现又要重新递归去找，时间会消耗好几倍，因此需要记录找到的结点数据

BTNode* BinaryTreeFind(BTNode* root, BTDateType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* left = BinaryTreeFind(root->left, x);if (left != NULL)return left;BTNode* right = BinaryTreeFind(root->right, x);if (right != NULL)return right;// 左右子树都没有return NULL;
}

6. 判断二叉树是否为完全二叉树

按照层序遍历的方式遍历完全二叉树，当我们遍历到空结点时，就开始判断。如果队列中还有空，就不是完全二叉树

// 判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Quene q;QueneInit(&q);if (root){QuenePush(&q, root);}while (!QueneEmpty(&q)){BTNode* front = QueneFront(&q);QuenePop(&q);// 遇到第一个空就开始判断，如果队列中还有空，就不是完全二叉树if (front == NULL){break;}QuenePush(&q, front->left);QuenePush(&q, front->right);}while (!QueneEmpty(&q)){BTNode* front = QueneFront(&q);QuenePop(&q);// 如果有非空，就不是完全二叉树if (front){QueneDesTroy(&q);return false;}}QueneDesTroy(&q);return true;
}

🏝️六、整体代码展示

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include "Quene.h"typedef int BTDateType;typedef struct BinaryTreeNode
{BTDateType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;// 手搓一个二叉树BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;
}BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}// 销毁
void BinaryTreeDestory(BTNode* root)
{if (root){BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);root = NULL;}
}// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Quene q;QueneInit(&q);if (root){QuenePush(&q, root);}while (!QueneEmpty(&q)){BTNode* front = QueneFront(&q);QuenePop(&q);printf("%d ", front->data);if (front->left){QuenePush(&q, front->left);}if (front->right){QuenePush(&q, front->right);}}QueneDesTroy(&q);
}// 前序遍历
void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}// 中序遍历
void InPrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InPrevOrder(root->left);printf("%d ", root->data);InPrevOrder(root->right);
}// 后序遍历
void EndingepiloguePrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}EndingepiloguePrevOrder(root->left);EndingepiloguePrevOrder(root->right);printf("%d ", root->data);
}int TreeSide(BTNode* root)
{return root == NULL ? 0 : TreeSide(root->left) + TreeSide(root->right) + 1;
}// 求叶子结点的个数
int TreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}else if (TreeLeafSize(root->left)== NULL && TreeLeafSize(root->right) == NULL){return 1;}return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}// 求树的深度
int TreeHight(BTNode* root)
{if (root == NULL){return 0;}int highleft = TreeHight(root->left);int highright = TreeHight(root->right);return highleft > highright ? highleft + 1 : highright + 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);
}// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDateType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* left = BinaryTreeFind(root->left, x);if (left != NULL)return left;BTNode* right = BinaryTreeFind(root->right, x);if (right != NULL)return right;// 左右子树都没有return NULL;
}// 判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Quene q;QueneInit(&q);if (root){QuenePush(&q, root);}while (!QueneEmpty(&q)){BTNode* front = QueneFront(&q);QuenePop(&q);// 遇到第一个空就开始判断，如果队列中还有空，就不是完全二叉树if (front == NULL){break;}QuenePush(&q, front->left);QuenePush(&q, front->right);}while (!QueneEmpty(&q)){BTNode* front = QueneFront(&q);QuenePop(&q);// 如果有非空，就不是完全二叉树if (front){QueneDesTroy(&q);return false;}}QueneDesTroy(&q);return true;
}int main()
{BTNode* root = CreatBinaryTree();PrevOrder(root);printf("\n");InPrevOrder(root);printf("\n");EndingepiloguePrevOrder(root);printf("\n");printf("TreeSide:%d\n", TreeSide(root));printf("TreeLeafSize:%d\n", TreeLeafSize(root));printf("TreeHight:%d\n", TreeHight(root));printf("BinaryTreeFind:%p\n", BinaryTreeFind(root,3));printf("BinaryTreeLevelKSize:%d\n", BinaryTreeLevelKSize(root, 3));printf("\n");BinaryTreeLevelOrder(root);return 0;
}

今天的分享就到这里啦，如果感觉内容不错，记得一键三连噢。创作不易，感谢大家的支持，我们下次再见！ヾ(￣▽￣)Bye_Bye