数据结构【链试结构二叉树】

 


🌟个人主页:落叶

目录

 ​编辑

实现链式结构⼆叉树

前中后序遍历:

遍历规则

代码实现

前序遍历:

中序遍历:

后序遍历:

图解遍历:

函数递归栈帧图:

结点个数以及高度等

【⼆叉树】结点个数

【二叉树】叶子节点个数

【二叉树】第k层节点个数

【二叉树】的深度/⾼度

【二叉树】查找值为x的结点 

【二叉树】销毁

层序遍历

判断是否为完全二叉树


🔥摘要:设⼆叉树的根结点所在层数 为1,层序遍历就是从所在⼆叉树的根结点出发,⾸先访问第⼀层的树根结点,然后从左到右访问第2 层上的结点,接着是第三层的结点,以此类推,⾃上⽽下,⾃左⾄右逐层访问树的结点的过程就是层 序遍历。根结点的左⼦树和右⼦树分别⼜是由⼦树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的,因此 ⼆叉树定义是递归式的,后序链式⼆叉树的操作中基本都是按照该概念实现的。回顾⼆叉树的概念,⼆叉树分为空树和⾮空⼆叉树,⾮空⼆叉树由根结点、根结点的左⼦树、根结点 的右⼦树组成的。根结点、左⼦树、右⼦树。

实现链式结构⼆叉树

⽤链表来表⽰⼀棵⼆叉树,即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组 成,数据域和左右指针域,左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址, 其结构如下:

创建二叉树数据:

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int data;
typedef struct Tree
{int arr;    //数值struct Tree* zuo;//左孩子struct Tree* you;//右孩子
}BT;

⼆叉树的创建⽅式⽐较复杂,为了更好的步⼊到⼆叉树内容中,我们先⼿动创建⼀棵链式⼆叉树

我们进行连接后就成下面这个二叉树


当然我们也可以这样看

//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;}int main()
{p();return 0;
}

回顾⼆叉树的概念,⼆叉树分为空树和⾮空⼆叉树,⾮空⼆叉树由根结点、根结点的左⼦树、根结点 的右⼦树组成的

根结点的左⼦树和右⼦树分别⼜是由⼦树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的,因此 ⼆叉树定义是递归式的,后序链式⼆叉树的操作中基本都是按照该概念实现的。

前中后序遍历:

⼆叉树的操作离不开树的遍历,我们先来看看⼆叉树的遍历有哪些⽅式

遍历规则

按照规则,⼆叉树的遍历有:前序/中序/后序的递归结构遍历:

(1)前序遍历(PreorderTraversal亦称先序遍历):访问根结点的操作发⽣在遍历其左右⼦树之前

访问顺序为:根结点、左⼦树、右⼦树

(2)中序遍历(InorderTraversal):访问根结点的操作发⽣在遍历其左右⼦树之中(间)

访问顺序为:左⼦树、根结点、右⼦树

(3)后序遍历(PostorderTraversal):访问根结点的操作发⽣在遍历其左右⼦树之后

访问顺序为:左⼦树、右⼦树、根结点

代码实现
前序遍历:

访问顺序为:根结点、左⼦树、右⼦树

//前序遍历-(根-左-右)
void qian(BT* root)
{if (root == NULL){return;}printf("%d ", root->arr);//左子树qian(root->zuo);//右子树qian(root->you);
}



结果:

//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;qian(n1);printf("\n");}int main()
{p();return 0;
}

中序遍历:

访问顺序为:左⼦树、根结点、右⼦树

//中序遍历-(左-根-右)
void zho(BT* root)
{if (root == NULL){return;}//左子树zho(root->zuo);printf("%d ", root->arr);//右子树zho(root->you);
}



结果:

//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;/*qian(n1);printf("\n");*/zho(n1);printf("\n");}int main()
{p();return 0;
}

后序遍历:

访问顺序为:左⼦树、右⼦树、根结点

//后序遍历
void ho(BT* root)
{if (root == NULL){return;}//左子树ho(root->zuo);//右子树ho(root->you);printf("%d ", root->arr);
}



结果:

