数据结构与算法学习总结(七)——二叉树的概念

2023-05-16

二叉树的定义

二叉树(binary tree)由结点的有限集合构成

这个有限集合或者为空集(empty)，或者为由一个根节点(root)及两颗互不相交、分别称作这个根的左子树(left bustree)和右子树(right subtree)的二叉树组成的集合。

二叉树的五种基本形态

二叉树可以是空集合，因此根可以有空的左子树或右子树，或者左右子树都为空。

二叉树相关术语

结点

-子结点、父结点、最左子结点

：若<k,k'>∈r，则称k是k'的父结点(或"父母")，而k'则是k的子结点(或"儿子"、"子女")

-兄弟节点、左兄弟、右兄弟

：若有序对<k,k'>及<k,k''>都∈r，则称K'和K''互为兄弟结点。

-分支结点、叶子结点

：没有子树的节点称为叶子结点(或树叶、终端结点)

：非终端结点称为分支结点

边

两个节点的有序对，称作边

路径、路径长度

除结点k0外的任何节点k ∈K，都存在一个结点序列k0,k1,...,ks，使得k0就是树根，且ks=k，其中有序对<k(i-1),ki>∈r(1<=i<=s)。这样的结点序列称为从根到结点k的一条路径，其路径长度为s(包含的边数)。

祖先、后代

若有一条由k到达ks的路径，则称k是ks的祖先，ks是k的子孙

层数

根为第0层，其他结点的层数等于其父结点的层数加1

深度

层数最大的叶子结点的层数

高度

层数最大的叶子结点的层数加1

满二叉树

如果一棵二叉树的任何结点，或者是树叶，或者恰有两颗非空子树，则此二叉树称为满二叉树

完全二叉树

最多只有最下面的两层结点度数可以小于2

最下一层的结点都集中最左边

扩充二叉树

所有空子树，都增加空树叶

外部路径长度E和内部内径长度I的关系满足：E=I+2n(n是内部结点个数)

二叉树的主要性质

在二叉树中，第i层上最多有2的i次方个结点(i>=0)
深度为k的二叉树至多有2的(k+1)次方减1个结点(k>=0)，其中深度(depth)定义为二叉树中层数最大的叶子结点的层数。
一棵二叉树，如果终端结点数为n0，度为2的节点数为n2，则n0=n2+1
满二叉树定理：非空满二叉树树叶数目等于其分支结点数加1
满二叉树定理推论：一个非空二叉树的空子树数目等于其结点数加1
有n个结点(n>0)的完全二叉树的高度为log2(n+1)，深度为[log2(n+1)]-1

ps:复习考研了，目标是北邮计算机的非全，可能得等学习到专业课的部分才会继续更新博客了，加油吧！

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构与算法学习总结

二叉树的概念

数据结构与算法学习总结(七)——二叉树的概念的相关文章

算法题1

假设有这样一个国家 xff0c 其法律规定当公民月收入为x时 xff0c 若x gt 1 则每月应当缴纳的税金为x的因数中除了x之外的最大值同时该国法律允许公民将月收入分成若干部分每部分均为整数 xff0c 要求每部分收入都大于1 xf
3.4日期处理

include lt iostream gt include lt cstdio gt 平年和闰年的每月的天数 int month 13 2 61 0 0 31 31 28 29 31 31 30 30 31 31 30 30 31 31
关于STL和Boost的理解

xff11 xff0e STL STL是standard Template Library即标准模板库的英文缩写 xff0c 是惠普实验室开发的一系列软件的统称从根本上讲 STL是一些容器的集合 xff0c 这些容器有list vec
Ubuntu 各版本号和名称对照

版本开发代号中译发布日期支持结束时间内核版本桌面版服务器版4 10Warty Warthog多疣的疣猪2004 10 202006 04 302 6 85 04Hoary Hedgehog白发的刺猬2005 04 082006 10 312
【无标题】安装ROS E: 无法定位软件包 ros-melodic-desktop-full

一遇到问题二可能的原因和解决方法 1 源换一下 xff1a xff08 1 xff09 我是看这位大佬的 5条消息记录解决Ubuntu安装ros报错E Unable to locate package ros kinetic de
无线通信原理及协议栈（ZigBee、蓝牙等）解析

1 天线说起无线电通信 xff0c 不可不提起天线在无线电设备中 xff0c 用来辐射和接收无线电波的装置称为天线在发射端 xff0c 发射机产生的已调制的高频振荡电流 xff08 能量 xff09 经馈电 xff08 指被控制装置向
串口Serial连接方式

