理解树的结构-算法通关村

理解树的结构-算法通关村


1.树的结构

  • 树是一个有n个有限节点组成一个具有层次关系的集合,每个节点有0个或者多个子节点,没有父节点的节点称为根节点,也就是说除了根节点以外每个节点都有父节点,并且有且只有一个。树的种类比较多,最常见的是二又树,基本结构如下:
  • 参考上面的结构,可以很方便的理解树的如下概念:
    1. 节点的度:一个节点含有的子节点的个数称为该节点的度;
    2. 树的度:一棵树中,最大的节点的度称为树的度,注意与节点度的区别;
    3. 叶节点或终端节点:度为0的节点称为叶节点;
    4. 非终端节点或分支节点:度不为0的节点;
    5. 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;
    6. 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
    7. 兄弟节点:具有相同父节点的节点互称为兄弟节点;
    8. 节点的祖先:从根到该节点所经分支上的所有节点;
    9. 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
    10. 森林:由m(m>=0)棵互不相交的树的集合称为森林;
    11. 无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树;
    12. 有序树:树中任意节点的子节点之间有顺序关系,这种树称为有序树;
    13. 二叉树:每个节点最多含有两个子树的树称为二叉树;

2 树的性质

  • 性质1:在二叉树的第i层上至多有2^(i-1)个结点(i>0)
    性质2:深度为k的二叉树至多有2^k -1个结点(k>0)
    性质3:对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;
    性质4:具有n个结点的完全二叉树的深度必为 log2(n+1)
    性质5:对完全二叉树,若从上至下、从左至右编号,则编号为i的结点,其左孩子编号必为2i,其右孩子编号必为2i+1;其双亲的编号必为i/2(i=1 时为根,除外)
  • 满二叉树就是如果一棵二叉树只有度为0的节点和度为2的节点,并且度为0的节点在同一层上,则这棵二叉树为满二叉树。
  • 这棵二又树为满二叉树,也可以说深度为k=4,有2^k-1=15个节点的二又树。完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大 值,并且最下面一层的节点都集中在该层最左边的若干位置。

3 树的定义

  • 定义二叉树

  •   public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
      }
    
  • 定义N叉树

  •   public class Node {
          public int val;
          public List<Node> children;
      }
    

4树的遍历方式

  • 二叉树的遍历方式有层次遍历和深度优先遍历两种:
    • 深度优先遍历:先往深走,遇到叶子节点再往回走。
    •广度优先遍历:一层一层的去遍历,一层访问完再访问下一层。
    这两种遍历方式不仅仅是二叉树,N树叉也有这两种方式的,图结构也有,只不过我们更习惯叫广度优先和深度优先,本质是一回事。
    深度优先又有前中后序三种,记住一点:前指的是中间的父节点在遍历中的顺序,只要大家记住前中后序指的就是父节点在访问中的顺序就可以了。
    前序遍历:中左右 中序遍历:左中右 后序遍历:左右中

5 通过序列构造二叉树

  • 前面我们已经介绍了前中后序遍历的基本过程,现在我们看一下如何通过给出的序列来恢复原始二叉树,看三个序列:
    (1)前序:1 2 3 4 5 6 8 7 9 10 11 12 13 15 14
    (2)中序:3 4 8 6 7 5 2 1 10 9 11 15 13 14 12
    (3) 后序:8 7 6 5 4 3 2 10 15 14 13 12 11 9 1

5.1前中序列复原二叉树

  • 先看如何通过前中序列复原二叉树:

  • (1)前序:1 2 3 4 5 6 8 7 9 10 11 12 13 15 14
    (2)中序:3 4 8 6 7 5 2 1 10 9 11 15 13 14 12

  • 第一轮
  • 我们知道前序第一个访问的就是根节点,所以根节点就是1
    中序遍历的特点是根节点的左子树的元素都在根节点的左侧,右子树的元素都在根节点的右侧,从中序遍历序列我们可以划分成如下结构:

  • 前序中序划分:
    中序序列划分:[3 4 8 6 7 5 2 ] 1 [10 9 11 15 13 14 12]
    前序序列划分:1 [2 3 4 5 6 8 7] [9 10 11 12 13 15 14]
  • 上面前序序列第一个括号里的都是左子树的元素,第二个括号一定都是右子树的元素。参照中序的两个数组划分的。我们看到前序中7之前的元素都在中序第一个数组中,9之后的所有元素就在第二个数组种,所以我们从7和9之间划分。
    由此,画图表示一下此时知道的树的结构为:

  • 第二轮
  • 我们先看两个序列的第一个数组:
    前序:2 3 4 5 6 8 7 中序:3 4 8 6 7 5 2
    此时又可以利用上面的结论划分了:根节点是2,然后根据2在中序中的位置可以划分为:

  • 序列
    前序: 2 [3 4 5 6 8 7]
    中序:[3 4 8 6 7 5 ] 2
  • 此时树的结构为:

  • 第三轮:
  • 对 3 4 5 6 8 7 继续划分 : 前序:3 [4 5 6 8 7] 中序:3 [ 4 8 6 7 5 ] 此时结构为:

  • 第四轮
  • 对 4 5 6 8 7 继续划分:前序: 4 [5 6 8 7 ] 中序:4 [8 6 7 5 ]

  • 第五轮:
  • 对 5 6 8 7 继续划分:前序:5 [6 8 7 ] 中序:[8 6 7] 5

  • 同理,对序列 [10 9 11 15 13 14 12],进行划分:


