当前位置： 首页 > news >正文

数据结构 之 【链式二叉树】(C语言实现二叉树的前序中序后序层序遍历，节点个数、树的高度、第K层的节点个数、查找、完全二叉树的判别、销毁创建二叉树)

news 2025/7/12 10:57:34

目录

1前置说明

2.二叉树的遍历

2.1前序、中序、后序遍历

 2.2层序遍历

 3.节点个数

4.树的高度(根节点的高度为1) 

5.树的第K层的节点个数 (层数大于0)

6.查找 

7.判别完全二叉树

8.销毁二叉树

9.创建二叉树 

1前置说明

下文将链式二叉树简称为二叉树

学习二叉树首先需要创建一棵二叉树，但初学者直接学习二叉树的创建方式，难度可谓是从入门到入土，所以下面先手动创建一棵二叉树，了解二叉树的部分操作后再回过头来研究二叉树真正的创建方式

typedef int BTDataType;
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType val;}BTNode;BTNode* BuyBTNode(BTDataType val)
{BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (!root){perror("malloc fail");return NULL;}root->left = NULL;root->right = NULL;root->val = val;return root;
}BTNode* CreateBinaryTree()
{BTNode* node1 = BuyBTNode(1);BTNode* node2 = BuyBTNode(2);BTNode* node3 = BuyBTNode(3);BTNode* node4 = BuyBTNode(4);BTNode* node5 = BuyBTNode(5);BTNode* node6 = BuyBTNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}

 (1)上述代码重命名了 int 类型，方便后续更改数据类型

(2)一棵二叉树的一个节点包含：储存变量val，左右孩子节点指针left、right

(3)BuyBTNode函数在堆上开辟空间，并初始化每个节点

(4)CreateBinaryTree函数手动创建了一棵二叉树，并返回根节点指针。如下图：

2.二叉树的遍历

2.1前序、中序、后序遍历

1. 前序遍历(先序遍历、先根遍历)——访问根结点的操作发生在遍历其左右子树之前

即 根 左子树 右子树

2. 中序遍历(中根遍历)——访问根结点的操作发生在遍历其左右子树之中（间）

即 左子树 根 右子树

3. 后序遍历(后根遍历)——访问根结点的操作发生在遍历其左右子树之后

即 左子树 右子树 根

由于遍历访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）可解释为 根、根的左子树和根的右子树。NLR、LNR和LRN分别称为先根遍历、中根遍历和后根遍历

//根 左 右
void PrevOrder(BTNode* root){if (!root){printf("NULL ");return;}printf("%d ", root->val);PrevOrder(root->left);PrevOrder(root->right);
}
// 左 根 右
void InOrder(BTNode* root){if (!root){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->val);InOrder(root->right);
}
// 左 右 根
void PostOrder(BTNode* root){if (!root){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->val);
}

三种遍历实现方式及运行结果如上

以前序遍历为例，下面通过递归展开图，更好体会遍历的过程 

如上图

调用PrevOrder函数并传入根节点(节点存储值为1)的指针，指针不为空，打印节点值，然后递归调用PrevOrder函数访问根节点的左子树(节点存储值为2)，指针不为空，打印节点值，然后递归调用PrevOrder函数访问当前节点的左子树(节点存储值为3)，指针不为空，打印节点值，然后递归调用PrevOrder函数访问当前节点的左子树,指针为空，函数返回，开始访问值为3的节点的右子树，指针为空，函数返回，开始访问值为2的节点的右孩子，指针为空，函数返回，开始访问值为1的节点的右子树，.........

 上诉过程中，打印节点值、函数返回就是遍历访问节点的一种方式

首先访问根节点，然后是根节点的左子树，左子树又是由根、左子树、右子树构成的，所以先访问根，再访问根的左子树的左子树，左子树又是由根、左子树、右子树构成的，所以先访问根，再访问根的左子树的左子树的左子树，此时为空树，该方向的遍历停止，开始访问根的左子树的左子树的右子树，此时为空树，该方向的遍历停止，开始访问根的左子树的右子树，此时为空树，该方向的遍历停止，开始访问根的右子树...........

前中后序的遍历落实到了递归上，可根据下图再理解理解

三种遍历的本质差异在于访问根节点的时机

 2.2层序遍历

 顾名思义，层序遍历就是一层一层的访问二叉树的节点(先第一层，再第二层......)

这里需要用到前面队列的特性，首先树为空直接返回，否则，从根节点开始，将节点的指针

(不为空)入队，然后在出队的同时，将该节点的左右孩子节点入队，队列为空时就停止 

如上图所示，(以节点存储值代替节点指针说明)