串口Serial连接方式 1 协议终端选择Serial 2 会话选项 xff0c 选择串行 3 进入电脑设备管理器 xff0c 查看USB Serial Port以及端口设置串行选项根据端口设置配置确定并连接即可
tcp/ip 协议栈实现2-socket文件系统

core initcall sock init net socket c static int init sock init void int err Initialize sock SLAB cache sk init Initializ
VMware虚拟机安装Windows11（无需设置TPM密码）

VMware虚拟机安装Windows11 xff08 无需设置TPM密码 xff09 注意 xff1a 需要新版VMware xff0c 目前小白的版本为 16 2 3 一新建虚拟机向导 1 新建虚拟机点击菜单栏文件新建虚拟机 2 配
ROS相关：使用rospy 编写ros程序并使用rosbag存储数据

为什么使用rospy ROS支持C 43 43 和Python xff0c 由于ROS的底层是由C 43 43 编写 xff0c 因此大多数的ROS程序都使用C 43 43 xff0c 但是Python语言接口简单 xff0c 更容易编写
C函数调用过程

这几天在看GCC Inline Assembly xff0c 在C代码中通过asm或 asm 嵌入一些汇编代码 xff0c 如进行系统调用 xff0c 使用寄存器以提高性能能 xff0c 需要对函数调用过程中的堆栈帧 xff08 Stack
【GitHub】Branches和Tags分别是做什么用的？

在 GitHub 中 xff0c Branches xff08 分支 xff09 和 Tags xff08 标签 xff09 都是用于版本控制的重要工具 Branches xff08 分支 xff09 可以用来创建一个新的开发分支 xff0
git clone 指定分支

我们在有一个工程的权限后 xff0c 按照常规操作去拉代码 xff0c 往往会拉到默认的master分支若我们担心master分支拉下来后 xff0c 与其他代码有冲突 xff0c 想直接拉某分支的代码 xff0c 则该怎么操作呢 1 我
rocketmq的消息msgId和offsetMsgId

1 rocketmq的消息发送时 xff0c producer客户端生成msgId xff08 通过 ip 43 进程 43 自增值 43 当前与系统启动时间差值 xff09 xff0c 有另外的一个叫法uniqId 方法入口 xff1a
算法 - 桶排序（Bucket Sort）

执行流程 xff1a 创建一定数量的桶 xff08 比如用数组链表作为桶 xff09 按照一定的规制 xff08 不同类型的数据 xff0c 规则不同 xff09 xff0c 将序列中的元素均匀分配到对应的桶分别对每个桶进行单独排序将所有
测试Pangolin是否安装成功

一终端输入 cd Pangolin examples HelloPangolin cmake make HelloPangolin 二显示这个结果则成功三顺便放一个我可终于装完了ORB SLAM3 被内存不够折腾了好久换个内存条
交叉编译工具 aarch64-linux-gnu-gcc 的介绍与安装

AArch64 是随 ARMv8 ISA 一起引入的 64 位架构 xff0c 用于执行 A64 指令的计算机而且在 AArch64 状态下执行的代码只能使用 A64 指令集 xff0c 而不能执行 A32 或 T32 指令但是 xff
02 机器学习中的评估指标

机器学习中的评估指标 1 机器学习的目标根本目标 xff1a 在给定的训练数据上 xff0c 试图训练出能够归纳数据的规律的模型 xff0c 并且能在未知样本上也有好的效果泛化能力强的模型最好能很好地适用于未知样本 xff0c 如错误
方便Git提交代码的几个工具

团队使用git管理代码 xff0c 为了提交方便 xff0c 查看Log方便 xff0c 师傅告诉我先安装几个工具 xff0c 如下 xff1a cola gitk AnyEdit 一 gitk安装 xff08 备注 xff1a 开始我没走

随机推荐

git提交本地分支和远程分支断开连接

1级标题当 git push origin branch name时遇到报错如下 xff1a fatal origin does not appear to be a git repository fatal Could not read
spring MVC中关于model.addAttribute的使用方法【翻译】

关于model addAttribute的使用方法 http krams915 blogspot com 2010 12 spring 3 mvc using modelattribute in html 可能要 break the wal
ROS进阶学习手记 7 -- RViz仿真实例1

任务2 xff1a 用simulator RViz 工具 xff0c 完成对小车的建模 xff0c 名字drive RViz 61 dvrv 用 dvrv node 发布topic和数据格式 xff0c 向它发送位置指令 xff0c 使它能
在ROS 使用摄像头 WebCam 完成图像处理（1） -- 获取图像数据

