二叉树链式存储结构详解
创作时间:
作者:
@小白创作中心
二叉树链式存储结构详解
引用
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;
}
运行结果如下：
以上是测试代码，注意自己每写完一个函数功能就去测试，不要等着所有的函数写完才去测试。上面的测试代码所建立的二叉树正是前面的遍历规则中个大家所呈现的二叉树。大家可以前后对照着理解。不要只看，记得自己动手实现一下。养成良好的代码习惯在必要的时候也会事半功倍的！！！
热门推荐
基础英语 |适合少儿英语学习的10部动画片，收藏假期陪孩子一起看吧！
面包虫生长的5个过程
如何营造有温度的课堂氛围？
中子成像揭秘日本刀内部结构：非破坏性技术首次捕捉到备州长船则光的微观特征
家用健身器材有哪些 5大器材让你在家也能练出好身材
地中海气候特点是什么 分布在什么地区
福建省位于热带还是亚热带 福建省气候特点介绍
误食尿素对人体有害吗
沈飞六代机或率先应用机载垂发系统，将成空战规则重塑者
国际旅行必读：各国食品入境限制全攻略
距印度不足 80 公里，新藏铁路建成的战略价值究竟几何
如何判断瓷砖质量？这些标准助你选购优质建材
启动电容对晶振频率的双重影响及优化指南
什么是市场保护措施
英特尔13/14代酷睿CPU遭遇稳定性问题 AMD的机会来了？
鬼谷八荒捏脸：定制属于你的仙侠世界角色
专访安徽宿州市长王启荣：因地制宜发展农业新质生产力，让“大粮仓”更加“数智化”
宝宝多大能吃南瓜子？这些食用要点请收好
敦刻尔克大撤退：德军困境与盟军撤退的较量
C语言中十六进制数如何进一位
大米能冷冻保存吗？4个方法可以看！
管道离心泵的材料选择
马斯克的成长经历给我们的启示
酒神与日神：尼采论希腊悲剧精神
江团和鲶鱼哪个干净？4步告诉你答案
菠萝切开后怎么保存？隔夜还能吃吗？
烤鸡的热量及营养成分
烤鸡的热量及营养成分
引入10条高铁、城际！广州火车站大改造
感冒鼻塞流鼻涕最快解决办法是什么