//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;/*qian(n1);printf("\n");*//*zho(n1);printf("\n");*/ho(n1);}int main()
{p();return 0;
}

图解遍历:

以前序遍历为例:


函数递归栈帧图:


前序遍历结果:123456

中序遍历结果:321546

后序遍历结果:315641


结点个数以及高度等
【⼆叉树】结点个数

// ⼆叉树结点个数 
int BinaryTreeSize(BT* root)
{if (root == NULL){return 0;}//                左子树                     右子树return 1+ BinaryTreeSize(root->zuo)+ BinaryTreeSize(root->you);
}



结果:

//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;/*qian(n1);printf("\n");*//*zho(n1);printf("\n");*///ho(n1);// ⼆叉树结点个数 printf("size:%d \n", BinaryTreeSize(n1));}int main()
{p();return 0;
}

【二叉树】叶子节点个数

// ⼆叉树叶⼦结点个数 
int BinaryTreeLeafSize(BT* root)
{if (root == NULL){return 0;}//左子树和右子树都等于空,就是叶子节点if (BinaryTreeLeafSize(root->zuo) == NULL && BinaryTreeLeafSize(root->you) == NULL){return 1;}return BinaryTreeLeafSize(root->zuo) + BinaryTreeLeafSize(root->you);
}



结果:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;/*qian(n1);printf("\n");*//*zho(n1);printf("\n");*///ho(n1);// ⼆叉树结点个数 //printf("size:%d \n", BinaryTreeSize(n1));//叶子节点个数printf("叶子节点:%d\n", BinaryTreeLeafSize(n1));}int main()
{p();return 0;
}

【二叉树】第k层节点个数

// ⼆叉树第k层结点个数 
int BinaryTreeLevelKSize(BT* root, int k)
{if (root == NULL){return 0;}//k等于1了就返回1if (k == 1){return 1;}return BinaryTreeLevelKSize(root->zuo, k - 1) + BinaryTreeLevelKSize(root->you, k - 1);
}



结果:

这里加了2个节点5和6,就和上面那张图一样了。

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;/*qian(n1);printf("\n");*//*zho(n1);printf("\n");*///ho(n1);// ⼆叉树结点个数 //printf("size:%d \n", BinaryTreeSize(n1));// 叶子节点个数//printf("叶子节点:%d\n", BinaryTreeLeafSize(n1));//k层节点个数printf("k: %d \n", BinaryTreeLevelKSize(n1, 3));}int main()
{p();return 0;
}

【二叉树】的深度/⾼度

//⼆叉树的深度/⾼度
int BinaryTreeDepth(BT* root)
{if (root == NULL){return 0;}//遍历左子树,把值给zuoint zuo = BinaryTreeDepth(root->zuo);//遍历右子树,把值给youint you = BinaryTreeDepth(root->you);//进行判断return zuo > you ? zuo + 1:you + 1;
}



结果:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;/*qian(n1);printf("\n");*//*zho(n1);printf("\n");*///ho(n1);// ⼆叉树结点个数 //printf("size:%d \n", BinaryTreeSize(n1));// 叶子节点个数//printf("叶子节点:%d\n", BinaryTreeLeafSize(n1));k层节点个数//printf("k: %d \n", BinaryTreeLevelKSize(n1, 3));//⼆叉树的深度/⾼度printf("高度:%d \n", BinaryTreeDepth(n1));}int main()
{p();return 0;
}

【二叉树】查找值为x的结点 

// ⼆叉树查找值为x的结点 
BT* BinaryTreeFind(BT* root, data x)
{if (root == NULL){return NULL;}//等于x,返回当前节点if (root->arr == x){return root;}//zuo接收节点BT* zuo = BinaryTreeFind(root->zuo, x);if (zuo){//返回节点return zuo;}//you接收节点BT* you = BinaryTreeFind(root->you, x);if (you){//返回节点return you;}
}


左子树找不到,就找右子树


