数据结构之树与二叉树

devtools/2024/11/24 1:25:12/

华子目录

  • 1.树和二叉树的定义
    • 1.1树的定义
    • 1.2树的基本术语
    • 1.3线性结构和树结构
    • 1.4二叉树的定义
  • 2.二叉树的性质和存储结构
    • 2.1二叉树的性质
    • 2.2二叉树的存储结构
      • 2.2.1顺序存储
      • 2.2.2链式存储
    • 2.3遍历二叉树
    • 2.4大作业:二叉树的基本操作
      • 2.4.1代码思路(仅供参考,思路不限):
      • 2.4.2代码实践(递归写法)

1.树和二叉树的定义

1.1树的定义

nn≥0)个结点有限集或为空树n=0);或为非空树,对于非空树T

  • 有且仅有一个称之为结点
  • 根结点以外的其余结点可分为mm>0)个互不相交有限集T₁,T₂,…,Tm,其中每一个结点本身又是一棵树,并且成为子树

在这里插入图片描述
图 1(A) 是使用树结构存储的集合{A,B,C,D,E,F,G,H,I,J,K,L,M}示意图。对于数据A来说,和数据B、C、D有关系;对于数据B来说,和E、F有关系。这就是“一对多”的关系。将具有“一对多”关系的集合中的数据元素按照图 1(A)的形式进行存储,整个存储形状逻辑结构上看,类似于实际生活中倒着的树图 1(B)),所以称这种存储结构为“树型”存储结构

1.2树的基本术语

  • 结点中的一个独立单元。包含一个数据元素若干指向其子树分支,如图1(A)中的A、B、C、D
  • 结点的度结点拥有的子树数成为结点的度。例如,A的度3C的度1F的度0
  • 树的度树的度树内各结点度最大值图1(A)所示的树的度3
  • 叶子0结点称为叶子终端结点结点K、L、F、G、M、I、J都是树的叶子叶子结点孩子
  • 非终端结点度不为0结点称为非终端结点
  • 双亲和孩子结点的子树称为该结点孩子,相应地,该结点称为孩子双亲。例如,B的双亲AB的孩子E和F
  • 兄弟同一个双亲孩子之间互称兄弟。例如,H、I和J互为兄弟
  • 祖先:从该结点所经分支上所有结点。例如,M的祖先A、D和H
  • 子孙:以某结点子树中任一结点都称为该结点的子孙。如B的子孙E、K、L和F
  • 层次结点层次开始定义起第一层根的孩子第二层
  • 堂兄弟双亲同一层结点互为堂兄弟。例如,结点GE、F、H、I、J互为堂兄弟
  • 树的深度树中结点最大层次称为树的深度高度图1(A)所示的树的深度4
  • 有序树无序树:如果将树中结点各子树看成从左至右有次序的(即不能互换),则称该树有序树,否则称为无序树。在有序树最左边子树称为第一个孩子最右边的称为最后一个孩子
  • 森林:是mm≥0)棵互不相交树的集合。把树的根节点删除,它的子树们就构成了森林

1.3线性结构和树结构

线性结构树结构
第一个数据元素无前驱根结点无双亲
最后一个数据元素无后继叶子结点无孩子
其他数据元素一个前驱一个后继一对一其他结点(中间结点)一个双亲多个孩子一对多

1.4二叉树的定义

二叉树nn≥0)个结点所构成的集合,它或为空树n=0);或为非空树,对于非空树

  • 有且仅有一个称之为根的结点
  • 根结点以外其余结点分为两个互不相交的子集T₁和T₂,分别称为T左子树右子树,且T₁T₂本身又都是二叉树

二叉树一样具有递归性质二叉树的区别主要有以下两点

  • 二叉树每个结点至多只有两棵子树(即二叉树中不存在度大于2结点
  • 二叉树子树左右之分,其次序不能任意颠倒

二叉树的递归定义表明二叉树或为,或是由一个根结点加上两棵分别称为左子树右子树的、互不想交二叉树组成。由于这两棵子树也是二叉树,则由二叉树的定义,它们也可以是空树。由此,二叉树可以有5种基本形态,如下图所示:

在这里插入图片描述

树的基本术语是都适用于二叉树的

2.二叉树的性质和存储结构

2.1二叉树的性质

二叉树具有以下几个性质:

在这里插入图片描述
二叉树还有两种特殊的形态满二叉树完全二叉树

  • 二叉树中除了叶子结点每个结点都为2,则此二叉树称为满二叉树

在这里插入图片描述

  • 二叉树中除去最后一层节点满二叉树,且最后一层结点依次从左到右分布,则此二叉树被称为完全二叉树

在这里插入图片描述

  • 满二叉树一定是完全二叉树完全二叉树不一定是满二叉树

2.2二叉树的存储结构

  • 二叉树的存储结构两种,分别为顺序存储链式存储

2.2.1顺序存储

  • 二叉树顺序存储,指的是使用顺序表数组)存储二叉树。需要注意的是,顺序存储只适用于完全二叉树。换句话说,只有完全二叉树才可以使用顺序表存储。因此,如果我们想顺序存储普通二叉树,需要提前将普通二叉树转化为完全二叉树
  • 普通二叉树完全二叉树的方法很简单,只需给二叉树额外添加一些节点,将其"拼凑"成完全二叉树即可。如下图所示,左侧普通二叉树右侧转化后完全(满)二叉树

在这里插入图片描述
解决了二叉树转化问题,接下来我们来学习如何顺序存储完全(满)二叉树完全二叉树顺序存储,仅需从根节点开始,按照层次依次将树中节点存储到数组即可

在这里插入图片描述
例如,存储上图所示的完全二叉树,其存储状态下图所示:
在这里插入图片描述
由此,我们就实现了完全二叉树顺序存储

2.2.2链式存储

其实二叉树不合适数组存储,因为并不是每个二叉树都是完全二叉树普通二叉树使用顺序表存储会存在空间浪费的现象。接下来介绍二叉树链式存储结构
在这里插入图片描述
上图为一颗普通的二叉树,若将其采用链式存储,则只需从树的根节点开始,将各个节点及其左右孩子使用链表存储即可。因此,其对应的链式存储结构如下图所示:
在这里插入图片描述
由上图可知,采用链式存储二叉树时,其节点结构3部分构成:

  • 指向左孩子节点指针Lchild
  • 节点存储的数据data
  • 指向右孩子节点指针Rchild

其实,二叉树链式存储结构远不止上图所示的这一种。例如,在某些实际场景中,可能会做 “查找某节点的父节点” 的操作,这时可以在节点结构中再添加一个指针域,用于各个节点指向其父亲节点,如下图 所示:
在这里插入图片描述

2.3遍历二叉树

  • 二叉树的一些应用中,常常要求在树中查找具有某种特征结点,或者是对树中全部结点逐一处理,这就提出了一个遍历二叉树问题遍历二叉树是指按某一条搜索路径巡访树中每个结点,使得每个结点均被访问一次,而且仅被访问一次遍历二叉树二叉树最基本的操作,也是二叉树其他各种操作基础遍历的实质是对二叉树进行线性化的过程,即遍历的结果是将非线性结构树中结点排成一个线性序列。由于二叉树每个结点都有可能有两棵子树,因而需要寻找一种规律,以便使二叉树上的结点排列在一个线性队列上,从而便于遍历
  • 二叉树是有基本单元组成:根节点、左子树、右子树。因此,若能依次遍历三部分,便是遍历了整个二叉树。假如L、D、R分别表示遍历左子树、访问根节点、遍历右子树,则可有DLR、LDR、LRD、DRL、RDL、RLD6种遍历二叉树的方案。若限定先左后右,则只有前3种情况,分别称之为先(根)序遍历中(根)序遍历后(根)序遍历

基于二叉树递归定义,可得下述遍历二叉树递归算法定义。

先序遍历二叉树的操作定义如下:
  若二叉树,则空操作;否则
  (1)访问根节点
  (2)先序遍历左子树
  (3)先序遍历右子树

中序遍历二叉树操作定义如下:
  若二叉树,则空操作;否则
  (1)中序遍历左子树
  (2)访问根节点
  (3)中序遍历右子树

后序遍历二叉树的操作定义如下:
  若二叉树,则空操作;否则
  (1)后序遍历左子树
  (2)后序遍历右子树
  (3)访问根节点

在这里插入图片描述
例如,上图的二叉树表示的为表达式:a+b*(c-d)-e/f

  • 先序遍历二叉树,可得到二叉树先序序列为:-+a*b-cd/ef
  • 中序遍历二叉树,可得此二叉树中序序列为:a+b*c-d-e/f
  • 后序遍历二叉树,可得此二叉树后序序列为:abcd-*+ef/-

2.4大作业:二叉树的基本操作

构建二叉树(遍历列表按照先序顺序插入值)

