【数据结构】二叉树的深度理解


🍬个人主页:Yanni.—

🌈数据结构:Data Structure.​​​​​​

🎂C语言笔记:C Language Notes

前言

在之前学习了二叉树的基本概念,但二叉树有着更深入知识理解,这篇文章可以帮助大家在面临考试,刷题的时候大有帮助!!!

目录

前言

二叉树的性质

二叉树的储存结构

顺序储存

链式储存

二叉树链式结构的实现

二叉树链式结构的遍历

前序遍历的实现

中序遍历的实现

后序遍历的实现

二叉树的层序遍历

基础思路

代码实现

Text.c

Queue.h

Queue.c

二叉树结点计算 

全局变量法

传指针法


二叉树的性质

1. 若规定根节点的层数为1,则一棵非空二叉树的i层上最多有2^(i-1) 个结点.
2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2^h- 1.
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0=n2
+1
4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度h=LogN

二叉树的储存结构

二叉树的储存结构一般使用两种结构来存储,一种顺序结构,一种链式结构。

顺序储存

顺序结构存储就是使用数组来存储 ,一般使用数组 只适合表示完全二叉树,因为不是完全二叉树
会有空间的浪费。而现实中使用中只有堆才会使用数组来存储,二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。

链式储存

二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。
通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩 子和右孩子所在的链结点的存储地址 。
链式结构又分为二叉链和三叉链,当前我们学习中一般都 是二叉链,当我们学到高阶数据结构如红黑树等会用到三叉链。
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* pLeft;   // 指向当前节点左孩子struct BinTreeNode* pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{struct BinTreeNode* pParent; // 指向当前节点的双亲struct BinTreeNode* pLeft;   // 指向当前节点左孩子struct BinTreeNode* pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
};

二叉树链式结构的实现

二叉树链式结构的遍历

所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访
问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一,是二叉树上进行
其它运算之基础。  
前序/ 中序 / 后序的递归结构遍历:是根据访问结点操作发生位置命名
1. NLR:前序遍历 (Preorder Traversal 亦称先序遍历 )——访问根结点的操作发生在遍历其左右
子树之前。
2. LNR:中序遍历 (Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中
(间)。
3. LRN:后序遍历 (Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根,所以 N(Node )、 L(Left subtree )和 R(Right subtree)又
可解释为根、根的左子树和根的右子树。 NLR LNR LRN分别又称为先根遍历、中根遍历和后根
遍历。
前序遍历的实现

前序遍历的遍历顺序是,根->左子树->右子树。

                                          

从图中可以看出最后遍历出数据的顺序是A B D G H C E I F。

仔细观察可以发现,这种图类似与递归算法。所以在实现二叉树的遍历时可以用递归算法来实现。

void PrevOrder(BTNode* root)
{if (root == NULL){printf("NULL");return;}printf("%d", root->val);PrevOrder(root->Left);PrevOrder(root->Right);
}
中序遍历的实现

中序遍历的遍历顺序是,左子树->根->右子树。

                              

从图中可以看出最后遍历出数据的顺序是G D H B A E I C F。

同样我们利用递归算法来实现它。

void InOrder(BTNode* root)
{if (root == NULL){printf("NULL");return;}InOrder(root->Left);printf("%d", root->val);InOrder(root->Right);}
后序遍历的实现

中序遍历的遍历顺序是,左子树->右子树>根。

                                

从图中可以看出最后遍历出数据的顺序是G H D B A I E F C 。

同样我们利用递归算法来实现它。

void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL");return;}PostOrder(root->Left);PostOrder(root->Right);printf("%d", root->val);}

二叉树的层序遍历

除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。
设二叉树的 根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问 。树的结点的过程就是层序遍历。  

基础思路

                    

层序遍历的实现需要利用之前学到的队列的知识,通过队列的本质(先进先出)来一层一层的访问二叉树的每个结点。
如图所示
当A拿出来时,A的左子树B和右子树C进去队列

当B拿出来时,B的左子树C和右子树D进去队列

当C拿出来时,C的左子树F和右子树G进入队列

依次类推.....最终一层一层的拿出来。

代码实现

Text.c
#include<stdio.h>
#include<stdlib.h>
#include"Queue.h"typedef int BTNodeDate;
typedef struct BinatyTreeNode
{struct BinatyTreeNode* Left;struct BinatyTreeNode* Right;BTNodeDate val;            
}BTNode;
void LevelOrder(BTNode* root)//层序遍历
{Queue q;QueueInit(&q);if(root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d", front->val);if (front->Left){QueuePush(&q, front->Left);}if (front->Right){QueuePush(&q, front->Right);}}printf("\n");QueueDestroy(&q);
}
int main()
{BTNode* A = (BTNode*)malloc(sizeof(BTNode));A->Left = NULL;A->Right = NULL;A->val = 1;BTNode* B = (BTNode*)malloc(sizeof(BTNode));B->Left = NULL;B->Right = NULL;B->val = 2;BTNode* C = (BTNode*)malloc(sizeof(BTNode));C->Left = NULL;C->Right = NULL;C->val = 3;BTNode* D = (BTNode*)malloc(sizeof(BTNode));D->Left = NULL;D->Right = NULL;D->val = 4;BTNode* E = (BTNode*)malloc(sizeof(BTNode));E->Left = NULL;E->Right = NULL;E->val = 5;A->Left = B;A->Right = C;B->Left = D;B->Right = E;/*PostOrder(A);printf("\n");*/LevelOrder(A);return 0;
}
Queue.h
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
struct BinatyTreeNode;//前置声明typedef struct BinatyTreeNode* QDataType;
//表示队列节点的定义
typedef struct QListNode
{struct QListNode* next;QDataType val;
}QNode;
//队列的结构
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;//初始化队列
void QueueInit(Queue* q);
//队尾入队列
void QueuePush(Queue* q,QDataType x);
//队头出队列
void QueuePop(Queue* q);
//获取队列头部元素
QDataType QueueFront(Queue* q);
//获取队列尾部元素
QDataType QueueBack(Queue* q);
//获取队列中有效元素个数
int QueueSize(Queue* q);
//检验队列是否为空,如果为空则返回非零结果,如果非空则返回0
int QueueEmpty(Queue* q);
//销毁队列
void QueueDestroy(Queue* q);
Queue.c
#include"Queue.h"
//初始化队列
void QueueInit(Queue* q)
{assert(q);q->head = q->tail = NULL;q->size = 0;
}
//队尾入队列
void QueuePush(Queue* q, QDataType x)
{assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL)//考虑newnode为空的情况{printf("malloc fail!!!");exit(1);}newnode->next = NULL;newnode->val = x;if (QueueEmpty(q))//队列为空{q->head = q->tail = newnode;}else {           //队列不为空q->tail->next = newnode;q->tail = newnode;}q->size++;//插入数据之后不要忘了把size++
}//队头出队列
void QueuePop(Queue* q)
{assert(q);if (q->head->next == NULL){free(q->head);q->head = q->tail = NULL;}else {QNode* next = q->head->next;free(q->head);q->head = next;}q->size--;
}
//获取队列头部元素
QDataType QueueFront(Queue* q)
{assert(q);assert(q->head);return q->head->val;
}
//获取队列尾部元素
QDataType QueueBack(Queue* q)
{assert(q);assert(q->tail);return q->tail->val;
}
//获取队列中有效元素个数
int QueueSize(Queue* q)
{assert(q);return q->size;
}
//检验队列是否为空,如果为空则返回非零结果,如果非空则返回0
int QueueEmpty(Queue* q)
{assert(q);return q->size == 0;
}
//销毁队列
void QueueDestroy(Queue* q)
{assert(q);QNode* pcur = q->head;while (pcur){QNode* next = pcur->next;free(q->head);pcur = next;}q->head = q->tail = NULL;q->size = 0;
}

二叉树结点计算 

全局变量法
int size = 0;
void TreeSize(BTNode* root)//计算结点个数
{if (root == NULL){return;}size++;TreeSize(root->Left);TreeSize(root->Right);
}
传指针法

在参数传参的时候,我们要记住传值不改变值,传地址才会改变值。

void TreeSize(BTNode* root,int* psize)
{if (root == NULL){return;}(*psize)++;TreeSize(root->Left,psize);TreeSize(root->Right,psize);
}

好啦,这就是今天学习的分享啦!看到希望大家的三连呀!

如果有不当之处,欢迎大佬指正!

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

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

相关文章

使用Obsidian实现Anki快速制卡

文章目录 前言准备双双启用遇到问题查看是什么问题解决问题 开始使用使用前的一些设置快速制卡 前言 我现在使用 Anki 的同时也使用 Obsidian&#xff0c;正好可以通过插件来让这两个十分好用的软件实现联动。 在 Obsidian 中实现 Anki 的快速制卡。 准备 首先要在这两个软…

原型制作 | 歌词与进度条的位置呼应

在之前的案例里面咱们做过了歌词滚动的效果&#xff0c;具体效果是这样的&#xff0c;点击播放按钮&#xff0c;歌词开始滚动&#xff1b;点击暂停按钮&#xff0c;歌词停止滚动&#xff0c;再次点击播放&#xff0c;歌词会继续滚动&#xff1b;一直播放直到结束&#xff0c;歌…

java常见面试题汇总

&#x1f30f;个人博客主页&#xff1a;意疏-CSDN博客 希望文章能够给到初学的你一些启发&#xff5e; 如果觉得文章对你有帮助的话&#xff0c;点赞 关注 收藏支持一下笔者吧&#xff5e; 阅读指南&#xff1a; 开篇说明一、封装 继承 多态1.封装2.继承3.多态 二、什么是重载…

【前端】VUE 在线运行 模拟器 通过字符串动态渲染页面 可以灵活使用

【前端】VUE2 在线运行 模拟器 通过字符串动态渲染页面 可以灵活使用 <template><div><!-- 这里是动态组件--><component :is"component"></component><!-- 这里是动态组件--><br /><br /><br />可…

Gitlab添加ssh秘钥download项目

1. 查看 、设置 git 用户名和邮箱 git config user.namegit config user.email git config --global user.name 用户名git config --global user.email 邮箱 2. 查看本地是否有ssh秘钥 秘钥默认放在C:\Users\用户\.ssh\目录下&#xff0c;进入这个目录&#xff0c;如果有 …

elasticsearch的高亮查询三种模式查询及可能存在的问题

目录 高亮查询使用介绍 高亮参数 三种分析器 可能存在的查询问题 fvh查询时出现StringIndexOutOfBoundsException越界 检索高亮不正确 参考文档 高亮查询使用介绍 Elasticsearch 的高亮&#xff08;highlight&#xff09;可以从搜索结果中的一个或多个字段中获取突出显…

社区维修平台

TOC springboot0751社区维修平台 第一章 绪 论 1.1背景及意义 系统管理也都将通过计算机进行整体智能化操作&#xff0c;对于社区维修平台所牵扯的管理及数据保存都是非常多的&#xff0c;例如住户管理、社区公告管理、维修工管理、维修订单管理、接单信息管理、订单信息管…

谁将解锁储能的未来?迈威通信邀您共探EESA储能展的秘密

九月金秋&#xff0c;硕果盈枝&#xff0c;迈威通信诚挚邀请您共赴一场科技盛宴——第三届EESA储能展&#xff0c;时间锁定9月2日至4日&#xff0c;地点&#xff1a;国家会展中心(上海)&#xff0c;一场关于绿色能源、智慧储能的梦幻之旅即将启航&#xff01; 您准备好迎接未来…

利用大型语言模型协作提升甲状腺结节超声诊断的一致性和准确性| 文献速递-基于深度学习的癌症风险预测与疾病预后应用

Title 题目 Collaborative Enhancement of Consistency and Accuracy in US Diagnosis of Thyroid Nodules Using Large Language Models 利用大型语言模型协作提升甲状腺结节超声诊断的一致性和准确性 Background 背景 Large language models (LLMs) hold substantial …

Redis内存管理

Redis使用Jemalloc(默认编译)来进行内存的管理&#xff1a; Jemalloc将内存分成许多不同的区域&#xff0c;每个区域成为arena&#xff0c;areana之间相互独立。Jemalloc通过创建多个arena来减少线程申请内存的操作冲突。一般arena数量为cpu数量*4. arena以chunk为单位向操作…

FPGA 综合笔记

仿真时阻塞赋值和非阻塞赋值 Use of Non-Blocking Assignment in Testbench : Verilog Use of Non-Blocking Assignment in Testbench : Verilog - Stack Overflow non-blocking assignment does not work as expected in Verilog non-blocking assignment does not work a…

Python使用QtSide6(PyQt)编写界面

1、安装QtSide6 开始菜单cmd 创建虚拟环境 python -m venv env2 进入虚拟环境 call env2/scripts/activate 安装Pyside6 pip install Pyside6 2、设计Qt界面 打开designer.exe&#xff0c;设计界面 点击菜单【窗体】【View Python Code...】&#xff0c;点击【全部复制】…

HarmonyOs透明弹窗(选择照片弹窗样式)

1.鸿蒙中需要实现一个如下图的弹窗 2.由上图中可以得出&#xff0c;只需要三个Text组件依次向下排列&#xff0c;弹窗背景设置透明即可&#xff0c;弹窗代码如下(仅展示弹窗样式)&#xff1a; /**** 自定义选择图片弹窗** 外部定义需要导出*/ CustomDialog //自定义弹窗 export…

android13顶部状态栏里面调节背光,不隐藏状态栏面板

总纲 android13 rom 开发总纲说明 目录 1.前言 2.代码分析 3.修改方法 4.编译运行 5.彩蛋 1.前言 android13顶部状态栏里面调节背光,这个时候状态栏面板会被隐藏掉,有些需求就需要不隐藏这个面板。 2.代码分析 查找亮度条属性 id/brightness_slider ./frameworks/b…

TOMCAT入门到精通

目录 一 WEB技术 1.1 HTTP协议和B/S 结构 1.2 前端三大核心技术 1.2.1 HTML 1.2.2 CSS&#xff08;Cascading Style Sheets&#xff09;层叠样式表 1.2.3 JavaScript 二 WEB框架 2.2后台应用架构 2.2.1单体架构 2.2.2微服务 2.2.3单体架构和微服务比较 三 tomcat的…

2024Go语言面试宝典Golang零基础实战项目面试八股力扣算法笔记等

2024最新Golang面试八股文&#xff0c;以及各种零基础全套实战项目&#xff0c;经典力扣算法题以及常见的面试题型&#xff0c;大厂面试题。go语言面试必备。包括GO基础类、GO并发编程、GO RUNTIME、微服务、容器技术、Redis、MySQL、Linux、缓存、网络和操作系统、消息队列、分…

房产系统架构开发小程序分析

房产系统架构开发小程序在当前市场中具有显著的优势和潜力。以下是对房产小程序的分析&#xff1a; 用户需求满足&#xff1a;房产小程序通过提供楼盘信息查询、VR看房体验、购房流程指南等功能&#xff0c;满足用户对房产信息的需求&#xff0c;并提供更加便捷的用户体验 。…

NSSCTF练习记录:[SWPUCTF 2021 新生赛]crypto6

题目&#xff1a; 先转为base16 JZLVK6CNKRATKT2ENN2FUR2NGBGXSMDYLFWVC6SMKRAXOWLKKF2E6VCBO5HVISLXJZVEKMKPI5NGY再转base32 NWUxMTA5ODktZGM0My0xYmQzLTAwYjQtOTAwOTIwNjE1OGZl再转base64&#xff0c;得到答案 5e110989-dc43-1bd3-00b4-9009206158fe

如何使用GPT-SoVITSS生成各种角色的语言

百度网盘 请输入提取码 项目来自b站UP主花儿不哭 一&#xff0c;先除去背景声音————人生伴奏出去背景声音 1.下载后&#xff0c;按下面路径打开&#xff0c;打开文件beta&#xff0c;打开go-webui程序 回车&#xff0c;然后稍等一下&#xff0c;等待网页打开 2.勾选如下…

day6JS-DOM(文档对象模型)

DOM树 DOM 操作 1. 获取元素 1.1 根据id名获取元素 document.getElementById("id名"); 案例&#xff1a; <body><div id"box">div盒子</div><h1>一级标题</h1><script>console.log(document.getElementById(&quo…