5.2 通过中序和后序序列恢复二叉树

  • 通过中序和后序也能恢复原始序列的,唯一的不同是后序序列的最后一个是根节点,中序的处理也是上面一样的过程:
    前序:12345687910 1112 1315 14
    中序: 3486752110911 15 13 14 12
    后序:876543210 15 14 13 12 1191
    可以自行试一试,不再赘述。
    问题:为什么前序和后序不能恢复二叉树
    既然上面两种都行,那为什么前序和后序不行呢?我们看上面的例子:
    (1) 前序: 123456879 10 1112 13 15 14
    (2) 后序:87654321015 141312 1191
    后序:876543210 15 14 13 12 1191
    可以自行试一试,不再赘述。
    问题:为什么前序和后序不能恢复二叉树
    既然上面两种都行,那为什么前序和后序不行呢?我们看上面的例子:
    (1) 前序: 123456879 10 1112 13 15 14
    (2) 后序:87654321015 141312 1191
  • 根据上面的说明,我们通过前序可以知道根节点是1,通过后序也能知道根节点是1,但是中间是怎么划分的呢?其他元素哪些属于左子树,哪些属于右子树呢?很明显通过两个序列都不知道,所以前序和后序序列不能恢复二叉树。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/474959.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

如何自定义异常类

如何自定义异常类 为什么要使用自定义异常类&#xff1f; 在 Java 中&#xff0c;自定义异常是指用户根据自己的需求创建的异常类。Java 提供了一些预定义的异常类&#xff0c;如 NullPointerException、ArrayIndexOutOfBoundsException 等&#xff0c;但有时这些预定义的异常…

直播预告!5位大厂测开学长学姐助力你上岸测开

大家好&#xff0c;我是洋子&#xff0c;24届春招补录&25届暑期实习招聘已经进入到白热化阶段&#xff0c;近期收到了很多同学关于求职问题的咨询&#xff0c;所以开一场公益直播来为大家答疑解惑 主题&#xff1a;校招测试开发求职如何准备&职业发展 时间&#xff1…

十二、MySQL 主从复制+高可用+读写分离

目录 一、mysqlkeeplived实现高可用LVS负载均衡 一、什么是高可用 二、为什么要用高可用 三、高可用的作用 四、keeplived 是什么&#xff1f;它用在哪里 五、安装mysql以及配置主从 六、keepalived安装 1、配置 单VIP 实现高可用 master上配置 2、backup上的配置 3、…

蓝桥杯-礼物-二分查找

题目 思路 --刚开始想到暴力尝试的方法&#xff0c;但是N太大了&#xff0c;第一个测试点都超时。题目中说前k个石头的和还有后k个石头的和要小于s&#xff0c;在这里要能想到开一个数组来求前n个石头的总重&#xff0c;然后求前k个的直接将sum[i]-sum[i-k-1]就行了&#xff0…

@EnableConfigurationProperties注解使用

前言 当我们想把配置的内容,动态赋值到某个配置类上的时候,可以使用EnableConfigurationProperties ConfigurationProperties注解 代码准备 创建配置文件prop.properties nameada age18 email123qq.com 创建配置类 ComponentScan("com.test.pops") PropertySo…

天地一体化5G网络中LNA的辐射效应

Youssouf A S, Habaebi M H, Hasbullah N F. The radiation effect on low noise amplifier implemented in the space-aerial–terrestrial integrated 5G networks[J]. IEEE Access, 2021, 9: 46641-46651. 图2 面向卫星的5G综合网络架构方案 这篇论文《The Radiation Effect…

docker快速安装达梦数据库

docker快速安装达梦数据库 文章目录 docker快速安装达梦数据库前言环境准备下载镜像运行、配置容器 前言 因为公司需要将自己的底代码平台与客户的需求做适配&#xff0c;客户要求必须满足信创要求&#xff0c;使用达梦数据库。所以需要将原有的MySQL数据库与达梦数据库适配&a…

Android:adb命令

