【数据结构4】树的实例-模拟文件系统、二叉树的遍历(先序遍历、中序遍历、后序遍历、层次遍历)

本文主要是介绍【数据结构4】树的实例-模拟文件系统、二叉树的遍历(先序遍历、中序遍历、后序遍历、层次遍历),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1 树和二叉树
2 树的实例-模拟文件系统
3 二叉树
3.1 二叉树的遍历
二叉树的先序遍历
二叉树的中序遍历
二叉树的后序遍历
二叉树的层次遍历

1 树

树是一种数据结构
比如:目录结构
树是一种可以递归定义的数据结构树是由n个节点组成的集合:如果n=0,那这是一棵空树;如果n>0,那存在1个节点作为树的根节点,其他节点可以分为m个集合,每个集合本身又是一棵树

在这里插入图片描述

2 树的实例-模拟文件系统

class Node:"""表示文件系统树中的一个节点。属性:name (str): 节点的名称。对于目录,它以 '/' 结尾,对于文件,不以 '/' 结尾。type (str): 节点的类型,'dir' 代表目录,'file' 代表文件。children (list): 该节点的子节点列表。仅对目录节点有效。parent (Node): 该节点的父节点。如果是根节点,则为 None。"""def __init__(self, name, type='dir'):"""初始化一个新的节点。:param name: 节点的名称。目录名称通常以 '/' 结尾,文件名称不以 '/' 结尾。:param type: 节点的类型。默认为 'dir'(目录),可以设置为 'file'(文件)以表示文件节点。"""self.name = nameself.type = typeself.children = []  # 初始化为空列表,目录节点可以包含子节点self.parent = None  # 父节点初始化为 Nonedef __repr__(self):return self.nameclass FileSystemTree:"""表示一个文件系统树,支持创建目录、列出目录内容以及切换目录等操作。属性:root (Node): 文件系统树的根节点,初始化时创建。now (Node): 当前工作目录。操作会影响该目录。"""def __init__(self):"""初始化文件系统树,创建根目录,并将当前工作目录设置为根目录。"""self.root = Node("/")  # 创建根目录,名称为 "/"self.now = self.root  # 将当前工作目录设置为根目录def mkdir(self, name):"""在当前工作目录下创建一个新的目录。:param name: 新目录的名称。必须以 '/' 结尾。如果没有结尾的 '/', 会自动添加。"""if name[-1] != "/":  # 检查目录名称是否以 '/' 结尾name += '/'  # 添加 '/' 以确保目录名称正确node = Node(name)  # 创建新的目录节点self.now.children.append(node)  # 将新目录添加到当前工作目录的子节点列表中node.parent = self.now  # 设置新目录的父节点为当前工作目录def ls(self):"""展示当前工作目录下的所有子节点。:return: 当前目录下的子节点列表(包括目录和文件)。"""return self.now.children  # 返回当前目录的子节点列表def cd(self, name):"""切换到指定的目录。支持绝对路径和相对路径。:param name: 目标目录的路径。可以是绝对路径(以 '/' 开头)或相对路径(不以 '/' 开头)。:return: 无返回值。成功切换目录时,更新当前工作目录。:raises ValueError: 如果指定的路径无效或目录不存在,抛出异常。"""if name[-1] != "/":  # 确保目录名称以 '/' 结尾name += '/'# 处理路径components = name.split('/')  # 将路径分解为各个部分node = self.now  # 从当前工作目录开始遍历for component in components:if component == '..':# 如果路径部分是 '..',则返回到上一级目录if node.parent is not None:node = node.parentelif component and component != '/':# 如果路径部分是有效的目录名,则查找该目录found = Falsefor child in node.children:if child.name == component + '/':node = child  # 找到目标目录,更新当前节点found = Truebreakif not found:# 如果没有找到目标目录,则抛出异常raise ValueError('无效的目录')self.now = node  # 更新当前工作目录为目标目录tree = FileSystemTree()
tree.mkdir('var/')
tree.mkdir('bin/')
tree.mkdir('bin/python')
tree.mkdir('usr/')print(tree.root.children)
print(tree.ls())
print(tree.cd('bin/'))
tree.cd("../")
print(tree.ls())

3 二叉树

二叉树的链式存储:将二叉树的节点定义为一个对象,节点之间通过类似链表的链接方式来连接。节点定义:
class BiTreeNode:def __init__(self, data):self.data = dataself.lchild = Noneself.rchild = None

**实现这棵二叉树**
在这里插入图片描述

