当前位置: 首页 > news >正文

二叉树的存储

目录

1.使用孩子表示法创建二叉树

2.二叉树的遍历

2.1前中后序遍历

2.2 前中后序遍历的选择题

2.3实现前中后序遍历

2.3.1前序遍历

2.3.2中序遍历

2.3.3后序遍历

3.二叉树的基本操作

3.1获取叶子节点的个数

3.2获取树中节点的个数

3.3获取第K层节点的个数

3.4获取二叉树的高度

3.5检测值为value的元素是否存在


1.使用孩子表示法创建二叉树

二叉树的存储结构 分为: 顺序存储 类似于链表的链式存储

这篇文章主讲的是链式存储。

二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方式有二叉和三叉表示方式。

二叉表示:

// 孩子表示法
class Node {
int val ; // 数据域
Node left ; // 左孩子的引用,常常代表左孩子为根的整棵左子树
Node right ; // 右孩子的引用,常常代表右孩子为根的整棵右子树
}

三叉表示:

// 孩子双亲表示法
class Node {
int val ; // 数据域
Node left ; // 左孩子的引用,常常代表左孩子为根的整棵左子树
Node right ; // 右孩子的引用,常常代表右孩子为根的整棵右子树
Node parent ; // 当前节点的根节点
}

这篇文章使用的存储储存方式是孩子表示法

在学习二叉树的基本操作前,需先要手动快速创建一棵简单的二叉树,使用孩子表示法。创建如下(图1)二叉树。

public class Tree {class TreeNode{char val;TreeNode left;TreeNode right;public TreeNode(char val){this.val=val;}}public TreeNode create(){TreeNode A=new TreeNode('A');TreeNode B=new TreeNode('B');TreeNode C=new TreeNode('C');TreeNode D=new TreeNode('D');TreeNode E=new TreeNode('E');TreeNode F=new TreeNode('F');TreeNode G=new TreeNode('G');TreeNode H=new TreeNode('H');A.left=B;A.right=C;B.left=D;B.right=E;C.left=F;C.right=G;E.right=H;return A;}
}


2.二叉树的遍历

依次对树中每个结 点均做一次且仅做一次访问

2.1前中后序遍历

为什么要有前中后序遍历顺序?

  在遍历二叉树时,如果没有进行某种约定,每个人都按照自己的方式遍历,得出的结果就比较混乱, 如果按 照某种规则进行约定,则每个人对于同一棵树的遍历结果肯定是相同的
如果 N代表根节点 L代表根节点的 左子树 R代表根节点的右子树 ,则根据遍历根节点的先后次序有以下遍历方式
NLR :前序遍历 (Preorder Traversal 亦称先序遍历 )—— 访问根结点 ---> 根的左子树 ---> 根的右子树。
LNR :中序遍历 (Inorder Traversal)—— 根的左子树 ---> 根节点 ---> 根的右子树。
LRN :后序遍历 (Postorder Traversal)—— 根的左子树 ---> 根的右子树 ---> 根节点。

 以图一为例:

前序遍历结果:A B D E H C F G
中序遍历结果:D B E H A F C G
后序遍历结果:D H E B F G C A

2.2 前中后序遍历的选择题

(1)某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH 。该完全二叉树的前序序列为()

A: ABDHECFG
B: ABCDEFGH
C: HDBEAFCG
D: HDEBFGCA
二叉树如图:

故选A

(2) 二叉树的先序遍历和中序遍历如下:先序遍历:EFHIGJK;中序遍历:HFIEJKG.则二叉树根结点为()

A: E              B: F               C: G            D: H
二叉树如图:
故选A
(3) 设一课二叉树的中序遍历序列: badce ,后序遍历序列: bdeca ,则二叉树前序遍历序列为 ()
A: adbce             B: decab              C: debac             D: abcde
二叉树如图:
故选D
(4)某二叉树的后序遍历序列与中序遍历序列相同,均为 ABCDEF ,则按层次输出 ( 同一层从左到右 ) 的序列为 ()
A: FEDCBA
B: CBAFED
C: DEFCBA
D: ABCDEF
二叉树如图:
故选A
思考题:

2.3实现前中后序遍历

2.3.1前序遍历
    // 前序遍历void preOrder(TreeNode root){if(root==null){return;}System.out.println(root.val+" ");preOrder(root.left);preOrder(root.right);}
2.3.2中序遍历
// 中序遍历void inOrder(TreeNode root){if(root==null){return;}preOrder(root.left);System.out.println(root.val+" ");preOrder(root.right);}
2.3.3后序遍历
// 后序遍历void postOrder(TreeNode root){if(root==null){return;}preOrder(root.left);preOrder(root.right);System.out.println(root.val+" ");}