1入队，1出队，同时2、4入队；2出队，同时3入队(2的右孩子为空，没必要入队);4出队，同时5、6入队；3出队(左右孩子为空，没必要入队)，5出队(左右孩子为空，没必要入队)，6出队(左右孩子为空，没必要入队)，停止

void LevelOrder(BTNode* root){if (!root)return;Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* Front = QueueFront(&q);QueuePop(&q);//if (Front)  //第一次插入的树节点指针不为空//第一次可以放心打印，后续控制不进空，就直接打印printf("%d ", Front->val);//空没有必要进，if (Front->left)QueuePush(&q, Front->left);if (Front->right)QueuePush(&q, Front->right);}QueueDestroy(&q);}

 (1)树为空，直接返回，否则初始化队列，并将根节点指针入队

(2)调用QueueFront函数拿到队首元素中存储的节点指针值，

然后出队，同时代入其不为空的孩子节点

(3)队列为空时停止，注意销毁队列，防止内存泄漏

 3.节点个数

//左 + 右 + 1
int TreeSize(BTNode* root){if (!root)return 0;return TreeSize(root->left) + TreeSize(root->right) + 1;
}

代码非常简洁，意思就是节点为空返回0，否则该棵树的节点个数等于

左子树的节点个数 + 右子树的节点个数 + 1

 如上图

调用TreeSize函数并传入根节点(节点存储值为1)的指针，指针不为空，调用TreeSize函数计算节点(节点存储值为1)的左子树(根节点存储值为2)的节点个数，指针不为空，调用TreeSize函数计算节点(节点存储值为2)的左子树(根节点存储值为3)的节点个数，指针不为空，调用TreeSize函数计算节点(节点存储值为3)的左子树的节点个数,指针为空，函数返回0，开始计算节点存储值为3的节点的右子树的节点个数，指针为空，函数返回0，开始计算值为2的节点的右子树的节点个数，指针为空，函数返回0，开始计算值为1的节点的右子树的节点个数，.........

总结来说，这又是一次递归实战，重要的是求出递推公式，找到最小子问题及其结束条件

对于本题来说， 

递推公式: 

该棵树的节点个数等于左子树的节点个数 + 右子树的节点个数 + 1

最小子问题及其结束条件：

对于某一个节点，为空就返回0，不为空就套用递推公式

4.树的高度(根节点的高度为1) 

//左右子树较高者 + 1
int TreeHeight(BTNode* root){if (!root)return 0;int l = TreeHeight(root->left);int r = TreeHeight(root->right);return l > r ? l + 1 : r + 1;
}

同样是递归实战，递推公式: 树高 = 左右子树较高者的高度 + 1

最小子问题及其结束条件：树为空就返回0，否则先分别计算左右子树的高度，再比较返回

以节点存储值代替节点指针进行说明

1不为空，先计算1的左子树(根节点存储值为2)的高度，2不为空，先计算2的左子树(根节点存储值为3)的高度，3不为空，先计算3的左子树的高度，树为空，返回0，再计算3的右子树的高度，树为空，返回0，比较返回1，(即2的左子树(根节点存储值为3)的高度),再计算2的右子树的高度，树为空，返回0，比较返回2，(即1的左子树(根节点存储值为2)的高度)，此时该树的左子树的高度计算完毕，开始计算其右子树的高度..........

5.树的第K层的节点个数 (层数大于0)

//左右子树第K - 1 层的节点个数之和
int TreeKLevel(BTNode* root, int k){assert(k > 0);if (!root)return 0;if (k == 1)return 1;return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}

递推公式: 树的第K层节点个数 = 左子树第 K - 1 层节点个数 + 右子树第 K - 1 层节点个数

最小子问题及其结束条件：对于某一节点，为空就返回0，不为空且所在层数(设为w)为1就返回1，否则需分别计算其左右子树第1+k - w层(不用手动计算，递归调用时，层数自动递减)的节点个数，再求和

以节点存储值代替节点指针进行说明

1不为空，先计算1的左子树(根节点存储值为2)第2层的节点个数，2不为空，先计算2的左子树(根节点存储值为3)第1层的节点个数，3不为空且层数为1，返回1，再计算2的右子树的第1层的节点个数，树为空，返回0，求和返回得到1的左子树的第2层的节点个数，此时该树的左子树的第2层的节点个数计算完毕，开始计算其右子树的第2层的节点个数..........

6.查找 

// 自己 左右子树中找
BTNode* BinaryTreeFind(BTNode* root, BTDataType x){if (!root)return NULL;if (root->val == x)return root;BTNode* left = BinaryTreeFind(root->left, x);if (left)return left;BTNode* right = BinaryTreeFind(root->right, x);if (right)return right;return NULL;
}

在普通二叉树中查找某个值的思路：先在当前节点找，再到左右子树去找

最小子问题及结束条件就是，对于某一节点，如果为空，返回空，如果所存储值就是要找的值就返回该节点的指针，否则再去它的左右子树找，找不到就返回空 

7.判别完全二叉树

层序遍历二叉树的节点指针(空树NULL也算)，可以发现

完全二叉树层序遍历的特点：不为空的节点指针连续

普通二叉树层序遍历的特点：为空的节点指针不连续

bool BinaryTreeComplete(BTNode* root)
{if (!root)return true;//首先入队Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* Front = QueueFront(&q);QueuePop(&q);//空也入队if (Front){QueuePush(&q, Front->left);QueuePush(&q, Front->right);}else{break;}}//完全二叉树的空是连续的！！while (!QueueEmpty(&q)){if (QueueFront(&q)){//注意资源清理QueueDestroy(&q);return false;}QueuePop(&q);}QueueDestroy(&q);return true;
}

 (1)树为空，返回真，否则根节点指针入队

(2)取得队首元素的节点存储值，出队，然后代入该节点的左右孩子(如果有的话)

(3)没有左右孩子，说明遇到了第一个NULL节点，此时选择跳出循环，遍历队列中剩下的元素，如果存在队首元素的节点存储值不为空，返回false，并及时清理队列资源，遍历完成则意味着该树是完全二叉树，返回true，并及时清理队列资源

8.销毁二叉树

销毁一棵二叉树，第一想法就是遍历销毁，可选择哪种遍历方式呢？

先序遍历，直接就把根节点给销毁了，需要提前保存左右孩子节点

中序遍历，根节点会先于右孩子节点销毁了，需要提前保存右孩子节点

所以选择后序遍历，先销毁孩子节点再销毁根而无需提前保存孩子节点

void BinaryTreeDestory(BTNode** root)
{//root一定不为空assert(root);if (!(*root))return;BinaryTreeDestory(&((*root)->_left));BinaryTreeDestory(&((*root)->_right));free(*root);*root = NULL;
}

最小子问题及其结束条件：节点为空即返回，否则先销毁它的孩子节点，再销毁自己 

9.创建二叉树 

通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

思路：遍历字符数组，遇到'#'(意味着空节点)就返回，否则就开辟一个节点的空间存储该值，

并用下一个字符所在的节点作为上一个字符所在节点的左孩子，......直到遇见'#'，左孩子方向创建完毕，开始创建右孩子节点

BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->_data = a[(*pi)++];root->_left = BinaryTreeCreate(a, pi);root->_right = BinaryTreeCreate(a, pi);return root;
}

(1)下标 i 遍历数组，需要传入它的地址使其按需改变

(2)思路就是按照先序遍历的顺序，先创建根节点，再创建根节点的左孩子，左孩子是一棵子树的根节点，所以再创建根节点的左孩子的左孩子，......直到为空，开始创建右孩子节点....

http://www.xdnf.cn/news/1102573.html

相关文章：

  • Redis5.0.5 漏洞
  • uni-app获取手机当前连接的WIFI名称
  • GIC控制器 （三）
  • 飞算JavaAI进阶：重塑Java开发范式的AI革命
  • 语音对话秒译 + 视频悬浮字 + 相机即拍即译：ViiTor 如何破局跨语言场景？
  • 上位机知识篇---Docker
  • SpringCloud之Ribbon
  • 从延迟测试误区谈起：SmartPlayer为何更注重真实可控的低延迟？
  • 飞算JavaAI 实战笔记
  • 从零实现一个GPT 【React + Express】--- 【3】解析markdown，处理模型记忆
  • 继承和多态扩展学习
  • 没有Mac如何完成iOS 上架：iOS App 上架App Store流程
  • Django--02模型和管理站点
  • 【Springboot】Bean解释
  • CPT203-Software Engineering: Project Managent 项目管理
  • 继承 示例
  • 飞算 JavaAI：开启 Java 开发新时代
  • 使用Python将目录中的JPG图片按后缀数字从小到大顺序纵向拼接，很适合老师发的零散图片拼接一个图片
  • Set 二分 -＞ 剑指算法竞赛
  • 【9】PostgreSQL 之 vacuum 死元组清理
  • Ant ASpin自定义 indicator 报错
  • 模拟开关、可编程增益仪表放大器电路
  • VLM-R1 + GRPO 算法完整复现全过程日志
  • 随手记录第二十话 -- Python3版本虚拟环境安装与AI的接入使用
  • RuoYi+Uniapp(uni-ui)开发商城系统
  • python学习DataFrame数据结构
  • 数据结构第一章复杂度的认识
  • 【java17】使用 Word 模板导出带替换符、动态表格和二维码的文档
  • iOS 数组如何设计线程安全
  • 提示工程：突破Transformer极限的计算科学