测试案例输入列表[‘A’,‘B’,‘C’,’#’,’#’,‘D’,‘E’,’#’,‘G’,’#’,’#’,‘F’,’#’,’#’,’#’],输出的遍历结果见下图

在这里插入图片描述

二叉树的生成,需要用以上输入列表的数值哦;对于非递归遍历,需要用到

2.4.1代码思路(仅供参考,思路不限):

二叉树生成

  • 构建结点类,构建二叉树类
  • 输入一个列表,然后从列表取数,按照先序顺序进行递归插入数值,即先创建根结点,再左子树,再右子树
  • 首先输入一个字符,判断其是否为,不是的即创建根结点该结点数值域该字符,继续递归生成左子树,输入第二个字符,判断其是否为,不是的即生成结点,是的将返回上一层递归,如此判断递归生成二叉树

二叉树遍历

  • 按照先序、中序、后序遍历顺序输出字符即可
  • 非递归的遍历是需要借助栈的
  • 中序遍历非递归算法思想来举例:定义一个空栈,从根结点开始访问,若当前节点非空,则将该节点压栈并访问其左子树循环执行,直至当前节点时,取栈顶元素访问并弹栈,然后访问其右子树,再重复如上操作,直至遍历节点的指针为空并且栈也为空

2.4.2代码实践(递归写法)

python">class Tree:def __init__(self, item):self.item = itemself.l = Noneself.r = Nonedef llink(self, other):  #左连接子节点self.l = otherdef rlink(self, other): # 右连接子节点self.r = otherdef get_depth(self): # 获取深度(递归)if self.l == None:l_depth = 0else:l_depth = self.l.get_depth()if self.r == None:r_depth = 0else:r_depth = self.r.get_depth()return max(l_depth, r_depth) + 1def get_len(self):  # 获取节点数(递归)if self.l == None:l_len = 0else:l_len = self.l.get_len()if self.r ==None:r_len = 0else:r_len = self.r.get_len()return l_len + r_len + 1def show_first(self):  # 先序遍历(递归)print(self.item, end=" ")if self.l != None:self.l.show_first()if self.r != None:self.r.show_first()def show_mid(self):  # 中序遍历(递归)if self.l != None:self.l.show_mid()print(self.item, end=" ")if self.r != None:self.r.show_mid()def show_last(self):  # 后序遍历(递归)if self.l != None:self.l.show_last()if self.r != None:self.r.show_last()print(self.item, end=" ")def create(x):try:tmp = next(x)if tmp == "#":returnroot = Tree(tmp)root.llink(create(x))root.rlink(create(x))return rootexcept:passtree_list = ['A', 'B', 'C', '#', '#', 'D', 'E', '#', 'G', '#', '#', 'F', '#', '#', '#']
it = iter(tree_list)
root = create(it)# 先序遍历
print(root.show_first())# 中序遍历
print(root.show_mid())# 后序遍历
print(root.show_last())

http://www.ppmy.cn/devtools/136423.html

相关文章

[js] 0.1+0.2

0.10.2≠0.3?? 无可避免的浮点误差 【前端面试】为什么 0.1 0.2 不等于 0.3 计算机是通过二进制的方式存储数据的,所以计算机计算 0.1 0.2 的时候,实际上是计算的两个数的二进制的和。0.1 的二进制是0.0001100110011001100…(1100 循环&…

计算机毕业设计 | SpringBoot+vue汽车资讯网站 汽车购买咨询管理系统(附源码+论文)

1,绪论 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及,互联网成为人们查找信息的重要场所,二十一世纪是信息的时代,所以信息的管理显得特别重要。因此,使用计算机来管理汽车资讯网站的相关信息成为必然…

深度解析FastDFS:构建高效分布式文件存储的实战指南(上)

文章目录 一、FastDFS简介1.1 概述1.2 特性 二、FastDFS原理架构2.1 FastDFS角色2.2 存储策略2.3 上传过程2.4 文件同步2.5 下载过程 三、FastDFS适用场景四、同类中间件对比4.1 FastDFS和集中存储方式对比4.2 FastDFS与其他文件系统的对比 五、FastDFS部署5.1 单机部署5.1.1 使…

xiaolin coding 图解网络笔记——HTTP篇

1. HTTP 是什么? HTTP 是超文本传输协议(HyperText Transfer Protocol),一个用在计算机世界里专门在【两点】之间【传输】文字、图片、音频、视频等【超文本】数据的【约定和规范】。 2. HTTP 常见的状态码有哪些? …

内容分发网络CDN、动态内容缓存简介

概述 CDN,Content Delivery Network,内容分发网络。使用户可就近取得所需内容,解决网络拥挤状况,提高用户访问网站的响应速度。CDN更智能的镜像缓存流量导流。 核心功能: 加速静态资源加载(如图片、视频…

uniApp项目运行到鸿蒙手机,应用图标一直是H,应用名一直是HBuilder问题

项目运行到鸿蒙手机,应用图标一直是H,应用名一直是HBuilder问题 应用运行到鸿蒙手机和鸿蒙模拟器,应用图标一直是H,应用名一直是HBuilder,在自动生成的harmony-configs文件夹下也没有配置的文件, 这时候需要你将DevEco Studio 下…

【专题】中国企业出海洞察报告暨解码全球制胜之道报告汇总PDF洞察(附原数据表)

原文链接:https://tecdat.cn/?p38314 在当今全球化的浪潮中,中国企业的出海行动正以前所未有的规模和速度展开,成为全球经济舞台上的重要力量。本报告旨在对 2024 年中国企业出海情况进行深度洞察,涵盖多个领域和视角。 从对外投…

ansible playbook安装nacos

目录 1.创建nacos应用相关的用户 2.创建rocketmq所需目录任务 3.安装JDK1.8、python以及虚拟环境安装PyMysql(用于执行数据库脚本) 4. 解压nacos 5.创建nacos数据库 6.上传sql文件 7.创建数据库表 8.启动nacos 9.nacos集群主机ip配置 10.变量配置 11.配置nacos.yml 更…