专栏首页别先生数据结构之树-第一篇

数据结构之树-第一篇

1、二分搜索树,数据存储的方式是一种树结构。而线性数据结构,把所有的数据排成一排的。为什么需要树结构呢,因为树结构本身是一种天然的组织结构,使用树结构非常高效。将数据使用树结构存储后,效率是出奇的高效。

  二分搜索树(Binary Search Tree)具有一定的局限性,所以引入了平衡二叉树,平衡二叉树包含了AVL和红黑树等等。当算法需要一些特殊的操作的时候,将数据组织成树结构,会针对某一类特殊的操作,产生非常高效的结果,引入了堆和并查集,都是为了满足对数据的某一类特殊的操作,进行高效的处理。同时对于某些特殊的数据,很多时候,我们可以另辟蹊径,将他们以某种形式存储成树结构,结果就是会对这些特殊的数据,他们所在的那个领域的问题,相应的这种解决方案,提供极其高效的结果,引入了线段树和Trie(字典树、前缀树),其中线段树主要处理线段这种特殊的数据,而Trie主要用于处理字符串这种数据。

  二叉树,和链表一样,也是一种动态数据结构,换句话说,我们不需要在创建这个数据结构的时候就去决定好这个数据结构最多可以容纳多少元素,这样的问题。我们如果要添加元素,就new一个新的空间,把它添加到数据结构中,就好了,如果要删除元素,也是同理的。

二叉树节点Node的定义,如下所示:

 1 package com.tree;
 2 
 3 /**
 4  * 1、二叉树里面的每个元素也是存储在节点中。
 5  */
 6 public class Node<E> {
 7 
 8     private E e;//存储元素的e
 9     // 二叉树,两个指向其他节点的引用。
10     private Node left;//指向左边的引用。左孩子。
11     private Node right;//指向右边的引用。右孩子。
12 
13 }

2、二叉树的基本概念。

二叉树和链表一样,也具有天然的递归结构,在二叉树的操作中,更加强调递归结构。

二叉树中,一个节点也可以看作是二叉树,甚至一个NULL也可以看作是二叉树。类比链表中,只有一个节点,就是头部节点可以看作是链表,也可以把空本身看作是一个链表。 

3、 二分搜索树Binary Search Tree,首先,二分搜索树是一颗二叉树。

4、二分搜索树添加元素。首先,二分搜索树里面一个节点都没有,也就是说二分搜索树的root是空的话。

4.1、演示一个复杂的二分搜索树添加元素的过程。

此时,来了一个新的节点元素60,从根节点出发,60比41大,插入到根节点41的右子树,就变成了60和58作比较,60比58大,就应该插入到58的右子树去,此时58的右子树为空,所以60变成了58的右子树的根节点。

此时,来了一个新的节点元素28,从根节点出发,28比41小,插入到根节点41的左子树,就变成了28和41的左孩子22作比较,28比22大,就应该插入到22的右子树,就变成了28和22的右孩子33做比较,28比33小,就要和33的左孩子进行比较,此时,33没有左孩子,所以,28变成了33的左孩子。

此时,来了一个新的节点元素50,从根节点出发,50比根节点41大,插入到根节点41的右子树,此时,50和根节点41的右孩子58比较,50比根节点41的右孩子58小,就插入到58的左子树,此时50和根节点58的左孩子50进行比较,由于50和根节点58的左孩子(另外一个50节点)50相等,在这种情况下怎么办呢,在此代码实现中实现的二分搜索树,不做任何改变,相当于50已经存在于这个二分搜索树当中了。即此实现的二分搜索树不包含重复元素的。

在某些应用中,想包含重复的元素,也不难,只要改变他们的定义,比如说,让左子树的所有节点小于等于这个节点,或者右子树的所有节点大于等于这个节点。

5、二分搜索树的前序遍历,过程如下所示。看着可能有点乱,建议自己使用debug和画图的方式进行理解,代码逻辑看似简单,实则暗藏杀机。

6、如何快速的获取到二分搜索树的前序遍历,中序遍历,后序遍历的结果。

6.1、如何快速的获取到二分搜索树的前序遍历,中序遍历,后序遍历的结果。

7、二分搜索树前序遍历的非递归写法。栈这种数据结构,栈有一个非常重要的应用,就是在我们的系统中,做这种程序调用的时候,在进行子过程的调用的时候,可以把原来这个过程执行到了哪里,给压入系统栈中,方便在子过程调用结束之后,找回原来的那个位置。二分搜索树可以借助栈来记录之后我们要访问节点的顺序。