结果:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
//申请空间
BT* koj(data x)
{//申请节点BT* tab = (BT*)malloc(sizeof(BT));if (tab == NULL){perror("malloic");exit(1);}tab->arr = x;tab->zuo= tab->you = NULL;return tab;
}
void p()
{//创建节点BT* n1 = koj(1);BT* n2 = koj(2);BT* n3 = koj(3);BT* n4 = koj(4);//BT* n5 = koj(5);//BT* n6 = koj(6);//进行连接n1->zuo = n2;n1->you = n3;n2->zuo = n4;//n2->you = n5;//n3->zuo = n6;/*qian(n1);printf("\n");*//*zho(n1);printf("\n");*///ho(n1);// ⼆叉树结点个数 //printf("size:%d \n", BinaryTreeSize(n1));// 叶子节点个数//printf("叶子节点:%d\n", BinaryTreeLeafSize(n1));k层节点个数//printf("k: %d \n", BinaryTreeLevelKSize(n1, 3));⼆叉树的深度/⾼度//printf("高度:%d \n", BinaryTreeDepth(n1));// ⼆叉树查找值为x的结点 BT* tab = BinaryTreeFind(n1, 4);printf("%s\n", tab == NULL ? "没找到" : "找到了");}int main()
{p();return 0;
}

【二叉树】销毁



// ⼆叉树销毁
void BinaryTreeDestory(BT** root)
{if (*root == NULL){return;}//二级指针,需要传一级指针地址BinaryTreeDestory(&(*root)->zuo);BinaryTreeDestory(&(*root)->you);//释放空间free(*root);*root = NULL;
}

图解析:


结果:

我们可以看到全部销毁了。


层序遍历

除了先序遍历、中序遍历、后序遍历外,还可以对⼆叉树进⾏层序遍历。设⼆叉树的根结点所在层数 为1,层序遍历就是从所在⼆叉树的根结点出发,⾸先访问第⼀层的树根结点,然后从左到右访问第2 层上的结点,接着是第三层的结点,以此类推,⾃上⽽下,⾃左⾄右逐层访问树的结点的过程就是层 序遍历

实现层序遍历需要额外借助数据结构:队列


创建队列,初始化,把根节点入队列

循环队列不为空,取队头打印,出队头。

然后判断左子树和右子树,是不是空,不是空就入队列。

销毁队列。

//层序遍历
//借助数据结构--队列
void LevelOrder(BT* root)
{Queue add;//初始化Queuecsh(&add);//入数据Queue_ruwei(&add, root);while (!buer(&add)){//取队头-打印BT* tab = qto(&add);printf("%d ", tab->arr);//出队Queue_chu(&add);//判断是不是空, 队头节点的左右孩子入,队列if (tab->zuo){Queue_ruwei(&add, tab->zuo);}if (tab->you){Queue_ruwei(&add, tab->you);}}//队列销毁Queuexiaoh(&add);
}

结果:


判断是否为完全二叉树


注意:

如果是完全二叉树,跳出循环之后队列里都是NULL。

如果不是完全二叉树,跳出循环之后队列里,还有非空节点。

思路:

创建一个队列,把根节点入队列,循环队列里不为空。

取队头节点,然后出队,判断这个节点是不是空,是空跳出循环。

不是空,左子树和右子树入队列。

是完全二叉树的话剩下的都是空,

循环取出队头数据,出队,进行判断,不等于空的话还有非空节点,那就是不完全二叉树了,返回false。

最后循环都为空,是完全二叉树,返回true。


bool pdercs(BT* root)
{Queue add;//队列初始化Queuecsh(&add);//入队列Queue_ruwei(&add, root);while (!buer(&add)){//取队头数据BT* tab =  qto(&add);//出队Queue_chu(&add);if (tab == NULL){//等于空结束循环break;}//不为空让左右子树入队列//左子树_入队列Queue_ruwei(&add, tab->zuo);//右子树_入队列Queue_ruwei(&add, tab->you);}//循环判断队列,有一个数值不是完全二叉树,都是NULL就是完全二叉树while (!buer(&add)){//取队头BT* app = qto(&add);//出队Queue_chu(&add);//判断如果还有非空节点,返回falseif (app != NULL){Queuexiaoh(&add);return false;}}//循环完,说明队列里都是NULL,是完全二叉树,返回true//队列销毁Queuexiaoh(&add);return true;
}

结果:

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

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

相关文章

Oracle归档日志满了,导致程序打不开,如何解决。

加油&#xff0c;新时代打工人&#xff01; 归档日志错误&#xff0c;登录不上&#xff0c;只能用system 角色登录&#xff0c; 错误提示 oracle 错误257 archiver error connect internal only until freed 解决cmd进入rman RMAN&#xff08;Recovery Manager&#xff09;是一…

数学基础(六)

一、分布 正态分布 二项式分布 均匀分布 卡方分布 二、核函数 核函数的目的&#xff1a; 将低维数据转换为高维数据 线性核函数&#xff1a; Linear核函数对数据不做任何变换 当特征已经比较丰富了&#xff0c;样本数据量巨大&#xff0c;需要进行实时得出结果时进行使用…

小程序学习day11-生命周期函数、组件所在页面的生命周期、自定义组件的插槽、自定义组件的父子通信

40、自定义组件&#xff08;续&#xff09;&#xff08;续&#xff09; &#xff08;10&#xff09;生命周期函数 1&#xff09;小程序里的全部生命周期函数 ①created&#xff08;在组件刚被创建时执行&#xff09;&#xff08;被创建&#xff0c;但未被放入页面&#xff09…

Servlet---axios框架 ▎路由守卫

前言 在现代Web应用中&#xff0c;前端和后端通常分离&#xff0c;前端使用框架&#xff08;如Vue.js、React&#xff09;与后端服务交互。Servlet是Java EE中处理HTTP请求的重要组成部分&#xff0c;能够生成动态Web内容。 Axios是一个基于Promise的HTTP客户端&#xff0c;简…

手机mkv转换mp4:轻松实现视频格式兼容

如今手机已成为我们日常生活中不可或缺的伴侣&#xff0c;而视频文件则是我们享受娱乐、获取信息的重要来源。然而&#xff0c;由于不同设备和平台对视频格式的支持各有不同&#xff0c;我们有时会遇到无法在手机上播放某些视频文件的问题。 mkv是一种常见的视频格式&#xff…

AI赋能奥维云网数字生态大会,瞰见智慧家庭市场新未来

近日&#xff0c;主题为“智无界鉴未来”的“奥维云网2024数字生态大会”在杭州盛大开启。 据「TMT星球」了解&#xff0c;本次大会邀请到了国务院发展研究中心专家做政策解读&#xff0c;得到了中国电子视像行业协会、中国家用电器协会、中国五金制品协会、中国家用电器商业协…

如何使用ssm实现保险业务管理系统设计与实现

TOC ssm131保险业务管理系统设计与实现jsp 绪论 1.1 研究背景 当前社会各行业领域竞争压力非常大&#xff0c;随着当前时代的信息化&#xff0c;科学化发展&#xff0c;让社会各行业领域都争相使用新的信息技术&#xff0c;对行业内的各种相关数据进行科学化&#xff0c;规…

使用Python做一个脚本自动化机器人(二)

刚发现一个好用的Python库DrissionPage&#xff0c;使用该库不区分浏览器&#xff0c;也无需下载driver文件。 import logging from DrissionPage import WebPage from DrissionPage import ChromiumPage,ChromiumOptionsclass BaiduPage():# 创建对象page ChromiumPage()# 访…

【深度学习与NLP】——最全环境配置总指南

目录 一、Anaconda 的环境准备 1.下载和安装 1.1. 下载 1.1.1. 官网下载 1.1.2. 镜像站下载&#xff08;官网下载速度慢可选&#xff09; 1.2. 安装 2. 环境配置 2.1 Windows 平台 2.2 MacOS 和 Linux 平台 3. 环境验证 3.1 Windows 平台 3.2 MacOS 和 Linux 平台 …

漏洞挖掘 | 浅谈一次edusrc文件上传成功getshell

0x1 前言 这里记录一下我在微信小程序挖人社局等一些人力资源和社会保障部信息中心漏洞&#xff0c;人社这类漏洞相对于web应用端的漏洞来讲要好挖很多&#xff0c;里面的WAF过滤等一些验证也少。比如你在开始学习src漏洞挖掘&#xff0c;就可以从微信小程序下手。 一般像这类…

C#为复杂属性提供下拉式编辑框和弹出式编辑框

一.为属性提供编辑类 弹出式和下拉式是如何实现的呢&#xff0c;这需要为属性提供一个专门的编辑类。.Net为我们提供了一个System.Drawing.Design.UITypeEditor类&#xff0c;它是所有编辑类的基类&#xff0c;从他继承出了诸如ColorEditor、FontEditor的类&#xff0c;因此我们…

B. 不知道该叫啥

题意&#xff1a;求长度为n的数列方案数&#xff0c;数列需满足两个条件&#xff1a;1.均为正整数。2.相邻两个数乘积不能超过m 思路&#xff1a;考虑dp。 设表示前i个点以j结尾的方案数&#xff0c;则有&#xff1a; 可以得出&#xff1a; 双指针数论分块解决。把每个m/i相…

基于STM32开发的智能水箱液位控制系统

目录 引言环境准备工作 硬件准备软件安装与配置系统设计 系统架构硬件连接代码实现 系统初始化液位监测与控制水泵控制与状态显示Wi-Fi通信与远程监控应用场景 家庭用水系统的液位控制工业水箱的液位管理常见问题及解决方案 常见问题解决方案结论 1. 引言 智能水箱液位控制系…

一种简单视觉处理

背景 网友说他有个芯片的图&#xff0c;识别不出管脚的位置 俺就写了一个代码&#xff0c;识别管脚的位置&#xff0c;先看结果。 代码 识别图片&#xff0c;并显示结果&#xff0c;对于结果位置使用红色标出 PT pt new PT();pt.Find(bmp);Bitmap bmp_tmp new Bitmap(bmp);…

GPT-4、Claude 3 Opus 和 Gemini 1.0 Ultra 挑战控制工程的新领域

介绍 论文地址&#xff1a;https://arxiv.org/abs/2404.03647 近年来&#xff0c;GPT-4、Claude 3 Opus 和 Gemini 1.0 Ultra 等大规模语言模型&#xff08;LLM&#xff09;迅速发展&#xff0c;展示了它们解决复杂问题的能力。LLM 的这些发展在多个领域都有潜在的应用前景。…

Adobe After Effects的插件--------CC Ball Action

CC Ball Action是粒子效果器,其将2D图层变为一个个由3D小球构成的图层。它是AE内置的3D插件。 使用条件 使用该插件的图层需是2D图层。 我们以一张图片素材为例: 给图片图层添加CC Ball Action效果控件,然后新建一个摄像机(利用摄像机旋转、平移、推拉工具,方便在各个角…

探究Python中的函数与模块

一、引言 随着程序的复杂度增加&#xff0c;代码的组织与重用性就显得尤为重要。为了编写更加结构化、易于维护的代码&#xff0c;函数和模块的使用是必不可少的。 函数是Python中最基本的代码组织形式&#xff0c;通过将代码封装成函数&#xff0c;我们可以实现代码的重用、…

C++不同数据类型连接成一个字符串

在C中数据连接的方式使用号进行连接。 1.都是字符型时直接使用连接几个字符串&#xff1b; 2.不是字符类型时&#xff0c;要用to_string函数转换后再连接。

【C语言】浮点型数据在内存中的储存

浮点型数据在内存中的储存 文章目录 浮点型数据在内存中的储存引例概念提出浮点型数据储存规定对于有效数字M的特别规定对于指数E的特别规定指数E的储存指数E的读取 利用规则解释原因 在之前学习过整形数据在内存中的储存后&#xff0c;浮点型数据在内存中的储存又会怎样呢&…

android 实现简易音乐播放器

音乐App 源代码 &#xff1a; 简易音乐APP源代码 1、简介 一个简易的音乐APP&#xff0c;主要练习对四大组件的应用。感兴趣的可以看看。 播放界面如下&#xff1a; 歌曲列表界面如下&#xff1a; 项目结构如下&#xff1a; 接下来将对代码做详细介绍&#xff1a; 2、Musi…