class BiTreeNode:def __init__(self, data):self.data = dataself.lchild = None  # 左孩子self.rchild = None  # 右孩子a = BiTreeNode('A')
b = BiTreeNode('B')
c = BiTreeNode('C')
d = BiTreeNode('D')
e = BiTreeNode('E')
f = BiTreeNode('F')
g = BiTreeNode('G')e.lchild = a
e.rchild = g
a.rchild = c
c.lchild = b
c.rchild = d
g.rchild = froot = e
print(root.lchild.rchild.data)

3.1 二叉树的遍历

在这里插入图片描述

二叉树的前序遍历

def pre_order(root):"""二叉树的前序遍历:param root::return:"""if root:print(root.data, end=',')pre_order(root.lchild)pre_order(root.rchild)pre_order(root)  # E,A,C,B,D,G,F,

二叉树的中序遍历

def mid_order(root):"""二叉树的中序遍历:param root::return:"""if root:mid_order(root.lchild)print(root.data, end=',')mid_order(root.rchild)mid_order(root)  # A,B,C,D,E,G,F,

二叉树的后序遍历

def post_order(root):"""二叉树的后序遍历:param root::return:"""if root:post_order(root.lchild)post_order(root.rchild)print(root.data, end=',')post_order(root)  # A,C,B,D,G,F,E

二叉树的层次遍历

from collections import dequedef level_order(root):"""层次遍历二叉树的函数:param root: 二叉树的根节点:return: None"""# 初始化一个队列,用于层次遍历queue = deque()# 将根节点入队queue.append(root)# 当队列不为空时,继续遍历while len(queue) > 0:# 从队列中取出一个节点node = queue.popleft()# 打印当前节点的数据print(node.data, end=',')# 如果当前节点有左子节点,将左子节点入队if node.lchild:queue.append(node.lchild)# 如果当前节点有右子节点,将右子节点入队if node.rchild:queue.append(node.rchild)level_order(root)  # E,A,G,C,F,B,D,

这篇关于【数据结构4】树的实例-模拟文件系统、二叉树的遍历(先序遍历、中序遍历、后序遍历、层次遍历)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1104235

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

springboot security验证码的登录实例

《springbootsecurity验证码的登录实例》:本文主要介绍springbootsecurity验证码的登录实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录前言代码示例引入依赖定义验证码生成器定义获取验证码及认证接口测试获取验证码登录总结前言在spring

tomcat多实例部署的项目实践

《tomcat多实例部署的项目实践》Tomcat多实例是指在一台设备上运行多个Tomcat服务,这些Tomcat相互独立,本文主要介绍了tomcat多实例部署的项目实践,具有一定的参考价值,感兴趣的可... 目录1.创建项目目录,测试文China编程件2js.创建实例的安装目录3.准备实例的配置文件4.编辑实例的

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

Spring 中使用反射创建 Bean 实例的几种方式

《Spring中使用反射创建Bean实例的几种方式》文章介绍了在Spring框架中如何使用反射来创建Bean实例,包括使用Class.newInstance()、Constructor.newI... 目录1. 使用 Class.newInstance() (仅限无参构造函数):2. 使用 Construc

Linux中的缓冲区和文件系统详解

《Linux中的缓冲区和文件系统详解》:本文主要介绍Linux中的缓冲区和文件系统方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、FILE结构1、fd2、缓冲区二、文件系统1、固态硬盘2、逻辑地址LBA(一)数据块 Data blocks(二)inode表

MyBatis-Plus中Service接口的lambdaUpdate用法及实例分析

《MyBatis-Plus中Service接口的lambdaUpdate用法及实例分析》本文将详细讲解MyBatis-Plus中的lambdaUpdate用法,并提供丰富的案例来帮助读者更好地理解和应... 目录深入探索MyBATis-Plus中Service接口的lambdaUpdate用法及示例案例背景

MyBatis-Plus中静态工具Db的多种用法及实例分析

《MyBatis-Plus中静态工具Db的多种用法及实例分析》本文将详细讲解MyBatis-Plus中静态工具Db的各种用法,并结合具体案例进行演示和说明,具有很好的参考价值,希望对大家有所帮助,如有... 目录MyBATis-Plus中静态工具Db的多种用法及实例案例背景使用静态工具Db进行数据库操作插入

CSS模拟 html 的 title 属性(鼠标悬浮显示提示文字效果)

《CSS模拟html的title属性(鼠标悬浮显示提示文字效果)》:本文主要介绍了如何使用CSS模拟HTML的title属性,通过鼠标悬浮显示提示文字效果,通过设置`.tipBox`和`.tipBox.tipContent`的样式,实现了提示内容的隐藏和显示,详细内容请阅读本文,希望能对你有所帮助... 效