c语言-数据结构-链式二叉树

目录

1、二叉树的概念及结构

2、二叉树的遍历概念

2.1 二叉树的前序遍历

2.2 二叉树的中序遍历 

2.3 二叉树的后序遍历 

2.4 二叉树的层序遍历

3、创建一颗二叉树 

4、递归方法实现二叉树前、中、后遍历 

4.1 实现前序遍历

4.2 实现中序遍历

4.3 实现后序遍历 

5、求二叉树的结点总数

6、求二叉树叶子个数

7、求第k层结点总数

8、求二叉树的高度

9、从二叉树中查找值为x的结点

10、层序遍历

11、二叉树的销毁

12、测试功能

结语:


1、二叉树的概念及结构

        二叉树是由根节点和一个左子树以及一个右子树构成,且每一个结点的孩子节点可以少于两个但是不能多于两个,每个结点都带有一个数据,作为结点的有效值。二叉树示意图如下:

        从上图可以看出,位于根结点左半部分的称为左子树,位于根结点右半部分的称为右子树,二叉树的顺序不能颠倒。同时2既可以看出是根结点1的孩子结点,他也可以作为3的父母结点,因此2也可以看作是一个根结点。 

        因此二叉树通常都采用递归的方式来实现。

2、二叉树的遍历概念

        在学习数组的时候,有一个最基本的概念就是遍历数组,数组的很多问题都是在遍历数组的基础上完成的。学习链表的时候,链表的很多操作也是在遍历链表的前提下实现的。因此,要对二叉树进行一系列的操作,也需要遍历二叉树。

        二叉树的遍历一般采用递归的方式,对二叉树的每个结点进行相应操作。二叉树的遍历分为:前序遍历、中序遍历、后序遍历以及层序遍历。

2.1 二叉树的前序遍历

       前序遍历的顺序:根、左子树、右子树。结构图如下:

        上图的二叉树前序遍历:123NNN45NN6NN(N表示NULL)。 

        前序遍历详解:1为根节点,因此从1开始遍历,2是1的左子树也就是遍历到2这个位置(前序遍历顺序:根-左子树-右子树),这时候会把2看成一棵树(2为根结点),然后逻辑又回到了根-左子树-右子树,3是2的左子树,因此下一个遍历的就是3,这时候又把3看成了一棵树(3为根结点),遍历3结点的左子树也就是NULL,当遍历当NULL的时候就开始“往上收回”,这时候3的左子树收回后就去遍历右子树,而这里3的右子树也是NULL因此也发生收回,最后的结果就是3结点遍历完成,同时表示结点2的左子树遍历完成,接下来就是遍历结点2的右子树,最后收回到根结点1(表示根结点1的左子树遍历完成)。接下来就是去遍历根结点1的右子树,遍历右子树的逻辑也是一样,把4看成根节点,继续根-左子树-右子树的逻辑。

2.2 二叉树的中序遍历 

        中序遍历的结构图与前序遍历的结构图相似,只是中序遍历的顺序不一样,中序遍历顺序为:左子树、根、右子树。

        因此该二叉树的中序遍历的顺序为:N3N2N1N5N4N6N(N表示NULL)

        中序遍历详解:2可以看成是1的左子树,3可以看成是2的左子树,NULL是3的左子树。中序遍历的第一个是左子树,因此把3看成是一棵树并且从3入手,遍历3的左子树NULL,然后是根结点3,最后是3的右树NULL,所以顺序为N3N。接下来把3看成是2的左子树,逻辑一样为:左子树-根-右子树,3遍历完成代表2的左子树遍历完成,接下来是根结点2,然后是根结点2的右子树NULL,此时顺序为:N3N2N。2作为根结点遍历完成后,表示1的左子树遍历完成,接下来遍历的逻辑是根结点1-1的右子树,把4当成根结点执行同样的逻辑:左子树-根-右子树。

2.3 二叉树的后序遍历 

        接下来的后序遍历的顺序为:左子树、右子树、根。其逻辑与上述相似,只不过顺序做了调整。

        该二叉树的后序遍历顺序为:NN3N2NN5NN641(N表示NULL)。 

2.4 二叉树的层序遍历

        层序遍历顾名思义就是一层一层、自上而下从左到右的遍历,首先从第一层也就是根结点开始,其次是第二层,并且从左边到右边的遍历,以此类推。

        因此层序遍历的顺序为:1 2 4 3 5 6。

        下面使用代码来实现二叉树及各个功能。

3、创建一颗二叉树 

        从二叉树的结构分析可以得出,创建二叉树要满足三个条件:有效数据、指向左孩子的指针,指向右孩子的指针。

        创建二叉树代码如下:

typedef int TreeDataType;//int类型重定义
typedef struct TreeNode
{TreeDataType data;struct TreeNode* left;//指向左孩子指针struct TreeNode* right;//指向右孩子指针
}TNode;TNode* CreatTreeNode(int x)//创建结点
{TNode* treenode = (TNode*)malloc(sizeof(TNode));if (treenode == NULL){perror("CreatTreeNode");return NULL;}treenode->data = x;//给结点赋值treenode->left = NULL;treenode->right = NULL;return treenode;//返回创建树结点的地址
}TNode* CreatTree()//创造二叉树
{//创建结点TNode* n1 = CreatTreeNode(1);TNode* n2 = CreatTreeNode(2);TNode* n3 = CreatTreeNode(3);TNode* n4 = CreatTreeNode(4);TNode* n5 = CreatTreeNode(5);TNode* n6 = CreatTreeNode(6);//TNode* n7 = CreatTreeNode(7);//构建树结点之间的关系n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;//n5->left = n7;return n1;//返回该二叉树的根节点
}

        该二叉树的物理图:

4、递归方法实现二叉树前、中、后遍历 

4.1 实现前序遍历

        前序遍历代码如下:

void PreOrder(TNode* root)//前序遍历
{if (root == NULL){printf("N ");//当递归到NULL时打印并返回Nreturn;}printf("%d ", root->data);//打印根节点PreOrder(root->left);//打印左子树PreOrder(root->right);//打印右子树
}

        因为二叉树是由递归实现的,并且前序遍历的顺序为:根-左子树-右子树。进入函数PreOrder时如果结点root不是空结点,则可以将该结点看成根节点,按照前序遍历的逻辑打印该结点的值,然后继续遍历该结点的左子树,和右子树,当结果为NULL时就会跳出该函数。当结点3的函数走完了,就会收回至结点2的函数,说明结点2的左子树函数完成。

        具体步骤图如下:

4.2 实现中序遍历

        中序遍历的顺序与前序遍历顺序不一样,因此对前序遍历的代码稍作修改即可。

        中序遍历代码如下:

void InOrder(TNode* root)//中序遍历
{if (root == NULL){printf("N ");return;}//相比于前序遍历,把这两个语句的顺序交换了以下InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

        可以发现,中序遍历中的打印根结点的代码与左子树代码只是做了简单的更替便可以实现中序遍历,交换后三个语句的顺序也刚好对应中序遍历的顺序:左子树-根-右子树。

4.3 实现后序遍历 

        经过上述的规律可以得出后序遍历的代码逻辑。

        后序遍历代码如下:

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

5、求二叉树的结点总数

        求二叉树结点的总数,第一步就是要遍历二叉树。因此采用的是递归的方式,因此每次函数调用返回的时候要返回当前结点的个数。

        这里注意的点:当递归的函数返回一个值,是返回给上一层调用该函数的函数,如此层层返回最后返回给根结点函数。

        求二叉树结点总数代码如下:

int BinaryTreeSize(TNode* root)//结点个数
{if (root == NULL)//为空返回0return 0;//递归左右子树return BinaryTreeSize(root->left)+ BinaryTreeSize(root->right) + 1;//若执行到此语句说明root不为空//+1表示把当前的结点记录进去
}

6、求二叉树叶子个数

        把二叉树中没有孩子结点的结点称为叶子结点。

        因此叶子节点的特性是其他节点不具有的,既:左孩子和右孩子都为空。因此当递归至某个结点的时候发现其左孩子和右孩子都为空,则计数+1。

        求二叉树叶子个数代码如下:

int BinaryTreeLeafSize(TNode* root)//叶子个数
{if (root == NULL)//为空则不是叶子结点return 0;if (root->left == NULL && root->right == NULL)//左右孩子都为空则返回1{return 1;}elsereturn BinaryTreeLeafSize(root->left)//递归左子树+ BinaryTreeLeafSize(root->right);//递归右子树
}

7、求第k层结点总数

        比如求该二叉树的第三层结点总数。思路:从上往下看,如果求第三层,可以转换成求结点1的第三层,求结点2和4的第二层,求结点3 5 6 的第一层,都表示为该树的第三层,只是表达不一样。因此当k==1的时候说明这时候是在第k层。

        求第k层结点总数代码如下:

int BinaryTreeLevelKSize(TNode* root, int k)//求第k层结点的总数
{if (root == NULL)return 0;if (k == 1)return 1;//递归函数,k不断-1return BinaryTreeLevelKSize(root->left, k - 1)//递归左子树+ BinaryTreeLevelKSize(root->right, k - 1);//递归右子树
}

8、求二叉树的高度

        思路:先遍历到最底层,然后收回的时候每一层+1,取左子树递归函数的值与右子树递归函数的值的较大值加上该层高度1就是该层的高度。示意图如下:

        二叉树的高度代码如下:

int BinaryTreeHeight(TNode* root)//二叉树高度
{if (root == NULL)return 0;//递归函数int leftHeight = BinaryTreeHeight(root->left);//将左子树的高度存在一个变量中int rightHeight = BinaryTreeHeight(root->right);//将右子树的高度存在一个变量中//取两个变量的较大者加上该层的高度1return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

9、从二叉树中查找值为x的结点

        思路:若找到该节点,则返回该节点的地址,并且用一个指针变量来接收,之后的代码就不需要再运行。

        二叉树查找代码如下:

TNode* BinaryTreeFind(TNode* root, TreeDataType x)//查找值为x的结点
{if (root == NULL)//为空返回NULLreturn NULL;if (root->data == x)//若找到了则返回该结点的地址return root;TNode* xpoi= BinaryTreeFind(root->left, x);//递归左子树,找到了就存放在指针变量xpoi中if (xpoi != NULL)//如果没有找到就不执行if语句,则继续找return xpoi;xpoi= BinaryTreeFind(root->right,x);//递归右子树if (xpoi != NULL)return xpoi;return NULL;//若都没有找到则返回NULL给上层函数
}

10、层序遍历

        层序遍历的逻辑与前、中、后遍历的逻辑不一样,前、中、后遍历用的是递归的逻辑,而层序遍历则是采用非递归的逻辑。

        层序遍历的顺序如上图:1 2 4 3 5 6,他的思路是把树节点的地址放入队列中,这样就能通过对队列节点的解引用找到树结点的地址再解引用找到树结点的值。

        队列的逻辑是先进先出、后进后出, 因此先把根节点1的地址放入队列中,然后出队的时候是先出的1,同时把1的两个孩子的地址入队,此时队列中存放的是2 4,并且下一次出队先将2出掉,同时把2的孩子入队,此时队列里存放的是4 1,如此下去,最后出队的顺序为1 2 4 3 5 6,与层序遍历的顺序一样。

        因此层序遍历的代码涉及队列的创建:

//队列结构体
typedef struct TreeNode* QueueDataType;
typedef struct QNode
{struct QNode* next;QueueDataType data;
}QNode;typedef struct Queue
{struct QNode* head;struct QNode* tail;int size;
}Queue;void QueueInit(Queue* pq)//队列初始化
{assert(pq);pq->head = NULL;pq->tail = NULL;pq->size = 0;
}QNode* BuyNode(QueueDataType x)//创建队列结点
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("BuyNode");return NULL;}newnode->next = NULL;newnode->data = x;return newnode;//返回队列结点的地址
}void QueuePush(Queue* pq, QueueDataType x)//入队
{assert(pq);QNode* newnode = BuyNode(x);if (pq->head == NULL){assert(pq->tail==NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}bool Empty(Queue* pq)//判空
{assert(pq);return pq->head == NULL|| pq->tail==NULL;
}QueueDataType QueueFront(Queue* pq)//显示队头数据
{assert(pq);assert(!Empty(pq));return pq->head->data;
}void QueuePop(Queue* pq)//出队
{assert(pq);assert(!Empty(pq));if (pq->head == pq->tail)//一个节点{free(pq->head);pq->head = pq->tail = NULL;}else//多个节点{QNode* poi = pq->head;pq->head = pq->head->next;free(poi);}pq->size--;}void QueueDestroy(Queue* pq)//释放队列
{assert(pq);QNode* cur = pq->head;while (cur){QNode* poi = cur->next;free(cur);cur = poi;}pq->head = pq->tail = NULL;pq->size = 0;
}//层序遍历
void LevelOrder(TNode* root)
{Queue q;QueueInit(&q);if(root!=NULL)QueuePush(&q, root);while (!Empty(&q)){TNode* front=QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if(front->left)QueuePush(&q, front->left);if(front->right)QueuePush(&q, front->right);}QueueDestroy(&q);
}

11、二叉树的销毁

        由于二叉树是在堆上申请而来的,因此再使用完之后要对申请的空间进行释放。这里选择用后序的方法进行释放,原因是后序的顺序是:左子树-右子树-根,根是最后才释放的,如果用前序遍历释放就会出现先把根释放了,就不好找根的左子树和右子树了,中序遍历也同理。

        二叉树销毁代码如下:

void BinaryTreeDestory(TNode* root)//二叉树销毁
{if (root == NULL)return;//后序遍历BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);
}

12、测试功能

        上述解析了如此多的功能,接下来对其进行测试,观察运行结果。

        测试代码如下:


int main()
{TNode* root = CreatTree();//创建树,并返回根结点PreOrder(root);//前序遍历printf("\ntreesize:%d", BinaryTreeSize(root));//树的结点个数printf("\ntreesize:%d", BinaryTreeSize(root));printf("\nLeafSize:%d", BinaryTreeLeafSize(root));//叶子个数printf("\nLevelKSize:%d", BinaryTreeLevelKSize(root, 3));//第k层结点个数printf("\nheight:%d", BinaryTreeHeight(root));//树的高度TNode* xpoi = BinaryTreeFind(root, 3);//查找结点if (xpoi == NULL)printf("二叉树无该结点\n");elseprintf("\n找到结点:%d", xpoi->data);printf("\n");LevelOrder(root);//层序遍历BinaryTreeDestory(root);//二叉树释放root = NULL;//手动置空return 0;
}

        运行结果:

        从运行结果来看,以上功能均可正常运行。 

结语:

        以上就是关于二叉树以及相关功能的实现与解析,二叉树的重点在于对函数递归的形象理解,本质上二叉树就是运用函数不断递归实现的,看似一小段代码实则可以延长出很多信息。最后希望本文可以给你带来更多的收获,如果本文对你起到了帮助,希望可以动动小指头帮忙点赞👍+关注😎+收藏👌!如果有遗漏或者有误的地方欢迎大家在评论区补充~!!谢谢大家!!

(~ ̄▽ ̄)~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/204201.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【服务器能干什么】二十分钟搭建一个属于自己的 RSS 服务

如果大家不想自己捣鼓,只是想尝尝鲜,可以在下面留言,我后台帮大家开几个账号玩一玩。 哔哩哔哩【高清版本可以点击去吐槽到 B 站观看】:【VPS服务器到底能干啥】信息爆炸的年代,如何甄别出优质的内容?你可能需要自建一个RSS服务!_哔哩哔哩_bilibili 前言 RSS 服务 市…

STM32F103C8T6第7天:

1. 智能小车:让小车动起来(360.64) 硬件接线 B-2A – PB0B-1A – PB1A-1B – PB2A-1A – PB10其余接线参考上官一号小车项目。 cubemx配置 代码(28.smartCar_project1/MDK-ARM) 2. 智能小车:串口控制小…

Vue弹窗的使用与传值

使用element-UI中的Dialog 对话框 vue组件结合实现~~~~ 定义html <div click"MyAnalyze()">我的区划</div><el-dialog title"" :visible.sync"dialogBiomeVisible"><NationalBiome :closeValue"TypeBiome" cl…

ruoyi-plus-vue docker 部署

本文以 ruoyi-vue-plus 5.x docker 部署为基础 安装虚拟机 部署文档 安装docker 安装docker 安装docker-compose 配置idea环境 上传 /doicker 文件夹 到服务器&#xff1b;赋值 777权限 chmod -R 777 /docker idea构建 jar 包 利用 idea 构建镜像; 创建基础服务 docker…

Oracle(2-5)Usage and Configuration of the Oracle Shared Server

文章目录 一、基础知识1、 Server Configurations服务器配置2、Dedicated server process专用服务器进程3、Oracle Shared ServerOracle共享服务器4、Benefits of Shared Server 共享服务器的优点5、Processing a Request 处理请求6、Configuring Shared Server 配置共享服务器…

设计模式-创建型模式-工厂方法模式

一、什么是工厂方法模式 工厂模式又称工厂方法模式&#xff0c;是一种创建型设计模式&#xff0c;其在父类中提供一个创建对象的方法&#xff0c; 允许子类决定实例化对象的类型。工厂方法模式是目标是定义一个创建产品对象的工厂接口&#xff0c;将实际创建工作推迟到子类中。…

Redis报错:JedisConnectionException: Could not get a resource from the pool

1、问题描述&#xff1a; redis.clients.jedis.exceptions.JedisConnectionException: Could not get a resource from the pool 2、简要分析&#xff1a; redis.clients.util.Pool.getResource会从JedisPool实例池中返回一个可用的redis连接。分析源码可知JedisPool 继承了 r…

PyQt6把QTDesigner生成的UI文件转成python源码,并运行

锋哥原创的PyQt6视频教程&#xff1a; 2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~共计18条视频&#xff0c;包括&#xff1a;2024版 PyQt6 Python桌面开发 视频教程(无废话版…

NSGA-II求解微电网多目标优化调度(MATLAB)

一、NSGA-II简介 NSGA-Ⅱ算法是Kalyanmoy Deb等人于 2002年在 NSGA 的基础上提出的&#xff0c;它比 NSGA算法更加优越&#xff1a;它采用了快速非支配排序算法&#xff0c;计算复杂度比 NSGA 大大的降低&#xff1b;采用了拥挤度和拥挤度比较算子&#xff0c;代替了需要指定的…

python实现自动刷平台学时

背景 前一阵子有个朋友让我帮给小忙&#xff0c;因为他每学期都要看视频刷学时&#xff0c;一门平均需要刷500分钟&#xff0c;一学期有3-4门需要刷的。 如果是手动刷的话&#xff0c;比较麻烦&#xff0c;能否帮他做成自动化的。搞成功的话请我吃饭。为了这顿饭&#xff0c;咱…

Python语言学习笔记之三(字符编码)

本课程对于有其它语言基础的开发人员可以参考和学习&#xff0c;同时也是记录下来&#xff0c;为个人学习使用&#xff0c;文档中有此不当之处&#xff0c;请谅解。 什么是字符编码 计算机从本质上来说只认识二进制中的0和1&#xff0c;字符编码(Character Encoding) 是一种将…

Android Bitmap 模糊效果实现 (二)

文章目录 Android Bitmap 模糊效果实现 (二)使用 Vukan 模糊使用 RenderEffect 模糊使用 GLSL 模糊RS、Vukan、RenderEffect、GLSL 效率对比 Android Bitmap 模糊效果实现 (二) 本文首发地址 https://blog.csdn.net/CSqingchen/article/details/134656140 最新更新地址 https:/…

便利高效双赢:无人机油气管道巡检全面升级

我国庞大的油气管道网络&#xff0c;包括原油、成品和天然气管道&#xff0c;因为地理区域广泛、建设年代久远、安全事故频发等现实因素&#xff0c;对管道的安全巡护与管理提出了更高的需求。在这一背景下&#xff0c;传统的人工巡护方式显然已经难以满足对高、精、准的要求。…

antd vue a-select 下拉框位置偏移

问题 下拉框未固定 原因 select下拉框的定位是根据body定位 解决方法 在select 标签中添加&#xff1a; :getPopupContainer"(triggerNode) > (triggerNode.parentElement)" :getPopupContainer"(triggerNode) > (triggerNode.parentElement)"…

Linux 面试题(一)

目录 1、绝对路径用什么符号表示&#xff1f;当前目录、上层目录用什么表示&#xff1f;主目录用什么表示? 切换目录用什么命令&#xff1f; 2、怎么查看当前进程&#xff1f;怎么执行退出&#xff1f;怎么查看当前路径&#xff1f; 3、怎么清屏&#xff1f;怎么退出当前命…

【Spring Boot】如何在Linux系统中快速启动Spring Boot的jar包

在Linux系统中先安装java的JDK 然后编写下列service.sh脚本&#xff0c;并根据自己的需求只需要修改export的log_path、exec_cmd参数即可 # 配置运行日志输出的路径 export log_path/usr/local/project/study-pro/logs # 当前服务运行的脚本命令 export exec_cmd"nohup /u…

redis-cluster集群

redis3.0引入的分布式存储方案 集群由多个node节点组成&#xff0c;redis数据分布在这些节点之中&#xff0c;在集群之中分为主节点和从节点 数据流程图 redis-cluster集群的工作模式 集群模式当中&#xff0c;主从一一对应&#xff0c;数据写入和读取与主从模式一样&#x…

<Linux> 文件理解与操作

目录 前言&#xff1a; 一、关于文件的预备知识 二、C语言文件操作 1. fope 2. fclose 3. 文件写入 3.1 fprintf 3.2 snprintf 三、系统文件操作 1. open 2. close 3. write 4. read 四、C文件接口与系统文件IO的关系 五、文件描述符 1. 理解文件描述符 2. 文…

蓝桥杯官网算法赛(蓝桥小课堂)

问题描述 蓝桥小课堂开课啦&#xff01; 海伦公式&#xff08;Herons formula&#xff09;&#xff0c;也称为海伦-秦九韶公式&#xff0c;是用于计算三角形面积的一种公式&#xff0c;它可以通过三条边的长度来确定三角形的面积&#xff0c;而无需知道三角形的高度。 海伦公…

同旺科技 USB 转 RS-485 适配器 -- 隔离型

内附链接 1、USB 转 RS-485 适配器 隔离版主要特性有&#xff1a; ● 支持USB 2.0/3.0接口&#xff0c;并兼容USB 1.1接口&#xff1b; ● 支持USB总线供电&#xff1b; ● 支持Windows系统驱动&#xff0c;包含WIN10 / WIN11 系统32 / 64位&#xff1b; ● 支持Windows …