3.二叉树的基本操作

// 获取树中节点的个数
int size ( Node root );
// 获取叶子节点的个数
int getLeafNodeCount ( Node root );
// 获取第 K 层节点的个数
int getKLevelNodeCount ( Node root , int k );
// 获取二叉树的高度
int getHeight ( Node root );
// 检测值为 value 的元素是否存在
Node fifind ( Node root , int val ); 

3.1获取叶子节点的个数

当前节点的左右子树若都为空,说明该节点为叶子结点,返回1

树的叶子节点的个数=左树叶子节点的个数+右树叶子节点的个数

    int getLeafNodeCount(TreeNode root){if(root==null){return 0;}return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);}

3.2获取树中节点的个数

若当前结点为空,返回0

先获取左节点个数,再获取右节点个数,然后返回两者相加再加上根节点的个数1

  int size(TreeNode root){if(root==null){return 0;}return size(root.right)+size(root.left)+1;}

3.3获取第K层节点的个数

本质是计算k=1时的节点数

树的叶子第K层节点的个数=左树叶子第K-1层节点的个数+右树第K-1层节点的个数

    int getKLevelNodeCount(TreeNode root, int k) {if(root==null){return 0;}if(k==1){return 1;}return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);}

3.4获取二叉树的高度

    int getHeight(TreeNode root) {if(root==null){return 0;}int lefthight=getHeight(root.left);int rifhthight=getHeight(root.right);return lefthight>rifhthight?(lefthight+1):(rifhthight+1);}

3.5检测值为value的元素是否存在

遍历左(右)子树,若没有找到,则返回null,若找到,则返回该结点

   TreeNode fifind(TreeNode root, int val) {if (root==null){return null;}if(root.val==val){return root;}TreeNode lefttree=fifind(root.left, val);if(lefttree!=null){return lefttree;}TreeNode righttree=fifind(root.right, val);if(righttree!=null){return righttree;}return null;}

以上为我个人的小分享,如有问题,欢迎讨论!!! 

都看到这了,不如关注一下,给个免费的赞 

 

相关文章:

二叉树的存储

目录 1.使用孩子表示法创建二叉树 2.二叉树的遍历 2.1前中后序遍历 2.2 前中后序遍历的选择题 2.3实现前中后序遍历 2.3.1前序遍历 2.3.2中序遍历 2.3.3后序遍历 3.二叉树的基本操作 3.1获取叶子节点的个数 3.2获取树中节点的个数 3.3获取第K层节点的个数 3.4获取…...

List 去重的几种方法

&#x1f514;HashSet去重 import java.util.HashSet;HashSet<Integer> set new HashSet<>(); set.add(1); set.add(2); set.add(2); System.out.println(set); // [1, 2]&#x1f514;TreeSet去重 import java.util.TreeSet;TreeSet<Integer> set new T…...

UNet网络制作

UNet网络制作 代码参考UNet数据集制作及代码实现_哔哩哔哩_bilibili&#xff0c;根据该UP主的代码&#xff0c;加上我的个人整理和理解。&#xff08;这个UP主的代码感觉很好&#xff0c;很规范 UNet网络由三部分组成&#xff1a;卷积块&#xff0c;下采样层&#xff0c;上采样…...

智能热水器丨打造智能家居新体验

随着科学技术的不断发展&#xff0c;智能电器越来越被大众所采纳&#xff0c;如智能扫地机&#xff0c;智能洗衣机&#xff0c;智能微波炉等等&#xff0c;越来越智能的电器为人们的生活带来了许多便利。以往的热水器一般都是只有按键/机械的控制方式&#xff0c;没有其他无线控…...

Python 十进制转化二进制1.0(简易版)

"""十进制转换二进制知识点&#xff1a;1、循环语句/跳转语句 while/break2、运算符 求余%、整除//3、字符串拼接4、字符串切片5、数据类型转换不足与改善&#xff1a;1、不能输入非正整数&#xff0c;否则报错或卡住"""# 倒序二进制存储 revers…...

WebGL 选中一个表面

目录 选中一个表面 示例程序&#xff08;PickFace.js&#xff09; 代码详解 gl.readPixels()见126行效果 gl.UNSIGNED_BYTE注意点 示例效果 选中一个表面 ​​​​​​​WebGL 选中物体_山楂树の的博客-CSDN博客可以使用同样的方法来选中物体的某一个表面。这一节在Pi…...

open ai chartgpt 安装插件 txyz.ai

