数据结构：二叉树(链式结构)

devtools/2024/12/22 2:34:16/

文章目录

1. 二叉树的链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成：数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，三叉链在结构上比二叉链多了一个指向父节点的指针域。

请添加图片描述
在这里先使用二叉链来实现二叉树

2. 二叉树的创建和实现相关功能

2.1 创建二叉树

用链表来实现二叉树，每个链表结点都由一个数据域和左右指针域组成

//定义二叉树的链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode {BTDataType data;//存储数据struct BinaryTreeNpde* left;//指向左孩子结点的指针struct BinaryTreeNode* right;//指向右孩子结点的指针
}BTNode;

接下来我们来实现创建节点的函数：

首先使用malloc函数创建一个节点大小的空间，如果创建失败就打印错误信息，创建成功则把数据存储在新节点的数据域中，再将新节点的左右孩子指针指向空，最后返回新节点即可

//创建二叉树新节点
BTNode* buyNode(BTDataType 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;
}

下面我们来创建一棵如图所示的二叉树
在这里插入图片描述

BTNode* CreateTree()
{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 = node3;node2->left = node4;node2->right = node5;node3->left = node6;return node1;
}

2.2 二叉树的前，中，后序遍历

下面来简单介绍一下前，中，后序遍历的规则
在这里插入图片描述
请添加图片描述
下面来根据上面所示的二叉树进行前，中，后序遍历

2.2.1 前序遍历

前序遍历就是先打印根节点的值，再遍历根节点的左子树，最后遍历根节点的右子树，也就是根左右

//前序遍历
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}

根据以上代码：进入函数先打印根节点存储的值，再递归左子树，左子树递归完后再递归右子树。不要忘了，如果遇到空节点记得要返回。

前序遍历的步骤：

  1. 打印根节点的值为1
  2. 递归左子树，创建根节点左孩子节点2的函数栈帧
  3. 打印节点2的值为2，创建节点2的左孩子节点4的函数栈帧
  4. 打印节点4的值为4，创建节点4的左孩子节点的函数栈帧
  5. 节点4的左孩子节点为空，返回节点4的函数栈帧
  6. 创建节点4的右孩子节点的函数栈帧
  7. 节点4的右孩子节点为空，返回节点4的函数栈帧
  8. 节点4的函数栈帧被销毁，返回节点2的函数栈帧
  9. 创建节点2的右孩子节点5的函数栈帧
  10. 打印节点5的值为5，创建节点5的左孩子节点的函数栈帧
  11. 节点5的左孩子节点为空，返回节点5的函数栈帧
  12. 创建节点5的右孩子节点的函数栈帧
  13. 节点5的右孩子节点为空，返回节点5的函数栈帧
  14. 节点5的函数栈帧被销毁，返回节点2的函数栈帧
  15. 节点2的函数栈帧被销毁，返回根节点的函数栈帧
  16. 创建根节点的右孩子节点3的函数栈帧
  17. 打印节点3的值为3，创建节点3的左孩子节点6的函数栈帧
  18. 打印节点6的值为6，创建节点6的左孩子节点的函数栈帧
  19. 节点6的左孩子节点为空，返回节点6的函数栈帧
  20. 创建节点6的右孩子节点的函数栈帧
  21. 节点6的右孩子节点为空，返回节点6的函数栈帧
  22. 节点6的函数栈帧被销毁，返回节点3的函数栈帧
  23. 创建节点3的右孩子节点的函数栈帧
  24. 节点3的右孩子节点为空，返回节点3的函数栈帧
  25. 节点3的函数栈帧被销毁，返回根节点的函数栈帧
  26. 根节点的函数栈帧被销毁

所以前序遍历的结果为：1 2 4 5 3 6

中序遍历和后序遍历与前序遍历的思路一样，只是打印节点的值和递归左右子树的顺序不同而已

2.2.2 中序遍历

思路：先遍历根节点的左子树，再打印根节点的值，最后遍历根节点的右子树，也就是左根右

中序遍历的结果：4 2 5 1 6 3

//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

2.2.3 后序遍历

思路：先遍历根节点的左子树，再遍历根节点的右子树，最后打印根节点的值，也就是左右根

后序遍历的结果：4 5 2 6 3 1

//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

2.3 二叉树节点个数

思路：先递归根节点的左子树，再递归根节点的右子树，如果递归到空节点就返回0，最后返回左子树节点个数和右子树节点个数的和再加一

//二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

2.4 二叉树叶子结点个数

思路：第一种情况：如果递归到的当前节点为空就返回0，第二种情况：如果节点的左右子树为空时说明该节点为叶子节点则返回1，第三种情况：如果递归到的节点既不是空又不是叶子节点，则继续递归该节点的左右子树，即返回该节点左右子树的叶子节点 return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right)

//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

2.5 二叉树第k层结点个数

思路：因为根节点是第一层，所以每次向下遍历时将k减一，当k=1时当前节点就是在第k层，返回1即可，所以只需一直递归节点的左右子树，每次递归节点的左右子树时还要让k减一。当递归到的节点为空时，只需返回0即可，要先判断节点为不为空，如果不为空再判断当前节点是不是在第k层。

//二叉树第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);
}

2.6 二叉树的深度/高度

思路：因为二叉树的左右子树的高度可能不一样，所以要分开递归二叉树的左右子树，然后再取最大值即可。当递归到空节点时返回0，否则继续递归当前节点的左右子树，最后返回左右子树深度的最大值再加一(因为当前的根节点也是一层)

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDepth = BinaryTreeDepth(root->left);int rightDepth = BinaryTreeDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

2.7 二叉树查找值为x的结点

思路：先遍历根节点的左子树，如果找到了值为x的节点就返回该节点的地址，右子树也无需再遍历了，如果没有找到再遍历右子树，如果找到了就返回该节点的地址，没有找到则返回空。再遍历的过程中，先判断节点是否为空，如果为空就返回空，不为空的话再判断该节点的值是不是x，如果是就返回该节点的地址，如果不是就继续遍历该节点的左右子树。

//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType 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;
}

2.8 层序遍历

这里需要借助队列，不熟悉的可以看一下数据结构—队列

层序遍历是指从根节点开始一层一层遍历二叉树，从上至下，从左至右，依次访问节点，如下图，该二叉树的层序遍历结果为：1 2 3 4 5 6

请添加图片描述
使用队列这个数据结构来实现层序遍历，队列的特点是先进先出。首先将根节点放入队列中，再将根节点出队，最后将根节点的左右孩子节点入队。将根节点的左孩子2出队，然后将根节点的左孩子2的左右孩子节点入队，以此类推……一直到队列为空

在这里插入图片描述

//层序遍历
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);}}QueueDestroy(&q);
}

2.9 判断二叉树是否为完全二叉树

思路：同样还是借助队列这个数据结构，与层序遍历不同的是，当节点的左右孩子节点为空时也要进行入队操作，当队头为空时，就退出循环，然后还需要判断队列里有没有不为空的节点，如果有说明二叉树不为完全二叉树，如果没有说明二叉树为完全二叉树

//判断二叉树是否为完全二叉树
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;
}

2.10 二叉树的销毁

思路：因为要销毁整个二叉树包括根节点，所以这里传递的是二级指针去接收一级指针的地址，这样就实现了形参改变实参。先销毁根节点的左子树和右子树，也就是递归到叶子节点开始销毁，然后往上一层一层地进行销毁，最后再销毁根节点。

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

3. 源代码

Tree.h头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义二叉树的链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode {BTDataType data;//存储数据struct BinaryTreeNpde* left;//指向左孩子结点的指针struct BinaryTreeNode* right;//指向右孩子结点的指针
}BTNode;//创建二叉树新节点
BTNode* buyNode(BTDataType x);
//创建一个二叉树
BTNode* CreateTree();
//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//二叉树结点个数
int BinaryTreeSize(BTNode* root);
//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
//二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);
//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
//二叉树销毁
void BinaryTreeDestory(BTNode** root);
//层序遍历
void LevelOrder(BTNode* root);
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

Tree.c源文件

#include "Tree.h"
#include "Queue.h"
//创建二叉树新节点
BTNode* buyNode(BTDataType 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;
}
//前序遍历
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);
}
//二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
//二叉树第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);
}
//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDepth = BinaryTreeDepth(root->left);int rightDepth = BinaryTreeDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType 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 BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*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);}}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;
}

test.c源文件

