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

代码随想录---二叉树的总结和二叉树的定义

二叉树的种类:

满二叉树:树的所有节点都是满,即都有左右孩子。

这棵二叉树为满二叉树,也可以说深度为k,有2^k-1个节点的二叉树。

完全二叉树完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2^(h-1)  个节点。

 二叉搜索树:二叉搜索树是一颗排序树。

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  • 它的左、右子树也分别为二叉排序树

 平衡二叉搜索树又被称为AVL(Adelson-Velsky and Landis)树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

二叉树的存储方式:

二叉树可以链式存储,也可以顺序存储。

那么链式存储方式就用指针, 顺序存储的方式就是用数组。

链式存储:使用链表

 顺序存储:使用数组的方式

查找节点:如果父节点的数组下标是 i,那么它的左孩子就是 i * 2 + 1,右孩子就是 i * 2 + 2。

但是用链式表示的二叉树,更有利于我们理解,所以一般我们都是用链式存储二叉树。

二叉树的遍历方式:

二叉树主要有两种遍历方式:

  1. 深度优先遍历:先往深走,遇到叶子节点再往回走。
  2. 广度优先遍历:一层一层的去遍历。

那么从深度优先遍历和广度优先遍历进一步拓展,才有如下遍历方式:

  • 深度优先遍历
    • 前序遍历(递归法,迭代法)
    • 中序遍历(递归法,迭代法)
    • 后序遍历(递归法,迭代法)
  • 广度优先遍历
    • 层次遍历(迭代法)

前中后遍历其实就是看根节点的位置。在中间就是中序;在前面就前序;在后面就是后序遍历。

  • 前序遍历:中左右
  • 中序遍历:左中右
  • 后序遍历:左右中

二叉树的定义:

java的定义:

public class TreeNode {int value;TreeNode left;TreeNode right;//无参数构造器:TreeNode(){}TreeNode(int value){this.value=value;}//有参数构造器:public TreeNode(int value, TreeNode left, TreeNode right) {this.value = value;this.left = left;this.right = right;}
}

python的定义:

class TreeNode: def __init__(self, value):self.value = valueself.left = Noneself.right = None

C++的定义:

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

相关文章:

代码随想录---二叉树的总结和二叉树的定义

二叉树的种类: 满二叉树:树的所有节点都是满,即都有左右孩子。 这棵二叉树为满二叉树,也可以说深度为k,有2^k-1个节点的二叉树。 完全二叉树:完全二叉树的定义如下:在完全二叉树中&#xff0c…...

Hive SQL 执行计划

我们在写Hive SQL的时候,难免会在运行的时候有报错,所以知道Hive SQL的执行计划具体是什么,然后假如在之后的运行过程中有报错,可以根据执行计划定位问题,调试自己的SQL开发脚本。 一、含义 Hive SQL的执行计划描述S…...

MySQL InnoDB引擎——三层B+树可以存储多少数据量

先说结论: 3层B树大概可以存: 主键为bigint:约2000w主键为int:约4000w*备注: 在《阿里开发手册》中建议,单表行数超过500万行或者单表容量超过2GB,才推荐进行分库分表,如果预计三年后…...

部署跨云容灾的五大难点

为什么企业需要跨云容灾? 据统计,全球已有70%的企业使用云计算服务。上云帮助企业更高效地管理数据资产,但它并非绝对安全。如停电、漏水等机房事故;地震、火灾等自然性灾害;亦或是人为失误,都有可能造成数…...

Docker Compose

为什么需要使用Docker ComposeDocker Compose 容器编排技术1、现在我们有一个springboot项目,需要依赖Redis、mysql、nginx。如果使用docker原生部署的话,则需要安装Redis、mysql、nginx容器,才可以启动我们springboot项目,这样的…...

【ARM架构】armv8 系统安全概述

ARMv8-A 系统中的安全 一个安全或可信的操作系统保护着系统中敏感的信息,例如,可以保护用户存储的密码,信用卡等认证信息免受攻击。 安全由以下原则定义: 保密性:保护设备上的敏感信息,防止未经授权的访问…...

数学小课堂:数学边界

文章目录 引言I 费马大定理1.1毕达哥拉斯定理的推广1.2 一波三折的定理证明过程1.3 希尔伯特第十问题II 数学的边界2.1 认识论问题2.2 在边界内做事情2.3 总结引言 了解数学本身的局限性,才能更好地使用它的原理和思维方式。 数学的边界,这是一个硬的边界,大家不要试图逾越…...

检测中断到来时,让LED灯状态取反,并且在串口工具上打印一句话