1 chatgpt 页面 左下角 用户 -> setting 2 3...

【算法思想】贪心

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学…...

freeswitch-01

文章目录 1. 电话实现技术2. 模拟信号与数字信号2.1 模拟信号2.2 数字信号 3. PCM4. 局间中继与电路复用技术5. 信令5.1 定义5.2 分类5.2.1 功能分类5.2.2 工作区域分类5.2.3 信道分类 5.3 用户线信令5.4 局间信令5.5 七号信令5.6 H.323与SIP信令 6. 媒体6.1 定义 7. 电路交换与…...

Zookeeper-集群介绍与核心理论

Zookeeper集群 4.Zookeeper集群4.1) 介绍4.2) 核心理论 4.Zookeeper集群 4.1) 介绍 Leader选举&#xff1a; Serverid&#xff1a;服务器ID。比如有三台服务器&#xff0c;编号分别是1,2,3。编号越大在选择算法中的权重越大。Zxid&#xff1a;数据ID。服务器中存放的最大数据…...

动态分配的内存位置在哪里?

在C++中,动态分配的内存位于称为堆(Heap)的内存区域。以下是一些关于堆和其他相关内存区域的基本信息: 堆(Heap): 这是一个用于动态内存分配的内存区域。使用new(C++)或malloc(C)等函数从堆中分配内存,并使用delete(C++)或free(C)释放这些内存。堆的大小通常受…...

Vue3中的Ref与Reactive:深入理解响应式编程

前言 Vue 3是一个功能强大的前端框架&#xff0c;它引入了一些令人兴奋的新特性&#xff0c;其中最引人注目的是ref和reactive。这两个API是Vue 3中响应式编程的核心&#xff0c;本文将深入探讨它们的用法和差异。 什么是响应式编程&#xff1f; 在Vue中&#xff0c;响应式编…...

Windows10/11显示文件扩展名 修改文件后缀名教程

前言 写这篇文章的原因是由于我分享的教程中的文件、安装包基本都是存在阿里云盘的&#xff0c;下载后需要改后缀名才能使用。 但是好多同学不会改。。 Windows 10 随便打开一个文件夹&#xff0c;在上方工具栏点击 “查看”点击 “查看” 后下方会显示更详细的工具栏然后点…...

【C++】手撕string(string的模拟实现)

手撕string目录&#xff1a; 一、 Member functions 1.1 constructor 1.2 Copy constructor&#xff08;代码重构&#xff1a;传统写法和现代写法&#xff09; 1.3 operator&#xff08;代码重构&#xff1a;现代写法超级牛逼&#xff09; 1.4 destructor 二、Other mem…...

用python3编译cv_bridge