之后,由于访问了28这个元素,下面就要访问28的子树了,此时,将28元素的两个子树压入栈,压入栈的顺序是先压入右孩子,再压入左孩子,因为栈是后入先出的,所以要先压入后续要访问的节点。此时的栈顶元素16就是下一次要访问的节点,那么,栈顶元素16出栈,此时对16进行相应的操作。

此时,对16这个节点先压入右孩子,再压入左孩子,就是先压入22,再压入13。之后,要压入13的右孩子和左孩子,此时,13的左右孩子都是空,所以什么都不用压入了。此时继续看栈顶元素22。

此时对栈顶元素22进行相应的操作,对22进行相应的操作,此时22就访问完了,此时压入22的左右子树,由于22的左右子树都是空,所以什么操作都不用做,此时,继续看栈顶元素是谁,此时栈顶元素是30,此时让栈顶元素30出栈,对它进行相应的操作,此时对30这个节点访问完了,下面相应的将30这个节点的左右子树压入栈。

此时,将30这个元素的右子树42和左子树压29入栈,此时对栈顶元素29进行操作,将栈顶元素出栈,对它进行相应的操作,此时29这个节点就访问完了,之后压入29的左右子树,由于29的左右子树都是空,所以什么都不做。

此时,将栈顶元素42拿出来,进行相应的操作,此时29这个节点就访问完了,之后压入42的左右子树,由于42的左右子树都是空,所以什么都不做。此时,再拿出栈顶元素,但是此时的栈已经空了,说明栈已经没有再记录要访问任何节点了,至此,我们的整棵二分搜索树的前序遍历就遍历完了。

8、层序遍历(又称为广度优先遍历),其实非常好理解,对于这个二分搜索树来说,每一个节点相应的就有一个深度的值,通常呢,把根节点的深度为0相应的这个节点。所谓的层序遍历,就是一层一层的,先遍历到第0层的节点,再遍历到第一层的节点,再遍历到第二层的节点,依次类推,这种遍历方式又称为广度优先遍历。可以理解为逐层向下遍历的节点,在广度上进行拓展,而不像之前遍历方式,顺着一个枝杈向最深地方走。

之后,将根节点28的左右两个孩子分别入队,此时分别将左孩子16和右孩子30入队。因为对于队列来说,是先到先得,或者先进先出,所以我们按照从左到右的顺序进行入队。

由于篇幅限制,接下一篇。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构之红黑树

      红黑树和红色和黑色这两种颜色有关,事实上,在红黑树中,对每一个节点都附着一个颜色,或者是红色或者是黑色。红黑树首先是一棵二分搜索树,这一点和AVL树是一样的...

    别先生
  • 数据结构之树-第二篇

    1、此时,将元素30从队首拿出来,进行访问,之后将30的左孩子29、右孩子42入队,那么此时队首元素就是13了。

    别先生
  • 力扣LeetCode,移除链表元素

    首先,结合给定的条件,此类ListNode就是一个实现了一个节点,节点包含存储元素的val变量和指向下一个节点的Node类型的next,然后创建了一个ListN...

    别先生
  • 消息队列实现复制的最佳实践

    把消息复制到多个节点,不仅可解决丢消息问题,还可保证消息服务的HA。所以都会把MQ配置集群模式,并开启消息复制保证系统。

    黄泽杰
  • 基于关系型数据库的App Inventor网络应用(3)

    第三节 初识Node-RED 开发环境简介 如图8所示,整个浏览器窗口被划分为四个部分: (1) 顶部黑色通栏,左侧显示Node-RED的LOGO,右侧显著位置...

    企鹅号小编
  • 带着问题学习分布式系统之中心化复制集

    假若我说有三个节点(计算机)要维护同一分数据,如果你对分布式系统并不了解,那么你可能会有什么问题呢,我想可能有两个最基本的问题:   为什么同一份数据要保存多...

    用户1263954
  • redis 主从复制

    在分布式系统中,为了解决单点问题,通常会把数据复制多个副本部署到其他节点,以便满足故障恢复和负载均衡等需求。redis也是如此,它为我们提供了复制功能,实现了相...

    小手冰凉
  • 【学习】K近邻算法基础:KD树的操作

    Kd-树概念 Kd-树其实是K-dimension tree的缩写,是对数据点在k维空间中划分的一种数据结构。其实,Kd-树是一种平衡二叉树。 举一示例: 假设...

    小莹莹
  • Redis主从复制

    上一篇讲到了Redis的持久化机制,有RDB快照持久化以及AOF日志持久化。Redis的持久化机制保证了Redis即使服务重启,也可以将硬盘中已经持久化的数据进...

    创译科技
  • 多叉树 & B树 & B+树 & B*树

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

    贪挽懒月

扫码关注云+社区

领取腾讯云代金券