【树——数据结构】

embedded/2024/11/15 8:34:43/

文章目录

      • 1.基本概念
      • 2.基本术语
          • 1.结点之间的关系描述
          • 2.结点,树的属性描述
          • 3.有序树,无序树
          • 4.森林
      • 3.树的性质
          • 考点1
          • 考点2
          • 考点3
          • 考点4
      • 4.树的存储结构
      • 5.树和森林的遍历

1.基本概念

结点,根节点,分支结点,叶子结点,边,子树
空树:节点数为0的树

非空树的特性

  1. 有且仅有一个根节点
  2. 没有后继的结点称为叶子结点
  3. 有后继的结点称为分支结点
  4. 除了根节点外,任何一个结点都有且仅有一一个前驱

树是一种递归定义的数据结构

2.基本术语

1.结点之间的关系描述
  1. 祖先结点/子孙结点
  2. 双亲结点(父节点) /孩子结点
  3. 兄弟结点/堂兄弟结点
  4. 两个节点之间的路径:只能从上往下
  5. 路径长度:路径上经过几条边
  6. 树的路径长度:从树根到每个结点的路径长度的总和
2.结点,树的属性描述
  1. 结点的层次(深度) :从上往下数
  2. 结点的高度:从下往上数
  3. 树的高度(深度) :总共多少层
  4. 结点的度:有几个孩子(分支)
    非叶子节点的度>0
    叶子结点的度=0
  5. 树的度: 树中各结点的度的最大值
3.有序树,无序树
  1. 有序树:逻辑上看,树中节点的各子树从左至右是有次序的,不能互换
  2. 无序树:逻辑上看,树中节点的各子树从左至右是无次序的,可以互换
4.森林

森林是m (m20)棵互不相交的树的集合

3.树的性质

考点1

结点数=总度数+1

考点2
  1. 度为m的树
    任意结点的度≤m (最多m个孩子)
    至少有一个结点度=m
    一定是非空树

  2. m叉树
    任意结点的度≤m (最多m个孩子)
    允许所有结点的度都<m
    可以是空树

考点3

在这里插入图片描述

考点4

在这里插入图片描述

4.树的存储结构

双亲表示法

  1. 每个结点中保存指向双亲的"指针”
  2. 根节点存储在0, -1表示没有双亲
  3. 新增数据元素无需按逻辑上的次序存储
  4. 优点:查指定结点的双亲很方便
  5. 缺点:查指定结点的孩子只能从头遍历

孩子表示法

  1. 顺序+链式存储——指针指向第一个孩子
  2. 优点:找孩子方便
  3. 缺点:找父节点不方便

孩子兄弟表示法

  1. 用二叉链表存储树——左孩子右兄弟
  2. 孩子兄弟表示法存储的树,从存储视角来看形态上和=叉树类似
  3. 考点:树与二叉树的相互转换。本质就是用孩子兄弟表示法存储树

重要考点:树、森林与二叉树的转换

  1. 本质:用二叉链表存储森林——左孩子右兄弟
  2. 森林中各个树的根节点之间视为兄弟关系

5.树和森林的遍历

树的遍历
先根遍历——深度优先遍历
先根,后子树
树的先根遍历序列与这棵树相应二叉树的先序序列相同
后根遍历——深度优先遍历
先子树,后根
树的后根遍历序列与这棵树相应二叉树的中序序列相同
层序遍历(用队列实现)——广度优先遍历

森林的遍历
先序遍历

  1. 若森林为非空,则按如下规则进行遍历:
  2. 访问森林中第一棵树的根结点。
  3. 先序遍历第一棵树中根结点的子树森林。
  4. 先序遍历除去第一棵树之后剩余的树构成的森林。
  5. 效果等同于依次对各个树进行根遍历

中序遍历

  1. 若森林为非空,则按如下规则进行遍历:
  2. 中序遍历森林中第一棵树的根结点的子树森林。
  3. 访问第一-棵树的根结点。
  4. 中序遍历除去第一-棵树之 后剩余的树构成的森林。
  5. 效果等同于依次对各个树进行根遍历
森林二叉树
先根遍历先序遍历先序遍历
后根遍历中序遍历中序遍历

http://www.ppmy.cn/embedded/27604.html

相关文章

RabbitMQ是如何保证消息不被重复消费,或者说是如何保证消息消费时的幂等性的

目录 面试官:RabbitMQ是如何保证消息不被重复消费?或者说是如何保证消息消费时的幂等性的1. 使用唯一业务标识2. 使用RabbitMQ的消息去重插件3. 使用业务逻辑实现幂等性4. 使用消息属性和死信队列5. 使用Spring Boot的重试机制该文章专注于面试,面试只要回答关键点即可,不需…

<网络> 通信函数listen的第二个参数

目录 前言&#xff1a; 一、实验 二、listen 函数的第二个参数 &#xff08;一&#xff09;未完成连接队列和全连接队列 &#xff08;二&#xff09;为什么 TCP 中要维护连接队列&#xff1f; &#xff08;三&#xff09;为什么连接队列的长度不能太长&#xff1f; &…

web3以太坊开发,前后端交互中涉及到的合约

在web3以太坊开发中&#xff0c;往往大家交流的时候&#xff0c;会涉及到一些合约相关的词汇&#xff0c;这里重点说两个合约&#xff0c;一个是manager合约&#xff0c;另一个是registry合约。 目录 1 Manager合约 2 Registry合约 2.1 Registry合约可以做什么&#xff1f; …

deepflow grafana plugin 编译问题解决

修改tsconfig.js 增加"noImplicitAny": false&#xff0c;解决代码类型没有指定&#xff0c;显示Any 错误 To solve the error, explicitly set the parameters type to any, use a more specific type or set noImplicitAny to false in tsconfig.json. https://b…

基于SpringBoot的“大学生社团活动平台”的设计与实现(源码+数据库+文档+PPT)

基于SpringBoot的“大学生社团活动平台”的设计与实现&#xff08;源码数据库文档PPT) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBoot 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统结构图 管理员登录界面图 管理员功能界…

midjourney简单使用体验

自从我下了controlNet近20G的模型以后&#xff0c;我发现我本地的sd实在跑不动了。 为了能更好的试验一下作图&#xff0c;我只能转战mj。 mj相对于我们来说还算挺友好的&#xff0c;有个梯子就行&#xff0c;虽然需要付费&#xff0c;但是。。多的我也不多说了&#xff0c;懂…

webpack打包工具

目录 1. yarn包管理器 1.1 yarn 是什么, 有什么用? 1.2 yarn的使用 ​​​​​​2. webpack基本概述 2.1 webpack是什么&#xff1f; 2.2 什么是打包&#xff1f; 2.3 webpack能做什么&#xff1f; 3. webpack基本使用步骤 3.1 webpack基本使用步骤 3.2 package.jso…

Jmeter Beanshell 设置全局变量

//获取token import com.alibaba.fastjson.JSONObject; import com.alibaba.fastjson.JSONArray; import java.util.*; import org.apache.jmeter.util.JMeterUtils; //获取可上机机器 String response prev.getResponseDataAsString(); JSONObject responseObect JSONObjec…