在ROS 使用摄像头 WebCam 完成图像处理 xff08 1 xff09 获取图像数据我们要使用摄像头 xff0c 先要能看到摄像头图像 xff1a xff08 见附录 xff09 然后我们这里是参考 ros by example v
ROS进阶学习手记 10 - 用iRobot Create 2搭建自己的TurtleBot（1）- Introduction

ROS进阶学习手记 10 搭建自己的TurtleBot xff08 1 xff09 Introduction 时隔一两个月 xff0c 再次回来继续写自己的ROS学习及应用手记这一两个月里 xff0c 我并没有闲着 xff0c 而是照着
ROS 进阶学习笔记（16）：ROS导航1：关于Costmap_2d Package （代价地图包）

61 61 61 关于Costmap 2d Package 61 61 61 wiki page http wiki ros org costmap 2d 61 61 61 我遇到的问题是 obstacle layer的刷新频率太低 61
ubuntu解决resolv.conf被重写问题

解决resolv conf被重写问题来源 xff1a http www cnblogs com lanxuezaipiao p 3613497 html 第二步中你虽然配置了DNS xff0c 但是每次重启虚拟机或重启网络后 etc re
视觉SLAM-回环检测

这是课上做的一个pre xff0c 大家可以看看帮助理解 xff0c 有问题或者写的不对的可以提出目录前言一 SLAM 问题 xff08 SLAM Problem 二回环检测 xff08 Loop Closing 三为什么要回环检
ROS进二阶学习笔记（9）-- 关于Overlay：重名 package 在不同catkin workspace 中，

要把ROS玩转 xff0c 必须把 catkin 玩转 http wiki ros org catkin Tutorials 其中 xff0c Overlay问题是重名 package 在不同catkin workspace 中时 xff
ROS进二阶学习笔记（10） -- rospy.Publisher() 之 queue_size

ROS进二阶学习笔记 xff08 10 xff09 rospy Publisher 之 queue size ref link 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 queue size
我的近况及hugo搭建教程

还是有朋友一直在关注我尽管很少 xff01 说声感谢 xff01 xff01 xff01 我还是愿意使用自己搭的hugo hugo搭建教程 xff1a Prerequisites Before you begin this tutoria
DSP芯片的定点运算

本文排版不恰当 xff0c 请到新浪爱问下载本文的pdf版 xff0c 豪猪哥 DSP芯片的定点运算1 0 第3章 DSP芯片的定点运算 3 1 数的定标在定点DSP芯片中 xff0c 采用定点数进行数值运算 xff0c 其操作数一般
STM32CubeMX自动生成SYSTICK配置

1 SYSTICK原理及其寄存器 1 1 SYSTICK原理 SysTick 是一个24位的倒计数定时器 xff0c 当计到0时 xff0c 将从RELOAD寄存器中自动重装载定时初值并继续计数 xff0c 且同时触发中断只要不把它在Sy
OpenCV之求多边形最小外接矩形中心点坐标及旋转度数

代码 include lt opencv2 opencv hpp gt include lt vector gt include lt algorithm gt using namespace cv using namespace std
SLAM总结(一)

1 概述 SLAM 机器人同时定位与建图 xff1a 本质上是一个系统 xff0c 主要分为四部分 xff1a 传感器数据输入 xff0c i前端数据处理 xff08 关键帧匹配 xff09 xff0c 后端数据优化 xff08 滤波器 x
Linux消息队列与信号量

Linux消息队列与信号量一消息队列概念 xff1a 消息队列是由内核负责维护管理的链式数据队列 xff0c 不是根据先后顺序出队 xff0c 而是根据消息类型进行收发数据 span class token keyword int s
类的使用中：为什么静态方法中使用非静态成员变量需要创建，静态的不需要，非静态方法中可以随便使用两者

package com qf javase day11 64 author 徐兴 64 version 1 0 64 date 2022 3 1 14 13 public class StaticDemo2 static和非static的使
STL应用篇

概要 STL是泛型编程 Generic Programming GP 和C 43 43 结合的产物 STL主要由几个核心部件组成 xff1a 迭代器容器算法函数对象适配器容器即物之所属 xff1b 算法是解决问题的方式 xff1b
计算机网络I-考前指导复习提纲

计算机网络I考前指导填空选择连线简答计算等题型考试范围基本在course review里面 xff0c 老师说可能会考的用表示 xff08 自己学校的考点都在这里 xff0c 仅供参考 xff09 PPT1 Networking
数据结构与算法学习总结(七)——二叉树的概念

二叉树的定义二叉树 binary tree 由结点的有限集合构成这个有限集合或者为空集 empty xff0c 或者为由一个根节点 root 及两颗互不相交分别称作这个根的左子树 left bustree 和右子树 right sub

热门标签