执行adb命令的窗口如下 Mac或Linux系统里的终端窗口&#xff1b; window系统运行输入cmd打开的指令窗口&#xff1b; Android Studio 里控制下面的Terminal窗口 1. 查看已链接的设备和模拟器 adb devices -l 2. 查看Android内核版本号 adb shell getprop ro.build.version.re…

面试笔记——Redis(集群方案:主从复制、哨兵模式和分片集群)

主从复制 在 Redis 主从集群中&#xff0c;一个主节点&#xff08;Master&#xff09;负责处理客户端的读写请求&#xff0c;而多个从节点&#xff08;Slave&#xff09;则负责复制主节点的数据&#xff0c;并对外提供读取服务——解决高并发问题。 主节点&#xff08;Master&…

vue@2.7.16 使用less、less-loader

遇到问题&#xff0c;npm install less-loader7.3.0 --save安装好less-loader后&#xff0c;执行npm run serve 项目运行不起来&#xff0c;排查后发现在安装less-loader后就提示需要安装less&#xff0c;正确的安装应如下&#xff1a; npm install less less-loader7.3.0 --sa…

了解电子元器件商城价格变动的背后逻辑

电子元器件商城价格的变动背后存在着多种逻辑和因素&#xff0c;这些因素相互交织、相互作用&#xff0c;共同影响着价格的波动。以下是一些可能存在的背后逻辑&#xff1a; 供需关系&#xff1a; 供应量变化&#xff1a;电子元器件市场的供应量受到供应商生产能力、原材料供应…

linux内核input子系统概述

目录 一、input子系统二、关键数据结构和api2.1 数据结构2.1.1 input_dev2.1.2 input_handler2.1.3 input_event2.1.4 input_handle 2.2 api接口2.2.1 input_device 相关接口input_device 注册流程事件上报 2.2.2 input handle 相关接口注册 handle指定 handle 2.2.3 input han…

[隐私计算实训营学习笔记] 第1讲 数据要素流通

信任四基石 数据的分级分类 技术信任&#xff1a;全链路审计、闭环完成的数据可信流通体系 技术信任&#xff1a;开启数据密态时代 数据可流通的基础设施&#xff1a;密态天空计算

第3章 数据治理

思维导图 数据治理的定义&#xff1a;是在管理数据资产过程中行使权力和管控&#xff0c;包括计划、监控、和实施。 职能&#xff1a;指导所有其他数据管理领域的活动。目的&#xff1a;确保根据数据管理制度和最佳实践正确地管理数据。整体驱动力&#xff1a;确保组织可以从其…

sd卡数据不小心删除了如何恢复,sd卡中的数据不小心被删除了如何进行恢复

在现代科技快速发展的时代,SD卡已经成为我们存储和传输数据的重要工具之一。当您不小心删除了SD卡中的数据时,这种意外情况可能引起您的困惑和焦虑。那些重要的文件、无价的回忆似乎在转瞬间消失得无影无踪。面对这种突发的数据丢失问题,我深感理解。sd卡数据不小心删除了如…

Mac上轻松几步搞定Docker与Redis安装:从下载安装到容器运行实测全程指南

1、去官网下载docker 安装&#xff1a;把图标拉到应用程序即可把图标拉到应用程序即可 https://docs.docker.com/desktop/install/mac-install/ 2、docker拉取redis镜像 拉取命令&#xff0c;后面填上版本号3.2.1&#xff0c;可以看到已经成功了。 docker pull redis:3.2.1…

Guitar Pro8吉他学习 、打谱 、 创作神器,让你的吉他之路更上一层楼!

Guitar Pro8吉他学习 、打谱 、 创作神器&#xff0c;让你的吉他之路更上一层楼&#xff01;轻松学习吉他&#xff0c;实现音乐梦想&#xff0c;Guitar Pro8助你一臂之力&#xff01; Guitar Pro 2024 win-安装包下载如下&#xff1a; https://wm.makeding.com/iclk/?zoneid5…

u盘数据删除或者移除了怎么办?冷静,恢复指南来帮你

在数字化时代&#xff0c;U盘已成为我们存储和传输数据的重要设备。然而&#xff0c;有时由于疏忽或误操作&#xff0c;我们可能会不小心删除或移除了U盘上的重要数据。面对这种情况&#xff0c;许多人可能会感到焦虑和困惑&#xff0c;不知道如何是好。本文将为您提供一些建议…

【Unity】宏定义Scripting Define Symbols

1.宏的用处 我们在使用Unity开发的时候&#xff0c;经常需要根据不同环境执行不同的代码 比如安卓手机和苹果手机获取路径代码 这个时候&#xff0c;宏就派上用场了。 代码示例&#xff1a; //获取路径public string GtePath(){//不同平台&#xff0c;取不同的存储路径string…