数据结构 | 树的定义及实现
目录
一、树的术语及定义
二、树的实现
2.1 列表之列表
2.2 节点与引用
一、树的术语及定义
节点:
节点是树的基础部分。它可以有自己的名字,我们称作“键”。节点也可以带有附加信息,我们称作“有效载荷”。有效载荷信息对于很多树算法来说不是重点,但它常常在使用树的应用中很重要。
边:
边是树的另一个基础部分。两个节点通过一条边相连,表示他们之间存在关系。除了根节点以外,其他每个节点都仅有一条入边,出边则可能有多条。
根节点:
根节点是树中唯一没有入边的节点。
路径:
路径是由边连接的有序节点列表。比如,哺乳纲食肉目
猫科
猫属
家猫就是一条路径。
子节点:
一个节点通过出边和子节点相连。
父节点:
一个节点是其所有子节点的父节点。
兄弟节点:
具有同一父节点的节点互称为兄弟节点。
子树:
一个父节点及其所有后代的节点和边构成一颗子树。
叶子节点:
叶子节点没有子节点。
层数:
节点n的层数是从根节点到n的唯一路径长度。根节点的层数是0。
高度:
树的高度是其中节点层数的最大值。
定义基本术语后,就可以进一步给出树的正式定义。实际上,下面提供了两种定义,其中一种涉及节点和边,另一种涉及递归。递归定义很有用。
定义一:树由节点及连接节点的边构成。树有以下属性:
- 有一个根节点;
- 除根节点外,其他每个节点都与其唯一的父节点相连;
- 从根节点到其他每个节点都有且仅有一条路径;
- 如果每个节点最多有两个子节点,我们就称这样的树为二叉树。
定义二:一棵树要么为空,要么由一个根节点和零颗或多颗子树构成,子树本身也是一棵树。每颗子树的根节点通过一条边连到父树的根节点。
二、树的实现
根据上面的定义,可以使用以下函数创建并操作二叉树。
- BinaryTree()创建一个二叉树实例。
- getLeftChild()返回当前节点的左子节点所对应的二叉树。
- getRightChild()返回当前节点的右子节点所对应的二叉树。
- setRootVal(val)在当前节点中存储参数val中的对象。
- getRootVal()返回当前节点存储的对象。
- insertLeft(val)新建一颗二叉树,并将其作为当前节点的左子节点。
- insertRight(val)新建一颗二叉树,并将其作为当前节点的右子节点。
实现树的关键在于选择一个好的内部存储技巧。Python提供两种有意思的方式,我们在选择前会仔细了解这两种方式。第一种称作“列表之列表”,第二种称作“节点与引用”。
2.1 列表之列表
在“列表之列表”的树中,我们将根节点的值作为列表的第一个元素;第二个元素是代表左子树的列表;第三个元素是代表右子树的列表。
myTree=['a', #根节点['b', #左子树['d',[],[]],['e',[],[]] ],['c', #右子树['f',[],[]],[] ]]
注意,可以通过标准的列表切片操作访问子树。树的根节点是myTree[0],左子树是myTree[1],右子树是myTree[2]。“列表之列表”表示法有个很好的性质,那就是表示子树的列表结构很符合树的定义,这样的结构是递归的!由一个根节点和两个空列表构成的子树是一个叶子节点。还有一个很好的性质,那就是这种表示法可以推广到有很多子树的情况。如果树不是二叉树,则多一个子树只是多一个列表。

接下来提供一些便于将列表作为树使用的函数,以正式定义树数据结构。注意,我们不是要定义二叉树类,而是要创建可用于标准列表的函数。
列表的函数BinaryTree:
def BinaryTree(r):return [r,[],[]]
BinaryTree函数构造一个简单的列表,它仅有一个根节点和两个作为子节点的空列表。要给树添加左子树,需要在列表的第二个位置加入一个新的列表。请务必当心:如果列表的第二个位置已经有内容了,我们要保留已有内容,并将它作为新列表的左子树。
插入左子树的Python代码:
def insertLeft(root,newBranch):t=root.pop(1)if len(t)>1:root.insert(1,[newBranch,t,[]])else:root.insert(1,[newBranch,[],[]])return root
插入右子树的Python代码:
def insertRight(root,newBranch):t=root.pop(2)if len(t)>1:root.insert(2,[newBranch,[],t])else:root.insert(2,[newBranch,[],[]])return root
为了完整地创建树的函数集,我们编写一些访问函数,用于读写根节点与左右子树。
树的访问函数代码:
def getRootVal(root):return root[0]def setRootVal(root,newVal):root[0]=newValdef getLeftChild(root):return root[1]def getRightChild(root):return root[2]

2.2 节点与引用
树的第二种表示法是利用节点与引用。我们将定义一个类,其中有根节点和左右子树的属性。这种表示法遵循对象编程范式。
#BinaryTree类
class BinaryTree:def __init__(self,rootObj):self.key=rootObjself.leftChild=Noneself.rightChild=None#插入左子节点def insertLeft(self,newNode):if self.leftChild==None:self.leftChild=BinaryTree(newNode)else:t=BinaryTree(newNode)t.left=self.leftChildself.leftChild=t#插入右子节点def insertRight(self,newNode):if self.rightChild==None:self.rightChild=BinaryTree(newNode)else:t=BinaryTree(newNode)t.right=self.rightChildself.rightChild=t#二叉树的访问函数def getRightChild(self):return self.rightChilddef getLeftChild(self):return self.leftChilddef setRootVal(self,obj):self.key=objdef getRootVal(self):return self.key

相关文章:
数据结构 | 树的定义及实现
目录 一、树的术语及定义 二、树的实现 2.1 列表之列表 2.2 节点与引用 一、树的术语及定义 节点: 节点是树的基础部分。它可以有自己的名字,我们称作“键”。节点也可以带有附加信息,我们称作“有效载荷”。有效载荷信息对于很多树算法…...
Delphi7通过VB6之COM对象调用FreeBASIC写的DLL功能
VB6写ActiveX COM组件比较方便,不仅PowerBASIC与VB6兼容性好,Delphi7与VB6兼容性也不错,但二者与FreeBASIC兼容性在字符串处理上差距比较大,FreeBASIC是C化的语言,可直接使用C指令。下面还是以实现MKI/CVI, MKL/CVL, M…...
【Linux 网络】NAT技术——缓解IPv4地址不足
NAT技术 NAT 技术背景NAT IP转换过程NAPTNAT 技术的缺陷 NAT(Network Address Translation,网络地址转换)技术,是解决IP地址不足的主要手段,并且能够有效地避免来自网络外部的攻击,隐藏并保护网络内部的计算…...
Flink 两阶段提交(Two-Phase Commit)协议
Flink 两阶段提交(Two-Phase Commit)是指在 Apache Flink 流处理框架中,为了保证分布式事务的一致性而采用的一种协议。它通常用于在流处理应用中处理跨多个分布式数据源的事务性操作,确保所有参与者(数据源或计算节点…...
【Docker晋升记】No.2 --- Docker工具安装使用、命令行选项及构建、共享和运行容器化应用程序
文章目录 前言🌟一、Docker工具安装🌟二、Docker命令行选项🌏2.1.docker run命令选项:🌏2.2.docker build命令选项:🌏2.3.docker images命令选项:🌏2.4.docker ps命令选项…...
[OnWork.Tools]系列 00-目录
OnWork.Tools系列文章目录 OnWork.Tools系列 01-简介_末叶的博客-CSDN博客OnWork.Tools系列 02-安装_末叶的博客-CSDN博客OnWork.Tools系列 03-软件设置_末叶的博客-CSDN博客OnWork.Tools系列 04-快捷启动_末叶的博客-CSDN博客OnWork.Tools系列 05-系统工具_末叶的博客-CSDN博…...
Cadvisor+InfluxDB+Grafan+Prometheus(详解)
目录 一、CadvisorInfluxDBGrafan案例概述 (一)Cadvisor Cadvisor 产品特点: (二)InfluxDB InfluxDB应用场景: InfluxDB主要功能: InfluxDB主要特点: (三&#…...
AtcoderABC222场
A - Four DigitsA - Four Digits 题目大意 给定一个整数N,其范围在0到9999之间(包含边界)。在将N转换为四位数的字符串后,输出它。如果N的位数不足四位,则在前面添加必要数量的零。 思路分析 可以使用输出流的格式设…...
架构实践方法
一、识别复杂度 将主要的复杂度问题列出来,然后根据业务、技术、团队等综合情况进行排序,优先解决当前面临的最主要的复杂度问题。对于按照复杂度优先级解决的方式,存在一个普遍的担忧:如果按照优先级来解决复杂度,可…...
点淘的MCN机构申请详细入驻指南!
消费趋势的变化,来自消费人群的变化。 后疫情时代,经济复苏的反弹力度不足,人们开始怀疑我们正从前几年的消费升级,跌入消费降级的时代,但这并不能准确概括消费市场的变化。 仔细翻看各大奢侈品集团的财报࿰…...
事务和事务的隔离级别
1.4.事务和事务的隔离级别 1.4.1.为什么需要事务 事务是数据库管理系统(DBMS)执行过程中的一个逻辑单位(不可再进行分割),由一个有限的数据库操作序列构成(多个DML语句,select语句不包含事务&…...
每日一题 34在排序数组中查找元素的第一个和最后一个位置(二分查找)
题目 给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target,返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1&…...
Spring Boot Admin 环境搭建与基本使用
Spring Boot Admin 环境搭建与基本使用 一、Spring Boot Admin是什么二、提供了那些功能三、 使用Spring Boot Admin3.1搭建Spring Boot Admin服务pom文件yml配置文件启动类启动admin服务效果 3.2 common-apipom文件feignhystrix 3.3服务消费者pom文件yml配置文件启动类control…...
JVM之内存模型
1. Java内存模型 很多人将Java 内存结构与java 内存模型傻傻分不清,java 内存模型是 Java Memory Model(JMM)的意思。 简单的说,JMM 定义了一套在多线程读写共享数据时(成员变量、数组)时,对数据…...
音视频 vs2017配置FFmpeg
vs2017 ffmpeg4.2.1 一、首先我把FFmpeg整理了一下,放在C盘 二、新建空项目 三、添加main.cpp,将bin文件夹下dll文件拷贝到cpp目录下 #include<stdio.h> #include<iostream>extern "C" { #include "libavcodec/avcodec.h&…...
【项目管理】PMP备考宝典-第二章《环境》
第一节:概述 1.项目所处的组织环境 (1)事业环境因素(EEFs) 组织内部的事业环境因素: 企业都会有愿景、使命、价值观,这些决定了企业的发展方向。不忘初心,坚定地走自己的路&#…...
ELK 将数据流转换回常规索引
ELK 将数据流转换回常规索引 现象:创建索引模板是打开了数据流,导致不能创建常规索引,并且手动修改、删除索引模板失败 "reason" : "composable template [logs_template] with index patterns [new-pattern*], priority [2…...
jackson库收发json格式数据和ajax发送json格式的数据
一、jackson库收发json格式数据 jackson库是maven仓库中用来实现组织json数据功能的库。 json格式 json格式一个组织数据的字符文本格式,它用键值对的方式存贮数据,json数据都是有一对对键值对组成的,键只能是字符串,用双引号包…...
ubuntu安装和卸载CLion
安装 在https://www.jetbrains.com/clion/download/#sectionlinux下载相应版本的安装包,解压之后,找到解压文件夹中的bin文件夹运行./clion.sh 卸载 使用sudo rm -rf删除以下内容;并把刚刚解压的文件删掉 ~/.config/JetBrains ~/.local/s…...
Petrel解释二维浅地层数据
Petrel是斯伦贝谢开发的一款地质解释和建模软件,有点像地理信息系统的ArcGIS,主要用于数据分析和展示。它不是用来处理原始数据的,而是集成各种处理后的结果数据进行特征分析和目标拾取。当然,它也能读取原始数据,比如…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