任务:检测中断到来时,让LED灯状态取反,并且在串口工具上打印一句话例如:当按键1按下之后,让LED1状态取反,并打印“LED1 down”当按键2按下之后,让LED2状态取反,并打印“LED2 down”当…...

2023年CDGA考试-第7章-数据安全(含答案)

2023年CDGA考试-第7章-数据安全(含答案) 单选题 1.数据安全不仅涉及防止不当访问,也涉及对数据的适当访问,下列理解不正确的是 ( ) A.强密码有助于提高破解风险 B.安全专家建议 45-180天修改一次密码 C.用户要尽量使用多套密码和账户 D.具有高度敏感信息权限的用户都应使…...

输出月份英文名称--C语言实现

任务描述 本关需要你编写一个用指针数组处理的c程序,然后从键盘输入月份时输出对应的英文名。 相关知识 指针 指针是一个变量,其值为另一个变量的地址,即内存位置的直接地址。就像其他变量或常量一样,你必须在使用指针存储其他变量地址之前,对其进行声明。 指针变量声明…...

6年测试经验老鸟:做不好自动化测试,还谈什么高薪?

提起自动化测试,可谓仁者见人,智者见智,心中五味杂陈啊!你从任何一个招聘渠道来看最近两年对测试岗位的要求,几乎都要求会自动化测试。而不少人一直认为手工测试才是王道,工作中有的时候也用不到程序&#…...

Java Web:开篇综述与第一章

前言 翻开这本书,又是一段新的学习路线,在学习的道路上是枯燥的,是乏味的,难免有放弃的想法。但回看曾经的学习笔记,自己也一步一步走过来了,即使会自我怀疑自我否定,但不坚持不努力是永远没有…...

ES6中对象的一些拓展

当对象键名与对应值名相等的时候,可以进行简写 const obj { name }允许字面量定义对象时,将表达式放在括号内 let lastWord last word;const a {first word: hello,[lastWord]: world };a[first word] // "hello" a[lastWord] // "wo…...

10分钟快速入门Pandas库

pandas 是基于NumPy 的一种工具,该工具是为解决数据分析任务而创建的,这篇文章主要介绍了10分钟快速入门Pandas库,重点介绍pandas常见使用方法,结合实例代码介绍的非常详细,需要的朋友可以参考下目录Pandas的介绍pandas 是基于Num…...

考研复试机试 | C++ | 王道机试课程笔记

目录Zero-complexity (上交复试题)题目&#xff1a;代码&#xff1a;括号匹配问题题目&#xff1a;代码&#xff1a;表达式解析问题 &#xff08;浙大机试题&#xff09;题目&#xff1a;代码&#xff1a;标准库里提供了栈 stack<typename> myStack .size() 栈的大小 .pu…...

【python科目一:生产线系统设计;激光刀切割材料】

工厂有若干条生产线&#xff0c;可以生产不同型号的产品&#xff0c;要求实现功能如下&#xff1a;1. ProductionLineMgmtSys 初始化生产线和产品的生产周期有num条生产线&#xff0c;编号从0开始periods[i]表示生产一个型号为i的产品所需的生产周期&#xff0c;单位为天2. Pro…...

Linux——进程概念(进程状态)

目录 进程状态 三态模型 五态模型 七态模型 Example eg1:阻塞态&#xff1a;等待某种资源的过程 eg2:挂起态 Linux内核源代码 Linux进程状态查看 Linux运行状态 R运行状态&#xff08;running&#xff09;: S睡眠状态&#xff08;sleeping)&#xff1a; D磁盘休眠状…...

超详细:正则表达式从入门到入门

文章目录匹配字符\d \D\s \S量词&#xff1a;匹配多个字符星号*加号问号&#xff1f;大括号{}集合字符[]明确字符范围字符补集字符常见字符集贪婪模式和非贪婪模式匹配开头和结尾贪婪模式和非贪婪模式常用函数re.findall()re.search()re.compile()re.split()re.sub()本文章首发…...

jupyter notebook小技巧

1、.ipynb 文件转word文档 将 jupyter notebook&#xff08;.ipynb 文件&#xff09;转换为 word 文件&#xff08;.docx&#xff09;的最简单方法是使用 pandoc。 首先安装pip install pandoc&#xff0c; 安装后&#xff0c;在将 Jupyter notebook文件目录cmd 然后输入打开…...

考研复试机试 | c++ | 王道复试班

目录n的阶乘 &#xff08;清华上机&#xff09;题目描述代码汉诺塔问题题目&#xff1a;代码&#xff1a;Fibonacci数列 &#xff08;上交复试&#xff09;题目代码&#xff1a;二叉树&#xff1a;题目&#xff1a;代码&#xff1a;n的阶乘 &#xff08;清华上机&#xff09; …...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...