二叉树链式存储结构详解
创作时间:
作者:
@小白创作中心
二叉树链式存储结构详解
引用
CSDN
1.
https://blog.csdn.net/2302_79546368/article/details/142897795
二叉树链式存储结构详解
1. 回顾引入
回顾二叉树的概念，二叉树分为空树和非空树，非空二叉树由根节点，根节点的左子树和根节点的右子树组成。
根节点的左子树和右子树分别又是由子树节点，子树节点的左子树和子树节点的右子树组成的，因此二叉树定义是递归式的，后续链式二叉树的操作中基本都是按照该概念实现的。
2. 遍历规则的介绍
2.1 前序遍历
前序遍历又称先序遍历：访问根节点的操作发生在遍历其左右子树之前。
访问顺序：根节点，左子树，右子树
2.2 中序遍历
中序遍历：访问根节点的操作发生在遍历其左右子树之中（间）。
访问顺序：左子树，根节点，右子树
2.3 后序遍历
后序遍历：访问根节点的操作发生在遍历其左右子树之后。
访问顺序：左子树，右子树，根节点
3. 链式二叉树的实现
在这里我们还是将其实现的部分分为三个部分：tree.h(二叉树的节点的结构的定义以及函数的声明部分），tree.c(函数功能的实现部分），test.c(函数功能的测试部分）
3.1 tree.h(二叉树的节点的结构的定义以及函数的声明部分）
#pragma once
#include <stdio.h>
#include <assert.h>
#include<stdlib.h>
#include<stdbool.h>
//链式结构树的节点的定义以及函数的声明
typedef int BTDatatype;
typedef struct TreeNode
{
BTDatatype data;
struct TreeNode* left;
struct TreeNode* right;
}BTNode;
//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//二叉树节点的个数
int BinaryTreeSize(BTNode* root);
//二叉树叶子节点的个数
int BinaryTreeLeafSzie(BTNode* root);
//二叉树第k层节点的个数
int BinaryTreeLevelKSzie(BTNode* root,int k);
//二叉树的深度
int BinaryTreeDepth(BTNode* root);
//在二叉树中查找值为x 的节点
BTNode* BinaryTreeFind(BTNode* root, int x);
//二叉树的销毁
void BinaryTreeDestroy(BTNode* root);
//二叉树的层序遍历
void LevelOrder(BTNode* root);
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);
ps:目前，我们在最开始学习二叉树的时候对二叉树的限制较少，在这里实现插入，删除之类的操作没有意义，后续会给大家更新到平衡树或者红黑树，二叉树会有限制，敬请期待！
3.2 tree.c(函数功能的实现部分）
3.2.1 前，中，后序遍历的实现
注意：可以结合前面的遍历规则进行理解！！！
//前序遍历
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 PostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
除此之外，需要认真的队2二叉树的递归式定义好好理解。在这里函数的实现的部分体现的尤为明显。
3.2.2 其余函数功能的实现
//二叉树节点的个数
int BinaryTreeSize(BTNode* root)
{
if (root == 0)
{
return 0;
}
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
//二叉树叶子节点的个数
int BinaryTreeLeafSzie(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return BinaryTreeLeafSzie(root->left) + BinaryTreeLeafSzie(root->right) ;
}
//二叉树第k层节点的个数
int BinaryTreeLevelKSzie(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)//判断是不是第k层
{
return 1;
}
//如果不是第k层就向下遍历
return BinaryTreeLevelKSzie(root->left, k - 1) + BinaryTreeLevelKSzie(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* BinaryTreeFind(BTNode* root, int x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* leftfind = BinaryTreeFind(root->left, x);
if (leftfind)
{
return leftfind;
}
BTNode* rightfind = BinaryTreeFind(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 LevelOrder(BTNode* root)
{
//这需要利用队列的性质进行遍历
//注意：这里是将节点的地址放进队列之中
Queue q;
QueueInit(&q);
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);
}
//判断二叉树是否为完全二叉树
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)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
值得注意的是在实现层序遍历和判断二叉树是否为完全二叉树的时候我们用到了前面所学的队列这一数据结构的性质，来帮助实现层序遍历和判断二叉树是否为完全二叉树。
3.3 test.c(函数功能的测试部分）
#define _CRT_SECURE_NO_WARNINGS
#include "tree.h"
BTNode* BuyNode(int x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
newnode->data = x;
newnode->left = newnode->right = NULL;
return newnode;
}
int main()
{
BTNode* node1 = BuyNode(10);
BTNode* node2 = BuyNode(5);
BTNode* node3 = BuyNode(19);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(8);
BTNode* node6 = BuyNode(13);
BTNode* node7 = BuyNode(24);
// 10
node1->left = node2, node1->right = node3;// 5 19
node2->left = node4, node2->right = node5;// 4 8 13 24
node3->left = node6, node3->right = node7;
BTNode* phead = node1;
printf("前序遍历的结果:");
PreOrder(phead);
printf("\n");
printf("中序遍历的结果:");
InOrder(phead);
printf("\n");
printf("后序遍历的结果:");
PostOrder(phead);
printf("\n");
printf("二叉树的节点的个数为:%d\n", BinaryTreeSize(phead));
printf("二叉树的叶子节点的个数为:%d\n", BinaryTreeLeafSzie(phead));
printf("二叉树的第%d层节点的个数为:%d\n",3, BinaryTreeLevelKSzie(phead,3));
if (BinaryTreeFind(phead,13))
{
printf("找到了\n");
}
else printf("未找到\n");
printf("层序遍历的结果为:");
LevelOrder(phead);
bool a=BinaryTreeComplete(phead);
if (a)
{
printf("该二叉树是完全二叉树\n");
}
else printf("该二叉树不是完全二叉树\n");
BinaryTreeDestroy(&phead);
return 0;
}
运行结果如下：
以上是测试代码，注意自己每写完一个函数功能就去测试，不要等着所有的函数写完才去测试。上面的测试代码所建立的二叉树正是前面的遍历规则中个大家所呈现的二叉树。大家可以前后对照着理解。不要只看，记得自己动手实现一下。养成良好的代码习惯在必要的时候也会事半功倍的！！！
热门推荐
荣光计划 | 让偏乡的孩子看见世界——智慧教室2024年记
全面提升研究生的创新实践能力
教育通识课程：现代综合素质教育的核心
秋冬宜昌游：打卡三峡大坝+露营
这10种蔬菜要常吃，营养物质丰富，增强身体抵抗力
长期用大蒜“炝锅”，炒出来的菜会致癌，是真的吗？告诉你答案
戴玉石贴身是否会变色？如何保养和清洗玉石饰品以保持其美观？
艺术开卷｜春水秋山玉：玉器中的草原风尚
人民币，被严重低估！
“以旧换新：让你轻松升级手机并保护环境的实用指南”
订阅、租借和租赁：三种商业模式的区别与优劣分析
中医怎么调理胃酸过多
虞恋莎教你：夫妻坦诚相待的智慧与技巧
奔驰C级电瓶品牌型号，C级蓄电池怎么更换教程
奔驰C260电瓶品牌型号及更换教程
宝古图沙漠冬季游：冰车、滑雪全攻略！
瑞舒伐他汀的副作用全解析：从肌肉疼痛到血糖异常
自制薯条，为你的世界杯观赛加点料！
炸薯条的健康隐患：反式脂肪酸和丙烯酰胺的影响与安全食用建议
橄榄油炸薯条：健康与美味的完美结合
炸薯条的完美选择：酸土豆 vs 肯纳贝克
小白买电动车技巧，掌握10个选电动车关键技巧，花少钱轻松买好车
心理师请回答：人最大的动力来自哪里？三个问题帮你激发内在动力
G606次高铁最新时刻表出炉！太原至北京仅需2小时57分
孕期吃花生，好处多还是风险大？一文解读！
破解花生迷思！營養、功效與保存秘訣全揭露（附10篇精選食譜）
“外小好声音”：用歌声点亮语言学习之路
合唱团七大绝技，让你秒变歌神！
西安市人民医院专家提醒：男性乳腺炎预防不容忽视
新版《古汉语常用字字典》《中国古代文化常识辞典》出版