首页 > 其他分享 >数据结构 --树

数据结构 --树

时间:2024-11-08 12:40:54浏览次数:4  
标签:左子 结点 路径 -- 右子 二叉 二叉树 数据结构

定义

树是n(n>=0)个结点的有限集。n=0时,称为空树。在任意一棵树非空树中应满足:

(1) 有且仅有一个特定的称为根 (root) 的结点

(2) 当时,其余结点可分为个互不相交的有限集,其中每一个集合本身又是一颗树,并且称为根的子树。

基本概念

结点的度:一个结点拥有的子树的数目

叶子结点:度为0的结点

树的度:树内各结点的度的最大值

树的深度或高度:树中结点的最大层次

森林:由m(>=0)棵互不相交的树的集合称为森林

有序树和无序树:树中结点的各子树从左到右是有次序的,不能互换,称该树为有序树,否则称为无序树

路径和路径长度:路径是由树中的两个结点之间的结点序列构成的。而路径长度是路径上所经过的边的个数

树的类型

二叉树

二叉树的特点包括:

(1)每个结点最多有两个子结点,分别称为左子结点和右子结点。

(2)左子树和右子树都是二叉树,它们本身也可以是空树。

(3)二叉树的结点结构包含一个数据元素和指向左右子树的指针。

二叉树和度为2的树

1.度为2的树至少有一个结点度数为2,而二叉树可以为空

2.度为2的树不区分左右子树

二叉排序树(二叉查找树/二叉搜索树)

(1)若左子树不空,则左子树上所有结点的值均小于它的 根结点的值;

(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;

(3)左,右子树也分别为二叉排序树;

平衡二叉树(AVL树)

平衡二叉树特点包括:

- 左子树和右子树的高度之差的绝对值小于等于1

- 左子树和右子树也是平衡二叉树

标签:左子,结点,路径,--,右子,二叉,二叉树,数据结构
From: https://www.cnblogs.com/hui-xiang/p/18534165

相关文章

  • PySpark中的StructStreaming的使用
    使用pyspark编写StructStreaming的入门案例,如有雷同,纯属巧合,所有代码亲测可用。一、SparkStreaming的不足1.基于微批,延迟高不能做到真正的实时2.DStream基于RDD,不直接支持SQL3.流批处理的API应用层不统一,(流用的DStream-底层是RDD,批用的DF/DS/RDD)4.不支持EventTi......
  • 数字IC后端笔试面试必备 | 低功耗设计实现十大灵魂拷问
    在IC低功耗设计实现中我们经常会涉及到powergatingcell,isolationcell,levelshiftercell。所以在实现过程中就会涉及这类cell的选型,摆放要求,secondarypgpin绕线要求等等。为了让大家全面掌握低功耗实现相关技术要点,下面罗列下面十个非常经典的灵魂拷问,供大家来自测。如......
  • Python数据分析NumPy和pandas(二十六、数据整理--连接、合并和重塑 之三:重塑和透视)
    对表格数据的重新排列操作,称为reshape或pivot。有很多种方法对表格数据进行重塑。一、使用分层索引进行reshape分层索引提供了一种在DataFrame中重新排列数据的方法。主要有两个函数方法:stack:将数据中的列旋转或透视到行。unstack:从行转为列。还是用代码示例来学习......
  • 一个非常有趣的挑战——物联网与AI结合的超级项目
    想要实现这个物联网与AI结合的超级项目,你需要准备一些硬件和软件环境,可以不同,我只是最近在学这个就以这个举例。以下是一个详细的清单,列出了所需的硬件和软件组件:硬件需求嵌入式设备开发板:例如STM32Nucleo板(如NUCLEO-F103RB)或其他支持Rust的嵌入式开发板。传感器:温......
  • 约瑟夫生者死者游戏问题
    C++使用单向循环链表解决需要实现节点的插入和删除——我为++做实事1、节点定义:structnode{  intnumber;//表示序号  node*next;};2、节点的插入:为每个节点(人)发放生死序号:index考虑链表为空和不为空的情况voidinsert_Node(node*&head,intindex)......
  • 洛谷P1157 组合的输出(Python)
    伤痕,是男子汉的勋章。——圣斗士星矢一、题目P1157组合的输出https://www.luogu.com.cn/problem/P1157二、代码defpri(L):foriinrange(len(L)):ifL[i]==True:print("{:3d}".format(i),end='')defdfs(n,r,cur,count):#n,r为题......
  • 人工智能--自然语言处理简介
    上一篇:《人工智能模型训练中的数据之美——探索TFRecord》序言:自然语言处理(NLP)是人工智能中的一种技术,专注于理解基于人类语言的内容。它包含了编程技术,用于创建可以理解语言、分类内容,甚至生成和创作人类语言的新作品的模型。在接下来的几章中,我们将会探讨这些技术。此外,现在有......
  • c++多态学习:多态含义与使用
    目录 多态的概念多态的定义多态的实现注意事项 多态的概念多态是面向对象编程中的一个重要概念,它指的是同一个行为具有多个不同表现形式或形态的能力。在C++中,多态主要通过虚函数来实现,允许将子类类型的指针赋值给父类类型的指针,并在运行时根据实际对象类型调用相......
  • 251 麦当劳
    //704麦当劳.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。///*http://oj.daimayuan.top/course/5/problem/251喜欢吃麦当劳的蜗蜗要在学校呆n天,如果第i天蜗蜗吃到了麦当劳,他可以获得ai点快乐值。然而蜗蜗不能吃太多麦当劳,在连续的m天中,他最......
  • Vuex的基本使用
    文章目录一、Vuex概述1.是什么2.使用场景3.优势4.注意二、如何构建vuex多组件共享数据环境1.创建项目2.创建三个组件3.源代码三、vuex的使用-创建仓库1.安装vuex2.新建`store/index.js`专门存放vuex3.创建仓库`store/index.js`4在main......