#include "Tree.h"BTNode* CreateTree()
{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 = node3;node2->left = node4;node2->right = node5;node3->left = node6;return node1;
}void BinaryTreeTest01()
{BTNode* node1 = CreateTree();PreOrder(node1);printf("\n");InOrder(node1);printf("\n");PostOrder(node1);printf("\n");printf("%d\n", BinaryTreeSize(node1));printf("%d\n", BinaryTreeLeafSize(node1));printf("第%d层结点个数为：%d\n", 3, BinaryTreeLevelKSize(node1, 3));printf("%d\n", BinaryTreeDepth(node1));if (BinaryTreeFind(node1, 10) == NULL){printf("没有找到\n");}else{printf("找到了\n");}LevelOrder(node1);printf("\n");printf("%s\n", BinaryTreeComplete(node1) == true ? "是完全二叉树" : "不是完全二叉树");BinaryTreeDestory(&node1);
}
int main()
{BinaryTreeTest01();return 0;
}

对以上内容有不同看法的欢迎来讨论，希望对大家的学习有帮助，多多支持哦！


http://www.ppmy.cn/devtools/86588.html

相关文章

代码混淆与代码打包---bash脚本

代码混淆与代码打包---bash脚本

0x00 背景 最简单混淆shell 0x01 操作 安装&#xff1a; yum install gzip 混淆&#xff1a; gzexe your_script.sh 反混淆&#xff1a; gzexe -d your_script.sh~ 0x02 后记 先立个flag&#xff0c;后面有时间更新其他混淆方式~~
阅读更多...
如何查看操作系统的性能指标：CPU、内存、磁盘、网络

如何查看操作系统的性能指标：CPU、内存、磁盘、网络

目录 本系列专栏 CPU篇 CPU使用率&#xff1a;top CPU负载&#xff1a;uptime CPU核心使用情况&#xff1a;mpstat -P ALL 1 上下文切换&#xff1a;vmstat 1 CPU等待 IO时长&#xff1a;iostat -x 1 CPU的频率&#xff1a;lscpu 或者 cat /proc/cpuinfo | grep "cpu MHZ…
阅读更多...
NLP与搜广推常见面试问题

NLP与搜广推常见面试问题

1 auc指标 AUC的两种意义 一个是ROC曲线的面积另外一个是统计意义。从统计学角度理解&#xff0c;AUC等于随机挑选一个正样本和负样本时&#xff0c;模型对正样本的预测分数大于负样本的预测分数的概率。下图为搜广推场景下的一个计算auc的例子 2 GAUC指标 就是在推荐系统…
阅读更多...
OCC 布尔操作

OCC 布尔操作

一、简介 BRepAlgoAPI_Algo 是 OpenCASCADE 中用于布尔操作的基类&#xff0c;提供了布尔运算的基础功能。布尔操作是计算几何中常见的操作&#xff0c;用于对两个形状进行交、并、差运算等。这些操作在 CAD 和 3D 建模中非常重要。 BRepAlgoAPI_Algo 的基本功能 BRepAlgoAPI…
阅读更多...
Python 初学者福音：30个实用任务详细步骤分享

Python 初学者福音：30个实用任务详细步骤分享

学习Python最快的方法就是通过实战。以下是30个极简Python任务&#xff0c;每个任务都有对应的代码片段&#xff0c;帮助你快速掌握Python开发技巧。无论你是初学者还是有经验的开发者&#xff0c;这些代码都能帮你提升技能。 1. 重复元素判定 检查列表中是否存在重复元素&am…
阅读更多...
细调模型精度：在sklearn中进行增量特征正则化的高级指南

细调模型精度：在sklearn中进行增量特征正则化的高级指南

细调模型精度&#xff1a;在sklearn中进行增量特征正则化的高级指南 在机器学习中&#xff0c;正则化是一种用于防止模型过拟合的技术&#xff0c;通过在损失函数中添加一个额外的项来惩罚模型的复杂度。当使用增量学习添加新特征时&#xff0c;正则化变得更加重要&#xff0c…
阅读更多...
文件上传题目练习

文件上传题目练习

之前学习文件上传的时候都是通过练习ctfhub上的题&#xff0c;知道有upload-labs这个靶场&#xff0c;但是还没尝试过&#xff0c;现在重新复习就打算打一下这个靶场 Pass-01 发现仅仅是弹出对话框&#xff0c;说明是前端验证 直接F12禁用js就可以了 上传成功 蚁剑测试连接&am…
阅读更多...
程序员修炼之路

程序员修炼之路

成为一名优秀的程序员&#xff0c;需要广泛而深入地学习多个领域的知识。这些课程不仅帮助建立扎实的编程基础&#xff0c;还培养了问题解决、算法设计、系统思维等多方面的能力。以下是一些核心的必修课&#xff1a; 计算机基础 计算机组成原理&#xff1a;理解计算机的硬件组…
阅读更多...
最新文章

Copyright @ 2022~2023