文章目录 概要依赖工作空间编译可能遇到的问题error: option --install-layout not recognized概要 当我在编写一个使用传感器图像传输和OpenCV4的ROS包时,从构建到编译代码的一切都很顺利。当我开始运行节点本身时,问题出现了,它给出了以下错误: Assertion failed (tlsSl…...

招商信诺人寿基于 Apache Doris 统一 OLAP 技术栈实践

本文导读&#xff1a; 当前&#xff0c;大数据、人工智能、云计算等技术应用正在推动保险科技发展&#xff0c;加速保险行业数字化进程。在这一背景下&#xff0c;招商信诺不断探索如何将多元数据融合扩充&#xff0c;以赋能代理人掌握更加详实的用户线索&#xff0c;并将智能…...

我的python安装在哪儿了?python安装路径怎么查?

对于 Python 开发者来说&#xff0c;Windows 系统中的 Python 安装路径是非常重要的。在本文中&#xff0c;我们将从多个方面探究如何查看 Python 安装路径&#xff0c;并提供代码示例。 一、使用文件浏览器查看 Python 安装路径 在 Windows 系统中&#xff0c;我们可以使用文…...

视频汇聚/安防监控平台EasyCVR指定到新的硬盘进行存储录像,如何自动挂载该磁盘?

TSINGSEE青犀视频监控汇聚平台EasyCVR可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。平台既具备传统安防视频监控的能力&…...

读博时的建议或心得

https://www.zhihu.com/question/32210068/answer/264273093 读论文&#xff1a;一开始读论文&#xff0c;一定要读顶会顶刊的&#xff0c;以后也一直要这样。如此&#xff0c;一方面保持了研究的水准&#xff0c;时刻提醒自己&#xff1a;我就是混这个层次的。另一方面&#…...

3分钟,免费制作一个炫酷实用的数据可视化大屏!

在当前大数据时代背景下&#xff0c;数据已成为在工业革命中如同煤炭、石油一般宝贵的资源。但是由于数据越来越庞大、越来越复杂&#xff0c;导致数据的可读性也越来越低。因此&#xff0c;对数据可视化的需求也越来越高&#xff0c;需要解决的问题也越来越复杂&#xff0c;而…...

别再死磕公式了!用Python+SymPy从零推导6轴机械臂的DH参数与正逆解(附完整代码)

用PythonSymPy自动化推导6轴机械臂运动学&#xff1a;从DH参数到八组逆解实战 机械臂运动学分析是机器人开发中最烧脑的环节之一。传统手工推导DH参数矩阵不仅容易出错&#xff0c;验证过程更是令人崩溃——想象一下&#xff0c;当你花了两天时间推导出十几页公式&#xff0c;…...

为MusicBee集成网易云音乐同步歌词的技术实现方案

为MusicBee集成网易云音乐同步歌词的技术实现方案 【免费下载链接】MusicBee-NeteaseLyrics A plugin to retrieve lyrics from Netease Cloud Music for MusicBee. 项目地址: https://gitcode.com/gh_mirrors/mu/MusicBee-NeteaseLyrics MusicBee作为一款功能强大的本地…...

告别虚拟机!Windows WSL2+GNU Radio玩转HackRF-One无线接收(避坑指南)

告别虚拟机&#xff01;Windows WSL2GNU Radio玩转HackRF-One无线接收&#xff08;避坑指南&#xff09; 在软件定义无线电&#xff08;SDR&#xff09;领域&#xff0c;HackRF-One因其开源设计和亲民价格成为入门首选。然而传统虚拟机方案常因性能损耗、驱动兼容性问题让新手望…...

3步突破显卡限制:如何让AMD/Intel显卡实现DLSS级画质?

3步突破显卡限制&#xff1a;如何让AMD/Intel显卡实现DLSS级画质&#xff1f; 【免费下载链接】OptiScaler OptiScaler bridges upscaling/frame gen across GPUs. Supports DLSS2/XeSS/FSR2 inputs, replaces native upscalers, enables FSR3 FG on non-FG titles. Supports N…...

Magma智能剪辑系统:视频自动生成实战

Magma智能剪辑系统&#xff1a;视频自动生成实战 1. 引言 想象一下这样的场景&#xff1a;你有一个精彩的视频创意&#xff0c;写好了详细的脚本&#xff0c;但面对一堆零散的素材片段却无从下手。传统的视频剪辑需要逐帧挑选、拼接、添加转场&#xff0c;一个几分钟的视频可…...

HelixDB部署与运维:从本地开发到生产环境的完整流程

HelixDB部署与运维&#xff1a;从本地开发到生产环境的完整流程 【免费下载链接】helix-db HelixDB is a powerful, graph-vector database built entirely in Rust for millisecond query latency and ease of use. 项目地址: https://gitcode.com/gh_mirrors/he/helix-db …...

提升开发效率:Android Studio零障碍IDE本地化配置指南

提升开发效率&#xff1a;Android Studio零障碍IDE本地化配置指南 【免费下载链接】AndroidStudioChineseLanguagePack AndroidStudio中文插件(官方修改版本&#xff09; 项目地址: https://gitcode.com/gh_mirrors/an/AndroidStudioChineseLanguagePack 开发人员在使用…...

视频格式转换革新:m4s-converter让B站缓存视频无缝播放

视频格式转换革新&#xff1a;m4s-converter让B站缓存视频无缝播放 【免费下载链接】m4s-converter 一个跨平台小工具&#xff0c;将bilibili缓存的m4s格式音视频文件合并成mp4 项目地址: https://gitcode.com/gh_mirrors/m4/m4s-converter 从缓存困境到自由播放&#x…...

【花雕学编程】Arduino BLDC 之使用互补滤波进行姿态控制的机器人

从专业工程视角来看&#xff0c;基于Arduino、使用互补滤波进行姿态控制的BLDC&#xff08;无刷直流电机&#xff09;机器人&#xff0c;是一个典型的嵌入式实时闭环控制系统。它集成了传感器数据融合、控制算法和电机驱动&#xff0c;广泛应用于对姿态稳定性有要求的场景。 1、…...

Mermaid Live Editor:代码驱动图表设计的终极解决方案

Mermaid Live Editor&#xff1a;代码驱动图表设计的终极解决方案 【免费下载链接】mermaid-live-editor Edit, preview and share mermaid charts/diagrams. New implementation of the live editor. 项目地址: https://gitcode.com/GitHub_Trending/me/mermaid-live-editor…...