专栏首页大猫的Java笔记聊聊树与二叉树

聊聊树与二叉树

1.什么是树

现实生活中的树就是有一个主干,加分支加叶子组成的一种植物,大概如下图所示

数据结构中的树是什么样子呢?他就像是一个倒着生长的树,对照着两幅图看,是不是很相似。其中圆圈的位置就是数据存放的地方。

每个元素我们叫作“节点”,也就是图中的每个圈;用来连线相邻节点之间的关系,我们叫作“父子关系,A 节点就是 B 节点的父节点,B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点,所以它们之间互称为兄弟节点。我们把没有父节点的节点叫作根节点,也就是图中的节点 E。我们把没有子节点的节点叫作叶子节点或者叶节点,比如图中的 G、H、I、J、K、L 都是叶子节点。

还有三个比较相似的概念:高度(Height)、深度(Depth)、层(Level)。它们的定义是这样的

实际上节点的高度就是该节点到最下面,也就是叶子节点的最长路径,高度就比较好理解了一般我们看一个东西有好高都是从小面开始向上计算的,而深度就是从上向下计算,例如水有多深,最上面的肯定就是水面,所以深度是0,而层和深度类似,是树的深度加1,我们可以这样理解,一般一栋楼房的层数在都是从下面开始计算的,所以我们可理解成从顶层开始计算的一种楼房。

2.二叉树

二叉树我们从名字上就可以看出来他每一个分叉只能有两个子节点(也就是一个父节点最多只能有两个子节点),分别是左节点和右节点。

满二叉树

所谓的满二叉树就是所有的叶子节点都在同一层,类似于上图中的图2,我们也可以为根据根节点左右能够对称的树叫满二叉树。

完全二叉树

完全二叉树相比满二叉树比较难理解,根据《大话数据结构》书中的解释,我觉得比较还是比较好理解,我们如果从根节点开始,从左到右定义一个顺序的编号,而如果节点是根据顺序走的那么就是完全二叉树,否则就不是;从下面图一种可以看出节点是完全根据顺序编号走的,而图二在第三层的时候右边两个没有节点,所以不是根据顺序走的,图三则是第四层第一个节点没有也不是根据顺序走的,图四第三层按照顺序编号第三个节点应该有数据而没有,所以也不是根据顺序编号走的。

3.二叉树的存储方式

二叉树的存储方式分为链式和顺序存储两种,我们可以根据数组来存储,也可以根据链表来存储,实际中链表存储居多,基本上很少有使用数组来存储的,链式存储我们可以定义两个指针,分别指向左右子节点的地址。

而数组存储就比较麻烦了,我们可以定义一个数组而数组中存放当前节点的数据,同时存放自己左右子节点的下标位置,当然这肯定不是一个简单的基本类型数组,而是一个类的数组,而这个类中存在着这三个变量,左右子节点的下标,以及自己的数据,当然这个时候你可能会说这样子是不是不太好找到自己的父节点了,那我们可以再加一个存放父节点下标位置的变量,根节点的父节点我们可以存储0。

4.二叉树的遍历

二叉树的遍历可以分为三种,分别为前序遍历、中序遍历、后续遍历实际上这三个只是把输出数据的代码放在了不同的位置。前序遍历就是将输出节点的代码放在左右子树之前,而中序遍历就是放在左子树递归后面,右子树递归前面,也就是放在他俩中间,而后续遍历就是输出语句放在左右子树递归之后。

最后看看遍历的时间复杂度,从我前面画的前、中、后序遍历的顺序图,可以看出来,每个节点最多会被访问两次,所以遍历操作的时间复杂度,跟节点的个数 n 成正比,也就是说二叉树遍历的时间复杂度是 O(n)。

本文分享自微信公众号 - 大猫的Java笔记(damaoJava),作者:大猫

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 肝了几天我算是理解了红黑树

    在学习红黑树之前我们需要了解一下二叉排序树,所谓二叉排序树就是一种特殊的二叉树,首先满足二叉树的性质,然后它存储数据的方式是左边节点比父节点的数据小,而右边节点...

    大猫的Java笔记
  • 堆和堆排序

    1.必须是一棵完全二叉树,完全二叉树指树的元素在新增时满足从上到下,从左到右的新增顺序。

    大猫的Java笔记
  • CountDownLatch源码分析

    CountDownLatch源码分析之前,首先看一看CountDownLatch的用法,我们通过一段代码来说明CountDownLatch的基本用法,代码如下。

    大猫的Java笔记
  • 红黑树(Red-Black Tree)

    红黑树,本质上来说就是一棵二叉查找树,但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡,从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(...

    None_Ling
  • 《Redis设计与实现》读书笔记(二十八) ——Redis集群节点结构与槽分配

    《Redis设计与实现》读书笔记(二十八) ——Redis集群节点结构与槽分配 (原创内容,转载请注明来源,谢谢) 一、概述 redis集群是...

    用户1327360
  • 数据结构:树与二叉树

    一颗高度为h,并含有2^h-1个节点的二叉树称为满二叉树,即树中的每一层都含有最多的节点。

    HLee
  • 红黑树算法

    前情提要 红黑树是AVL树里最流行的变种,有些资料甚至说自从红黑树出来以后,AVL树就被放到博物馆里了。红黑树是否真的有那么优秀,我们一看究竟。红黑树遵循以下...

    机器学习算法工程师
  • 多叉树 & B树 & B+树 & B*树

    二叉树虽然操作效率比较高,但是如果数据一多,就会有好多好多的节点,需要进行好多次的I/O操作,构建出来的二叉树就会很高很高,也会降低操作速度。

    贪挽懒月
  • 像管理 Pod 一样管理 Node | TKE 节点池全面上线

    晏子怡,腾讯云产品经理,目前负责TKE集群、网络及调度模块。 从 K8s 的声明式设计理念谈起 Pod 模板 K8s 最优雅精妙的一个设计理念在于声明式  A...

    腾讯云原生
  • 红黑树深入剖析及Java实现

    红黑树是平衡二叉查找树的一种。为了深入理解红黑树,我们需要从二叉查找树开始讲起。 BST 二叉查找树(Binary Search Tree,简称BST)是一棵二...

    美团技术团队

扫码关注云+社区

领取腾讯云代金券