【数据结构】树与二叉树(一):树(森林)的基本概念:父亲、儿子、兄弟、后裔、祖先、度、叶子结点、分支结点、结点的层数、路径、路径长度、结点的深度、树的深度

本文主要是介绍【数据结构】树与二叉树(一):树(森林)的基本概念:父亲、儿子、兄弟、后裔、祖先、度、叶子结点、分支结点、结点的层数、路径、路径长度、结点的深度、树的深度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 5.1 树的基本概念
    • 5.1.1 树的定义
      • 有序树、无序树
    • 5.1.2 森林的定义
    • 5.1.3 树的术语
      • 1. 父亲(parent)、儿子(child)、兄弟(sibling)、后裔(descendant)、祖先(ancestor)
      • 2. 度(degree)、叶子节点(leaf node)、分支节点(internal node)
      • 3. 结点的层数
      • 4. 路径、路径长度、结点的深度、树的深度
    • 5.1.4 树的表示
      • 1.树形表示法
      • 2.嵌套集合表示法
      • 3.嵌套括号表示法
      • 4.凹入表示法

5.1 树的基本概念

5.1.1 树的定义

  • 一棵树是结点的有限集合T:
    • 若T非空,则:
      • 有一个特别标出的结点,称作该树的,记为root(T);
      • 其余结点分成若干个不相交的非空集合T1, T2, …, Tm (m>0),其中T1, T2, …, Tm又都是树,称作root(T)的子树
        • 在这里插入图片描述
    • T 空时为空树,记作root(T)=NULL。

有序树、无序树

  如果子树T1, T2, …, Tm 的相对次序被指明,则称该树为有序树,否则称为无序树
  在有序树中,把Ti (1≤i≤m)称作根的第 i 个子树。因为计算机表示定义了树的一种隐含次序,所以大多数情况下假定所讨论的树都是有序的,除非另有说明。

  • 如果是有序树,那么两者是不同的;如果是无序树,那么两者是相同的。
    在这里插入图片描述

5.1.2 森林的定义

  一个森林是0棵或多棵不相交(非空)树的集合,通常是一个有序的集合。换句话说,森林由多个树组成,这些树之间没有交集,且可以按照一定的次序排列。在森林中,每棵树都是独立的,具有根节点和子树,树与树之间没有直接的连接关系。
  森林是树的扩展概念,它是由多个树组成的集合。在计算机科学中,森林也被广泛应用于数据结构和算法设计中,特别是在图论和网络分析等领域。

5.1.3 树的术语

1. 父亲(parent)、儿子(child)、兄弟(sibling)、后裔(descendant)、祖先(ancestor)

在这里插入图片描述

  • 这些术语用于描述节点之间的关系和层次结构

    • 每个节点都是它的子树的根节点的父亲
    • 反过来,每个节点都是它父亲的儿子
    • 具有相同父亲的节点称为兄弟
    • 每个节点都是它子树中所有节点的祖先
    • 反过来,每个节点都是它祖先的后裔
  • 节点之间的父子关系和兄弟关系可以帮助我们理解树的结构和遍历算法

  • 祖先和后裔的概念则用于描述节点之间的历史关系和衍生关系。

2. 度(degree)、叶子节点(leaf node)、分支节点(internal node)

在这里插入图片描述

  • 一个节点的儿子的个数称为该节点的次数
  • 如果一个节点的度为0,则它被称为终端节点叶子节点(在严格意义上,非根的终端节点称为叶子节点)。
  • 非终端节点称为分支节点

  在图5.1中,节点B有一个子树,其度为1;节点A有三个子树,其度为3;因此,这棵树的度为3,可以称为3元树(3-ary tree)。叶子节点是度为0的节点,例如在图5.1中,节点F、G、H和I是叶子节点,而节点A、B、C、D和E是分支节点。

3. 结点的层数

  • 结点的层数是根据递归定义来确定的:
    • 根节点的层数为0。
    • 其余节点的层数是其父节点的层数加1。
  • 根节点位于第0层,它的子节点位于第1层,子节点的子节点位于第2层,依此类推。
    在这里插入图片描述

4. 路径、路径长度、结点的深度、树的深度

  • 路径是指结点序列v1, v2, …, vk,其中每个节点vi是节点vi+1的父节点(1 ≤ i < k)。
  • 路径长度是指路径经过的边数,即k-1。
  • 结点vi的深度是指从根节点到结点vi的路径长度 D e p t h ( i ) Depth(i) Depth(i)
  • 一棵树的深度是指树中所有节点深度的最大值: m a x i = 1 , … , n D e p t h ( i ) max_{i=1,…, n}Depth(i) maxi=1,,nDepth(i)

在这里插入图片描述
  图5.1的树中,结点序列A, B, E是结点A到结点E的路径,路经长度为2,结点E的深度为2,树的深度为3。

5.1.4 树的表示

1.树形表示法

class TreeNode:def __init__(self, value):self.value = valueself.children = []# 创建一个树
root = TreeNode('A')
node1 = TreeNode('B')
node2 = TreeNode('C')
node3 = TreeNode('D')root.children.append(node1)
root.children.append(node2)
node2.children.append(node3)

2.嵌套集合表示法

tree = {'value': 'A','children': [{'value': 'B','children': []},{'value': 'C','children': [{'value': 'D','children': []}]}]
}

3.嵌套括号表示法

tree_str = '((A (B C)) D)'

4.凹入表示法

def print_tree(node, level=0):if node is None:returnprint('  ' * level + str(node.value))for child in node.children:print_tree(child, level + 1)print_tree(root)

这篇关于【数据结构】树与二叉树(一):树(森林)的基本概念:父亲、儿子、兄弟、后裔、祖先、度、叶子结点、分支结点、结点的层数、路径、路径长度、结点的深度、树的深度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

分辨率三兄弟LPI、DPI 和 PPI有什么区别? 搞清分辨率的那些事儿

《分辨率三兄弟LPI、DPI和PPI有什么区别?搞清分辨率的那些事儿》分辨率这个东西,真的是让人又爱又恨,为了搞清楚它,我可是翻阅了不少资料,最后发现“小7的背包”的解释最让我茅塞顿开,于是,我... 在谈到分辨率时,我们经常会遇到三个相似的缩写:PPI、DPI 和 LPI。虽然它们看起来差不多,但实际应用

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod