精华内容
下载资源
问答
  • 本篇文章将开始讲解树结构。其实树结构是平日里我们常见的一种数据结构,例如家族族谱、公司管理层级结构图等,这样的数据结构的存在一定有一定的道理。因此,在计算机领域中,树结构也是会被广泛用到的,例如数据库...

    本系列文章【数据结构与算法】所有完整代码已上传 github,想要完整代码的小伙伴可以直接去那获取,可以的话欢迎点个Star哦~下面放上跳转链接

    本篇文章将开始讲解树结构。其实树结构是平日里我们常见的一种数据结构,例如家族族谱公司管理层级结构图等,这样的数据结构的存在一定有一定的道理。

    • 家族族谱图

    在这里插入图片描述

    • 公司管理层级结构图

    在这里插入图片描述

    因此,在计算机领域中,树结构也是会被广泛用到的,例如数据库系统中就有用到。那么本文就从零开始学习一下树结构,并且也会封装一个二叉查找树,本文 3万+ 的详细教程,希望大家耐心观看,我是以一个纯小白的角度来写的这篇文章,相信大家认真看一定都能看懂的

    • 公众号:前端印象
    • 不定时有送书活动,记得关注~
    • 关注后回复对应文字领取:【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】

    在这里插入图片描述

    一、什么是树

    树在我们平日应该算是一个低头不见抬头见的东西了。这里我特地找了个比较好看的树放在这里,大家可以观察一下树的特点,如图

    在这里插入图片描述
    第一反应是不是从树根开始往上生长,分出了特别的多分叉?没错,咱们要学习的树结构就是参照着真正的树衍生过来的,只不过是一个倒着的抽象的树,如图
    在这里插入图片描述
    我们把图中第一层的圆圈看成是树根,以下的几层都是由树根延伸出去的分支,这里的每一个圆圈都可以用于存储我们的数据。

    是一种非线性数据结构,它是由一个或多个结点组成的

    二、树结构的优点

    总的来说,树结构是结合了之前我们讲过的数组、链表、哈希表等结构的优缺点,但也不能说哈希表是最好的数据结构,毕竟每种数据结构都有各自突出的优点

    树结构的优点:

    1. 空间利用率比较高
    2. 可以非常快速地查找到最大值和最小值

    三、树结构的术语

    因为本文是从零开始学习树结构,所以我们在这里有必要讲解一下,在我们封装各种树结构的过程中涉及到的术语,方便大家理解。

    术语名 含义
    结点 树中的数据元素
    结点的度 结点拥有的子树个数
    叶子结点 度为0的结点
    分支结点 度大于0的结点
    父节点 衍生出其它结点的结点为这些结点的父结点
    子结点 被某个结点衍生出来的结点为该结点的子结点
    兄弟结点 具有同一个父节点的所有结点为兄弟结点
    结点的层次 设定根结点所在层次为1,其它结点层次为其父节点层次+1
    树的深度 树的所有结点中的最大层次为该树的深度
    路径 从某个结点沿着树的层级关系到达另一个结点之间的路线
    路径长度 路径上的结点个数 -1

    我们来用图讲解一下每个术语的含义
    在这里插入图片描述
    如图,每一个圆圈就是一个结点结点A 延伸出去三个结点,因此 结点A 的度为 3结点B 延伸出去两个结点,因此 结点B 的度为 2结点C 并没有延伸出去的结点,故 结点C 的度为 0

    图中像 结点C 一样的度为 0 的结点还有 结点D结点E结点F,它们都称为叶子结点 ; 那么相对的,结点A结点B 的度都不为 0,它们就称为分支结点

    对于 父结点 、子结点 、兄弟结点,我们把图中的树结构看成族谱就很好理解了,假设 结点B爸妈,其延伸出去两个结点 结点E结点F,那么就是 B 生了 EF,所以 结点B 就是 结点E结点F父结点结点E结点F 就是 结点B子结点结点E结点F 互为兄弟结点

    树结构我们可以进行层次分级,例如统一规定根结点所在层次为 1,接着往下层级逐渐 +1。如图,结点A 所在的层次为 1;那么它的下一层层级就为 2,也就是 结点B结点C结点D 所在的层次为 2 ;再往下一层,结点E结点F 所在的层次为 3,这就是结点的层次。因为该树结构的最大层次为 3,所以该树的深度就为 3

    对于路径,假设我们要找到 结点A结点E 的路径,我们只需要沿着树的层次结构走就可以了,如图红线所标的路线就称为 结点A结点E路径
    在这里插入图片描述
    那么路径的长度为多少呢?因为该路径上经过了 3 个结点,因此,该路径的长度2

    四、什么是二叉树

    在树结构中,我们用到的最多的就是二叉树,因此它也是我们重点学习的对象,并且本文最后是要进行二叉查找树的代码封装,那么我们还是要先来了解一下二叉树的定义

    二叉树的定义: 树结构中每个结点最多只有两个子结点,即任何一个结点的度都小于等于 2

    我自己画了几个图来给大家举例哪些是二叉树,哪些不是

    首先说明,二叉树可以为空,也就是结点个数可以等于 0,此时称之为空二叉树


    在这里插入图片描述
    该树结构只有一个根节点,符合二叉树的定义,因此这一个非空二叉树


    在这里插入图片描述
    该树结构不是二叉树,因为 结点A 有三个子结点,不符合二叉树的定义


    在这里插入图片描述
    该树结构一个非空二叉树


    正是因为二叉树只有两个子结点,因此我们可以简单得把位于左侧和位于右侧的两个子结点分别称作其父节点的 左子结点右子结点

    讲到这里,我再补充个概念,叫做 左子树右子树 。因为我们整个二叉树就像是一棵树嘛,那么当我们以某个结点当作根结点,我们可以把其左边的所有结点组成的结构看成是一颗小一点的树,称之为 左子树 ;同理,其右侧所有结点组成的结构称之为 右子树 。如图

    在这里插入图片描述


    其实在二叉树中,又有两种特殊的二叉树,即 完美二叉树完全二叉树,接下来我们来简单讲解一下这两种类型的二叉树的概念

    五、完美二叉树

    完美二叉树 又叫 满二叉树,顾名思义,就是在一个二叉树中,除了最后一个层级的叶子节点外,其余每个结点都有两个子结点

    如图就是一个满二叉树
    在这里插入图片描述


    再来看一个不是满二叉树的例子,如图
    在这里插入图片描述
    该二叉树就不是一个满二叉树,因为处于倒数第二层的 结点C 只有一个子结点,不满足满二叉树的定义

    六、完全二叉树

    完全二叉树要满足以下两个条件:

    1. 除了最后一层外,其它各层的结点个数都达到最大个数
    2. 最后一层的结点集中在左侧,且结点连续,只有右侧部分可以缺失结点

    光看定义难以理解,我们来用实例了解完全二叉树
    在这里插入图片描述
    不是一个完全二叉树。其满足了完全二叉树的第一个条件,第一层最大结点个数应为 1,它有 1 个结点 ;第二层最大结点个数应为 2,它有 2 个结点 ;第三层最大结点个数应为 4,它有 4 个结点。

    但其不满足完全二叉树的第二个条件,因为最后一层的 结点H结点I结点J 没有连续集中在左侧。


    那么如何才算是连续集中在左侧呢?只需要在此图中给 结点D 添加一个右子结点即可使最后一层的结点连续集中在左侧,如图
    在这里插入图片描述
    这就一个正确的完全二叉树


    再来看一个例子,如图
    在这里插入图片描述
    这就不是一个完全二叉树了,虽然最后一层的结点连续集中在一起,但是它们集中在最后一层的右侧,这并不满足完全二叉树的定义


    其实 满二叉树 是一种特殊的 完全二叉树,不信你可以自己举个简单的例子验证一下

    七、二叉树的特性

    二叉树作为树结构中一种特殊的类型,它是有一些自己的特性的,我们来看一下

    (1)特性一

    一个二叉树第 i 层的最大结点个数为 2i1(i>=1)2^{i-1}(i>=1)

    在二叉树中,结点个数最多的情况就是满二叉树,即除了最后一层的叶子结点外,其余结点都有两个子结点,因此满二叉树每一层的结点个数都达到了最大值,其余类型的二叉树每一层结点个数只会小于或等于它

    我们可以自己来验证一下,下图时一个树的深度为 3 的满二叉树
    在这里插入图片描述
    第一层结点个数最多只有 20=12^0 = 1 个,图中有一个结点
    第二层结点个数最多只有 21=22^1 = 2 个,图中有两个结点
    第三层结点个数最多只有 22=42^2 = 4 个,图中有四个结点

    (2)特性二

    深度为 k 的二叉树拥有的最大结点数为 2k1(k>=1)2^k-1(k>=1)

    同样的,满二叉树是二叉树中结点个数最多的,因此其结点个数公式就为 2k1(k>=1)2^k-1(k>=1)

    我们可以验证一下

    在这里插入图片描述
    这是一个深度为 1 的满二叉树,最大结点个数为 201=12^0-1 = 1


    在这里插入图片描述
    这是一个深度为 2 的满二叉树,最大结点个数为 221=32^2-1 = 3


    在这里插入图片描述
    这是一个深度为 3 的满二叉树,最大结点个数为 231=72^3-1 = 7

    (3)特性三

    在非空二叉树中,n0n_0 表示叶子结点个数,n1n_1 表示分支结点个数,那么它们满足的关系有 n0=n1+1n_0=n_1 + 1

    该特性也是一个总结出来的规律,大家了解一下即可,可以自行验证一下

    八、二叉树的存储

    在使用二叉树存储数据时,我们有两种选择,一种是数组存储,另一种是链表存储

    (1)数组存储

    当使用数组存储时,如图
    在这里插入图片描述

    在按照从上到下,从左到右的顺序给二叉树标上下标以后,我们发现在使用数组存储二叉树的数据时,很难或者说几乎无法分辨结点之间的结点关系

    因此,有一种解决办法就是将二叉树补全成一个满二叉树,然后下标仍是按照从上到下,从左到右的顺序给的,如图
    在这里插入图片描述
    此时,我们就可以看到,各个结点之间就可以分辨得出来了,即父节点的下标值 index * 2 + 1,就等于其左子结点的下标值 ;同样的,父节点的下标值 index * 2 + 2,就等于其右子结点的下标值

    虽然现在结点间的关系可以辨别得出来了,但是有没有发现,这造成了很大的空间浪费,整个数组长度为 15,空着的位置就有 8

    所以我个人认为,用数组来存储二叉树的数据不太合适

    (2)链表存储

    链表存储也是二叉树最常用的一种存储方法。我们可以通过给每个结点封装一个对象,通过 leftright 分别指向其左子结点和右子结点

    来看一下,用链表存储的二叉树的样子,如图
    在这里插入图片描述
    我们只需要调用某结点的 leftright 就可以找到其子结点,这样做既避免了空间的浪费,又能把结点关系理得特别清楚

    九、什么是二叉查找树

    二叉查找树,英文名为 Binary Search Tree,简称BST,又名二叉排序树、二叉搜索树。

    二叉查找树本身就是一棵二叉树,它可以是一棵空树

    当二叉查找树不为空时,必须满足以下三个条件

    1. 非空左子树的结点的 key 小于其根结点的 key
    2. 非空右子树的结点的 key 大于其根结点的 key
    3. 左子树和右子树本身也是个二叉查找树

    我们可以先一个例子来体会一下这三个条件,如图

    在这里插入图片描述
    首先根结点的 key50 ,其左子结点为 10 小于 50,符合第一个条件 ;其右子结点为 70 大于 50,符合第二个条件

    再来看 结点10,其左子结点为 8 小于 10,符合第一个条件 ;其右子结点为 13 大于 10,符合第二个条件

    同理,结点70 也是符合的,因此就符合了第三个条件


    总结一下呢,就是以下几条结论:

    1. 左边的结点永远比根结点以及右边的结点小
    2. 右边的结点永远比根结点已经左边的结点大

    所以,接下来我们再来看几个例子,判断一下哪些时二叉查找树,哪些不是

    在这里插入图片描述
    这不是一个二叉查找树,因为 结点7 在右侧,比其根结点 8 要小,所以不符合条件。正确的位置应该是处于 结点8 的左子树位置


    在这里插入图片描述
    这是一个二叉查找树

    十、树的遍历

    以上给出的树结构的图都是我们布局好的非常美观的样子,但在程序里,树结构是非常抽象的,因此我们可以通过遍历全部结点的方式,将整个树结构展现出来

    树的遍历一共分成三种,分别是 先序遍历中序遍历后序遍历

    (1)先序遍历

    先序遍历: 访问根结点 => 访问左子树 => 访问右子树。在访问左子树或右子树的时候,仍是按照这个规则继续访问。

    我们来看一个简单的例子,如图,对其进行先序遍历

    在这里插入图片描述


    第一步: 先访问根结点 50 ,再访问左子树,最后访问右子树,如图
    在这里插入图片描述

    此时我们记录一下访问的过程,即 50 左子树10 右子树70


    第二步: 左子树10 也需要按照先序遍历的步骤进行,所以先访问 左子树10 中的根节点 10,再遍历其左子树,最后遍历其右子树,如图
    在这里插入图片描述

    因为 结点10 的左右子树都属于叶子结点了,即没有任何的子结点了,所需就无需对其进行遍历了

    我们接着第一步中的结果进行记录,即 50 10 8 13 右子树70


    第三步: 最后还剩个 右子树70 没有遍历了,那么同理,先访问其根结点 70,再遍历其左子树,最后遍历其右子树,如图
    在这里插入图片描述

    因为 结点70 的左右子树也都属于叶子结点了,所以也没有必要对其进行遍历了,直接获取该结点即可

    我们接着第二步的结果进行记录,即 50 10 8 13 70 60 80


    好了,到此位置,一个先序遍历的结果就出来了,我们来总结一下它的全部访问过程,如图
    在这里插入图片描述

    (2)中序遍历

    中序遍历: 访问左子树 => 访问根结点 => 访问右子树。在访问左子树或右子树的时候,仍是按照这个规则继续访问。

    我们来看一个简单的例子,如图,对其进行中序遍历

    在这里插入图片描述


    第一步: 先遍历 左子树10,再访问根结点 50,最后遍历右子树 70,如图

    在这里插入图片描述

    此时我们记录一下访问的过程,即 左子树10 50 右子树70


    第二步: 左子树10 也需要按照中序遍历的步骤进行,所以先遍历 左子树10 中的左子树,再访问其根节点 10,最后遍历其右子树,如图
    在这里插入图片描述

    因为 结点10 的左右子树都属于叶子结点了,即没有任何的子结点了,所需就无需对其进行遍历了

    我们接着第一步中的结果进行记录,即 8 10 13 50 右子树70


    第三步: 最后还剩个 右子树70 没有遍历了,那么同理,先遍历 右子树70 的左子树,再访问其根结点 70,最后遍历其右子树,如图
    在这里插入图片描述

    因为 结点70 的左右子树也都属于叶子结点了,所以也没有必要对其进行遍历了,直接获取该结点即可

    我们接着第二步的结果进行记录,即 8 10 13 50 60 70 80


    好了,到此位置,一个中序遍历的结果就出来了,我们来总结一下它的全部访问过程,如图

    在这里插入图片描述

    (3)后序遍历

    后序遍历: 访问左子树 => 访问右子树 => 访问根结点 。在访问左子树或右子树的时候,仍是按照这个规则继续访问。

    我们来看一个简单的例子,如图,对其进行后序遍历

    在这里插入图片描述


    第一步: 先遍历 左子树10,再遍历右子树 70,最后访问根结点 50,如图

    在这里插入图片描述

    此时我们记录一下访问的过程,即 左子树10 右子树70 50


    第二步: 左子树10 也需要按照后序遍历的步骤进行,所以先遍历 左子树10 中的左子树,再遍历其右子树,最后再访问其根节点 10,如图
    在这里插入图片描述

    因为 结点10 的左右子树都属于叶子结点了,即没有任何的子结点了,所需就无需对其进行遍历了

    我们接着第一步中的结果进行记录,即 8 13 10 右子树70 50


    第三步: 最后还剩个 右子树70 没有遍历了,那么同理,先遍历 右子树70 的左子树,再遍历其右子树,最后访问其根结点 70,如图
    在这里插入图片描述

    因为 结点70 的左右子树也都属于叶子结点了,所以也没有必要对其进行遍历了,直接获取该结点即可

    我们接着第二步的结果进行记录,即 8 13 10 60 80 70 50


    好了,到此位置,一个后序遍历的结果就出来了,我们来总结一下它的全部访问过程,如图
    在这里插入图片描述

    十一、二叉查找树的方法

    在封装二叉查找树之前,我们还是先来看一下二叉查找树常见的方法右哪些吧

    方法 作用
    insert() 向二叉查找树插入数据
    preOrder() 先序遍历二叉查找树,并返回结果
    inOrder() 中序遍历二叉查找树,并返回结果
    postOrder() 后序遍历二叉查找树,并返回结果
    getMax() 返回二叉查找树中的最大值
    getMin() 返回二叉查找树中的最小值
    search() 查找二叉查找树中的某个值
    remove() 移除某个值

    十二、用代码实现二叉查找树

    前提:

    1. 代码中会用到大量的递归思想,请还没了解过递归的小伙伴自行了解一下
    2. 部分方法会通过再封装一个内部函数来实现,请认真理解

    (1)创建一个构造函数

    首先创建一个大的构造函数,用于存放二叉查找树的一些属性和方法。

    function BinarySearchTree() {
        // 属性
        this.root = null
    }
    

    二叉查找树的属性最主要的就是 root ,用于指向树的根节点

    (2)创建结点构造函数

    因为我们准备通过链表来实现二叉查找树,所以我们需要先在内部封装一个结点的构造函数

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    }
    

    一个结点包括的内容有 左子结点右子结点,分别对应的 keyvalueleftright

    (3)实现insert()方法

    insert()方法就是将一个数据插入到二叉查找树中合适的位置。该方法接收两个参数,即 keyvalue

    实现思路:

    1. 调用内部结点构造函数,并把参数 keyvalue 传入,生成一个结点对象 node
    2. 判断二叉查找树是否右根结点,即判断是否为空,若为空,则直接将 node 作为二叉查找树的根结点,即将 node 赋值给 root 属性
    3. 若不为空,则遍历整个二叉查找树,用 node.key 与遍历到的结点的 key 值进行比对,最终找到合适的位置进行插入

    思路看着略微复杂,我做了动图方便大家理解,如图

    • 当二叉查找树为空时

    在这里插入图片描述

    • 当二叉查找树不为空时

    在这里插入图片描述
    这里我选择用递归的方式来遍历整个二叉查找树,因此我会再额外封装一个用于递归内部调用的函数 insertNode ,给其传入两个参数,第一个参数是当前遍历到的结点 ; 第二个参数是我们要插入的结点

    先来看下代码吧

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    
    	// 插入数据
        BinarySearchTree.prototype.insert = function(key, value = null) {
            // 1. 创建结点
            let node = new Node(key, value)
    
            // 2. 判断根结点是否存在
            // 2.1 不存在
            if(!this.root) {
                this.root = node
                return;
            }
    
            // 2.2 存在
            this.insertNode(this.root, node)
            
        }
    
    	// 插入结点函数(内部)
        BinarySearchTree.prototype.insertNode = function(oldNode, newNode) {
            // 1. 判断我们插入的数据的 key是否大于当前遍历结点的 key
            // 1.1 插入数据的 key 大于当前遍历结点的 key
            if(newNode.key < oldNode.key) {
                // 1.1.1 判断当前遍历结点的左结点是否为空
                // 1.1.1.1 为空
                if(oldNode.left === null) {
                    oldNode.left = newNode
                } 
    			// 1.1.1.2 不为空
    			else {
                    this.insertNode(oldNode.left, newNode)
                }
            } 
    		// 1.2 插入数据的 key 小于当前遍历结点的 key
    		else {
    			// 1.2.1 判断当前遍历结点的右结点是否为空
    			// 1.2.1.1 为空
                if(oldNode.right === null) {
                    oldNode.right = newNode
                } 
    			// 1.2.1.2 不为空
    			else {
                    this.insertNode(oldNode.right, newNode)
                }
            }
        }
    }
    

    insert() 方法中,若二叉查找树不为空,我们就调用 insertNode() 内部方法进行递归调用,并先把 root 和 我们新创建的结点 node 传过去当成参数 , 即表示用需要插入的结点先和根节点进行比较,然后慢慢比对下去,找到属于自己的位置插入

    我在代码上都标注了很详细的注解,大家可以消化消化

    我们来使用一下该方法

    let bst = new BinarySearchTree()
    
    bst.insert(50)
    bst.insert(10)
    bst.insert(70)
    bst.insert(5)
    bst.insert(15)
    
    console.log(bst.root)
    

    因为这里我们还没有封装遍历的函数,因此可以靠浏览器的打印来查看二叉查找树是否正确,结果如下
    在这里插入图片描述
    首先,根节点为 50,然后根节点的左子节点为 10,右子结点为 70
    在这里插入图片描述
    然后看到 结点10 的左子结点是 5,右子结点是 15
    在这里插入图片描述
    最后,结点70 没有自己的左右子结点

    总结一下,当前的二叉树如下图
    在这里插入图片描述
    判断一下,这个结果是正确的,这确实是一个二叉查找树,所以我们的 insert()方法就封装好啦

    (4)实现preOrder()方法

    preOrder()方法就是通过先序遍历的方式遍历整个二叉查找树,并返回遍历结果。该方法接收一个回调函数 handle 作为参数, 用于在遍历过程中执行某些操作

    实现思路:

    1. 从根结点开始,按照 访问根结点 => 访问左子树 => 访问右子树 的顺序对各个结点进行访问
    2. 访问到结点时,执行回调函数 handle ,并将访问到的结点的 key 作为参数传入

    因为上边已经详细将结果先序遍历的全过程了,因此我们直接来看代码

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    
    	// 先序遍历并返回结果(外部函数)
        BinarySearchTree.prototype.preOrder = function(handle) {
        
    		// 从整棵二叉查找树的根节点开始遍历
            this.preOrderNodes(this.root, handle)
            
        }
    
        // 以先序遍历的方式遍历整个树(内部函数)
        BinarySearchTree.prototype.preOrderNodes = function(node, handle) {
            if(node !== null) {
                // 将根结点的 key传给回调函数处理
                handle(node.key)
    			// 遍历左子树
                this.preOrderNodes(node.left, handle)
    			// 遍历右子树
                this.preOrderNodes(node.right, handle)
            }
            
        }
    }
    

    我们来使用一下该方法,并详细体会一下递归调用的过程是不是跟我们前面分析的先序遍历的思想一样

    let bst = new BinarySearchTree()
    
    bst.insert(50)
    bst.insert(10)
    bst.insert(70)
    bst.insert(5)
    bst.insert(15)
    
    let str = ''
    bst.preOrder(function(key) {
    	str += `${key} `
    })   
    
    console.log(str)             // 50 10 5 15 70
    

    首先二叉查找树是这样的
    在这里插入图片描述

    1. 刚开始我们从整棵树的根节点 root 开始遍历,先记录 rootkey值,即 50 ;然后遍历 root 的左子树,因此把 root.left 作为下一次调用 preOrderNodes() 方法的根结点

    2. 然后记录一下 结点10,即 50 10,然后我们又要继续遍历 结点10 的左子树,所以就把 结点10.left 作为下一次调用 preOrderNodes() 方法的根结点

    3. 此时访问到了 结点5,并记录一下 50 10 5,再下一次就是遍历 结点5 的左右子树,但因为 结点5 的左右子树都为 null,所以在调用preOrderNodes() 方法时不进行任何操作。到此为止, 结点10 的左子树已经全部遍历完毕,接着就要遍历其右子树,因此把 结点10.right 作为下一次调用 preOrderNodes() 方法的根结点

    4. 此时就访问到了 结点15,并记录一下 50 10 5 15,再下一次就是遍历 结点15 的左右子树,但因为 结点15 的左右子树都为 null,所以在调用preOrderNodes() 方法时不进行任何操作。到此为止,结点50 的左子树已经全部遍历完毕了,接着就要遍历其右子树,因此把 结点50.right 作为下一次调用 preOrderNodes() 方法的根结点

    5. 此时就访问到了 结点70,并记录一下 50 10 5 15 70,再下一次就是遍历 结点15 的左右子树,但因为 结点15 的左右子树都为 null,所以在调用preOrderNodes() 方法时不进行任何操作。到此为止,结点50 的右子树也全部遍历完毕了。

    6. 因为整棵树的根节点的左右子树都遍历完了,所以先序遍历的操作也就完成了,最终结果就为 50 10 5 15 70

    (5)实现inOrder()方法

    inOrder()方法就是通过中序遍历的方式遍历整个二叉查找树,并返回遍历结果。该方法无需传入参数

    实现思路:

    1. 从根结点开始,按照 访问左子树 => 访问根节点 => 访问右子树 的顺序对各个结点进行访问
    2. 访问到结点时,执行回调函数 handle ,并将访问到的结点的 key 作为参数传入

    因为上边已经详细将结果中序遍历的全过程了,因此我们直接来看代码

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    
    	// 中序遍历并返回结果(外部函数)
        BinarySearchTree.prototype.inOrder = function(handle) {
    
            // 从二叉查找树的根结点开始遍历
            this.inOrderNodes(this.root, handle)
            
        }
    
        // 以中序遍历的方式遍历整个树(内部函数)
        BinarySearchTree.prototype.inOrderNodes = function(node, handle) {
            if(node !== null) {
            	// 遍历左子树
                this.inOrderNodes(node.left, handle)
                // 将根结点的 key传给回调函数处理
                handle(node.key)
                // 遍历右子树
                this.inOrderNodes(node.right, handle)
            }
        }
    }
    

    因为树结构的三种遍历方式思想都一样,只不过是遍历的顺序有所差别,这里我就不再花大篇幅来讲解整个遍历过程了,直接来使用一下代码,核对一下结果是否准确

    let bst = new BinarySearchTree()
    
    bst.insert(50)
    bst.insert(10)
    bst.insert(70)
    bst.insert(5)
    bst.insert(15)
    
    let str = ''
    bst.inOrder(function(key) {
    	str += `${key} `
    })   
    
    console.log(str)                 // 5 10 15 50 70
    

    验证了一下,结果是正确的

    (6)实现postOrder()方法

    postOrder()方法就是通过后序遍历的方式遍历整个二叉查找树,并返回遍历结果。该方法无需传入参数

    实现思路:

    1. 从根结点开始,按照 访问左子树 => 访问右子树 => 访问根结点 的顺序对各个结点进行访问
    2. 访问到结点时,执行回调函数 handle ,并将访问到的结点的 key 作为参数传入

    因为上边已经详细将结果后序遍历的全过程了,因此我们直接来看代码

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    
    	// 后序遍历并返回结果(外部函数)
        BinarySearchTree.prototype.postOrder = function(handle) {
    
            // 从二叉查找树的根结点开始遍历
            this.postOrderNodes(this.root, handle)
            
        }
    
        // 以后序遍历的方式遍历整个树(内部函数)
        BinarySearchTree.prototype.postOrderNodes = function(node, handle) {
            if(node !== null) {
            	// 访问左子树
                this.postOrderNodes(node.left, handle)
                // 访问右子树
                this.postOrderNodes(node.right, handle)
                // 将根结点的 key传给回调函数处理
                handle(node.key)
            }
        }
    }
    

    因为树结构的三种遍历方式思想都一样,只不过是遍历的顺序有所差别,这里我就不再花大篇幅来讲解整个遍历过程了,直接来使用一下代码,核对一下结果是否准确

    let bst = new BinarySearchTree()
    
    bst.insert(50)
    bst.insert(10)
    bst.insert(70)
    bst.insert(5)
    bst.insert(15)
    
    let str = ''
    bst.postOrder(function(key) {
    	str += `${key} `
    })   
    
    console.log(str)               // 5 15 10 70 50
    

    验证了一下,结果是正确的

    (7)实现getMax()方法

    getMax()方法就是找到二叉查找树中 key 值最大的结点,并返回该结点对象

    实现思路: 该方法思路比较简单,因为二叉查找树越大的值都是往右走的,即 key值较大的结点都是其父结点的右子结点,因此我们可以从整个二叉查找树的根节点开始,一直向右查找,即 node.right,直到 node.right === null,该结点就为这个二叉查找树中 key值最大的结点

    我们来直接看一下代码吧

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    
    	// 获取二叉树中的最大值
        BinarySearchTree.prototype.getMax = function() {
        	// 从根结点开始遍历
            let node = this.root
    
    		// 一直向二叉查找树的的右边遍历,直到结点没有右子结点
            while(node.right !== null) {
                node = node.right
            }
    
    		// 返回 key值最大的结点对象
            return node
        }
    }
    

    我们来使用一下该方法

    let bst = new BinarySearchTree()
    
    bst.insert(50)
    bst.insert(10)
    bst.insert(70)
    bst.insert(5)
    bst.insert(15)
    bst.insert(60)
    bst.insert(80)
    bst.insert(13)
    bst.insert(12)
    bst.insert(14)
    bst.insert(19)
    bst.insert(20)
    bst.insert(16)
    bst.insert(17)
    
    console.log(bst.getMax())
    // Node { key: 80, value: null, right: null, left: null }
    

    可以看到,最终结果确实返回了 key值最大的结点,为 结点80

    (8)实现getMin()方法

    getMin()方法就是找到二叉查找树中 key 值最小的结点,并返回该结点对象

    实现思路: 该方法思路比较简单,因为二叉查找树越小的值都是往左走的,即 key值较小的结点都是其父结点的左子结点,因此我们可以从整个二叉查找树的根节点开始,一直向左查找,即 node.left,直到 node.left === null,该结点就为这个二叉查找树中 key值最小的结点

    我们来直接看一下代码吧

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    
    	// 获取二叉树中的最小值
        BinarySearchTree.prototype.getMin = function() {
        	// 从二叉查找树的根结点开始遍历
            let node = this.root
            // 一直向二叉查找树的左边遍历,直到结点没有左子结点
            while(node.left !== null) {
                node = node.left
            }
            // 返回 key值最小的结点对象
            return node
        }
    }
    

    我们来使用一下该方法

    let bst = new BinarySearchTree()
    
    bst.insert(50)
    bst.insert(10)
    bst.insert(70)
    bst.insert(5)
    bst.insert(15)
    bst.insert(60)
    bst.insert(80)
    bst.insert(13)
    bst.insert(12)
    bst.insert(14)
    bst.insert(19)
    bst.insert(20)
    bst.insert(16)
    bst.insert(17)
    
    console.log(bst.getMin())
    // Node { key: 5, value: null, right: null, left: null }
    

    可以看到,最终结果确实返回了 key值最小的结点,为 结点5

    (9)实现search()方法

    search()方法就是查找二叉查找树中指定的 key对应的结点的 value 值。该方法接收一个参数,即需要查找的结点的 key

    实现思路: 从二叉查找树的根节点 root 开始遍历,用我们的参数 key1 与遍历到的结点的 key2 进行比较,若 key1 > key2,则向右继续遍历 ;若 key1 < key2,则向左继续遍历 ;若 key1 === key2,则返回该结点的 value 值 ;若遍历到最后,找不到任何结点了,则返回 false

    我们来看一下实现代码

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    
    	// 查找指定的 key对应的数据
        BinarySearchTree.prototype.search = function(key) {
    		// 1. 从二叉查找树的根结点开始遍历
            let node = this.root
    		
    		// 2. 一直与遍历到的结点的 key值进行比较
            while(node !== null) {
            	// 查找的 key值大于当前结点 key值
                if(key > node.key) {
                    node = node.right
                }
                // 查找的 key值小于当前结点 key值 
                else if(key < node.key) {
                    node = node.left
                }
                // 查找到对应 key值的结点 
                else {
                    return node.value
                }
            }
    		// 未找到对应 key值的结点
            return false
        }
    }
    

    因为这个方法要返回结点的 value 值,因此这里我们就给每个结点赋值一定的 value

    let bst = new BinarySearchTree()
    
    bst.insert(50, '我是结点50')
    bst.insert(10, '我是结点10')
    bst.insert(70, '我是结点70')
    bst.insert(5, '我是结点5')
    bst.insert(15, '我是结点15')
    bst.insert(60, '我是结点60')
    bst.insert(80, '我是结点80')
    bst.insert(13, '我是结点13')
    bst.insert(12, '我是结点12')
    bst.insert(14, '我是结点14')
    bst.insert(19, '我是结点19')
    bst.insert(20, '我是结点20')
    bst.insert(16, '我是结点16')
    bst.insert(17, '我是结点17')
    
    console.log(bst.search(13))   // 我是结点13
    console.log(bst.search(50))   // 我是结点50
    console.log(bst.search(99))   // false
    

    (10)实现remove()方法

    remove()方法就是用来移除二叉查找树中指定 key 值的结点。该方法需要接收一个参数 key

    总的来说,在二叉查找树的封装中,我认为 remove() 方法应该算是需要考虑情况最最最最最多的,并且需要一定技巧的方法,因此我们先不着急封装,先来观察二叉查找树,如图

    在这里插入图片描述

    放眼望去,我们可以把结点先总的分成三种类型

    1. 叶子结点(没有子结点)
    2. 只有一个子结点(左子结点或右子结点)
    3. 有两个子结点

    同时,这三种情况就是我们在封装 remove() 方法时要考虑的三种情况,我们来分别研究一下

    • 删除的结点为叶子结点

    假设我们要删除 结点14 ,因为该结点为叶子结点,后面没有其它结点,所以直接删除它不会对后续结点造成影响,即将 结点14 的父节点 结点13 的右子结点设置为 null ,如图

    在这里插入图片描述

    • 删除的结点只有一个子结点

    假设我们要删除的结点为 结点5 ,该结点只有一个右子结点,那么我们只需要用 结点5 的右子结点来代替 结点5 原本的位置,因为 结点5 下面的所有结点肯定都小于 结点10,因此我们只需要将 结点10 的左子结点设置成 结点7 ,如图

    在这里插入图片描述
    同样的,如果我们要删除 结点15 ,也是只需要用其子结点来代替其原来的位置即可,如图
    在这里插入图片描述

    • 删除的结点有两个子结点

    假设我们要删除的结点为 结点10 ,它有两个子结点,且子结点后面还有好多结点。当 结点10 被移除以后,该位置上应该有一个比其左子结点 结点5 以及后面所有结点还要大,同时比其右子结点 结点15 以及后面所有结点还要小的结点,这样的结点怎么找呢?

    这里我给大家一个思路,此时我们有两种选择

    1. 第一种选择就是去 结点10 的左子树里找,找到左子树里 key 值最大的一个结点,在本例中,最大的结点肯定就是 结点7 了,然后我们用 结点7 代替 结点10 的位置,这样就能保证该位置上结点的 key 值大于左子树里所有结点的 key 值,又能保证小于右子树里所有结点的 key 值了。同时我们不能忘记了,结点7 也有它自己的子结点,但能保证的是它一定没有右子结点,因为如果 结点7 还有右子结点,那么 结点7 就不是最大的结点了,所以我们只需要考虑它有无左子结点即可。
      在这里插入图片描述

    2. 第二种选择自然就是去 结点10 的右子树里去找了,找到右子树里 key 值最小的一个结点,在本例中,最小的结点肯定是 结点13 了,然后我们也一样的用 结点13 代替 结点10 的位置,这样就能保证该位置上结点的 key 值大于左子树里所有结点的 key 值,又能保证小于右子树里所有结点的 key 值了。至于 结点13 的子结点如何处理,想必应该不用我再过多重复了吧
      在这里插入图片描述

    这就是 remove() 方法要考虑的三种情况了,接下来我们来讲解一下整个方法的实现思路

    实现思路:

    1. 先遍历整个二叉查找树,找到我们要删除的结点 node ,同时创建变量 parentdirection 分别记录结点 node 的父节点 以及结点node 属于其父节点的左结点还是右结点。若没有遍历到我们要删除的结点,则返回 false
    2. 若遍历到了要删除的结点 node ,则按上面提到三种情况分析结点 node 的类型,然后做出相应的处理,需要注意的是,无论分析哪种类型结点,我们还需要多做一步判断,那就是被删除结点是否为根节点 root

    好了,前面铺垫了那么多,现在我们来写一下代码吧,这里先申明一下,在面对被删除结点右两个子结点时,我选用的是我上面提到的第二种选择

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    
    	// 删除指定 key的数据
        BinarySearchTree.prototype.remove = function(key) {
            let node = this.root
            let parent = null
            let direction = ''
    
            // 1. 找到需要被删除的节点
            while(node !== null) {
                if(key < node.key) {
                    parent = node
                    direction = 'left'
                    node = node.left
                } else if(key > node.key) {
                    parent = node
                    direction = 'right'
                    node = node.right
                } else {
                    break;
                }
            }
    
            // 1.1 未找到对应节点,删除失败
            if(node === null) return false;
    
            // 1.2 找到对应节点
            // 2. 判断节点类型(叶子节点、只有一个子节点、有两个子节点)
    
            // 2.1 节点类型为叶子节点
            if(node.left === null && node.right === null) {
    
                if(node === this.root) {
                    this.root = null
                } else {
                    parent[direction] = null
                }
    
            } 
            
            // 2.2.1 节点只有一个右子节点
            else if(node.left === null) {
                if(node === this.root) {
                    this.root = this.root.right
                } else {
                    parent[direction] = node.right
                }
            } 
    
            // 2.2.2 节点只有一个左子节点
            else if(node.right === null) {
                if(node === this.root) {
                    this.root = this.root.left
                } else {
                    parent[direction] = node.left
                }
            } 
    
            // 2.3 节点有两个子节点
            else {
                let minNode = node.right
                let minNode_parent = node
                // 2.3.1 找到被删除节点右子节点的子孙节点中最小的节点
                while(minNode.left !== null) {
                    minNode_parent = minNode
                    minNode = minNode.left
                }
                
                // 2.3.2 判断 minNode是否有右子节点
                // 2.3.2.1 无右子节点
                if(minNode.right === null) {
                    if(node === this.root) {
                        this.root = minNode                 
                    } else {
                        parent[direction] = minNode      
                    }
                    minNode.left = node.left
                    minNode.right = node.right
                    minNode_parent.left = null      
                }
    
                // 2.3.2.2 有右子节点
                else {
                    if(node === this.root) {
                        this.root = minNode                
                    } else {
                        parent[direction] = minNode
                    }
                    minNode_parent.left = minNode.right
                    minNode.left = node.left
                    minNode.right = node.right      
                }
            }
            
        }    
    }
    

    这里我们仍然用上面提到的那个例子,因此先用 insert() 方法插入相应的结点

    let bst = new BinarySearchTree()
    
    bst.insert(50)
    bst.insert(10)
    bst.insert(70)
    bst.insert(5)
    bst.insert(15)
    bst.insert(7)
    bst.insert(6)
    bst.insert(13)
    bst.insert(14)
    bst.insert(60)
    bst.insert(80)
    
    let str = ''
    bst.preOrder(function(key) {
    	str += `${key} `
    })   
    
    console.log(str)         // 50 10 5 7 6 15 13 14 70 60 80
    

    我们采用先序遍历的方式,先验证二叉查找树的初始状态,此时的二叉树查找树如下图

    在这里插入图片描述

    • 删除结点6(叶子节点)
    bst.remove(6)
    
    let str = ''
    bst.preOrder(function(key) {
    	str += `${key} `
    })   
    
    console.log(str)         // 50 10 5 7 15 13 14 70 60 80
    

    在删除了 结点6 以后,先序遍历输出的结果为 50 10 5 7 15 13 14 70 60 80 ,还原成二叉查找树如下图

    在这里插入图片描述

    • 删除结点15(只有一个子结点)
    bst.remove(15)
    
    let str = ''
    bst.preOrder(function(key) {
    	str += `${key} `
    })   
    
    console.log(str)        // 50 10 5 7 6 13 14 70 60 80
    

    在删除了 结点15 以后,先序遍历输出的结果为 50 10 5 7 6 13 14 70 60 80 ,还原成二叉查找树如下图

    在这里插入图片描述

    • 删除结点10(有两个子结点)
    bst.remove(10)
    
    let str = ''
    bst.preOrder(function(key) {
    	str += `${key} `
    })   
    
    console.log(str)         // 50 13 5 7 6 15 14 70 60 80
    

    在删除了 结点10 以后,先序遍历输出的结果为 50 13 5 7 6 15 14 70 60 80 ,还原成二叉查找树如下图

    在这里插入图片描述

    • 删除根节点50(有两个子结点)
    bst.remove(50)
    
    let str = ''
    bst.preOrder(function(key) {
    	str += `${key} `
    })   
    
    console.log(str)         // 60 10 5 7 6 15 13 14 70 80
    

    在删除了 结点50 以后,先序遍历输出的结果为 60 10 5 7 6 15 13 14 70 80 ,还原成二叉查找树如下图

    在这里插入图片描述

    十三、结束语

    二叉查找树的讲解就到这里了,希望大家对二叉查找树有了更深一层的理解。下一篇文章我将讲解一下红黑树

    大家可以关注我,之后我还会一直更新别的数据结构与算法的文章来供大家学习,并且我会把这些文章放到【数据结构与算法】这个专栏里,供大家学习使用。

    然后大家可以关注一下我的微信公众号:前端印象,等这个专栏的文章完结以后,我会把每种数据结构和算法的笔记放到公众号上,大家可以去那获取。

    或者也可以去我的github上获取完整代码,欢迎大家点个Star

    我是Lpyexplore,创作不易,喜欢的加个关注,点个收藏,给个赞~ 带你们在Python爬虫的过程中学习Web前端

    展开全文
  • 文章目录关于数据结构中树结构的相关分享一、传统的数据结构中的树结构1.1 二叉查找树1.2 平衡二叉树1.3 平衡二叉树之红黑树1.4 B 树1.5 B+树1.6 B* 树二、字典树 ( Trie树 )三、决策树(利用信息论的熵依靠决策树做...

    关于数据结构中树结构的相关分享

    本文参考: 树结构参考文献

    一、传统的数据结构中的树结构

    • 树结构是一种非线性存储结构,存储的是具有“一对多”关系的数据元素的集合。

    在这里插入图片描述

    • 其中,讨论较多的是二叉树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。

    1.1 二叉查找树

    • 二叉查找树定义:又称二叉排序树或二叉搜索树。二叉排序树或者是一棵空树,具有下列性质:
    1. 左子树上所有结点的值均小于它的根结点的值;右子树均大于或等于它的根结点的值;
    2. 左、右子树也分别为二叉排序树;
    • 特点:
      • 二叉查找树的性质:对二叉查找树进行中序遍历,即可得到有序的数列。
      • 二叉查找树的高度决定了二叉查找树的查找效率。

    1.2 平衡二叉树

    • 为了让二叉搜索树的期望高度为 log2n,即使得各操作的时间复杂度为 O(log2n), 于是有了平衡二叉树(即 AVL树)。
    • 定义:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
    • 最小二叉平衡树的节点的公式如下: F(n)=F(n-1)+F(n-2)+1

    1.3 平衡二叉树之红黑树

    • 定义:红黑树是一种自平衡二叉查找树,其典型的用途是实现关联数组(比如 C++ 中的 STL 中的map,和 set 等关联式容器都是基于红黑树的)。

    • 它可以在O(logn)时间内做查找,插入和删除,这里的n是树中元素的数目。这使得它可以适用于实时应用(real time application)。

    • 红黑树还是2-3-4树的一种等同,它们的思想是一样的,只不过红黑树是2-3-4树用二叉树的形式表示的。

    • 2-3-4 树把数据存储在叫做元素的单独单元中。它们组合成节点。每个节点都是下列之一:

      • 2-节点,就是说,它包含 1 个元素和 2 个儿子;
      • 3-节点,就是说,它包含 2 个元素和 3 个儿子;
      • 4-节点,就是说,它包含 3 个元素和 4 个儿子。
    • 如下图(所示):

    在这里插入图片描述

    • 红黑树的性质:
      红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。除了二叉查找树特有性质之外,红黑树还增加了如下要求:

    性质1. 节点是红色或黑色,根是黑色,所有叶子都是黑色

    性质2. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点,即红黑相间),从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点(简称黑高)。

    • 红黑树的图例,如下:

    在这里插入图片描述

    • 性质分析:
      • 有了上面的几个性质作为限制,即可避免二叉查找树退化成单链表的情况。但是,仅仅避免这种情况还不够,这里还要考虑某个节点到其每个叶子节点路径长度的问题。如果某些路径长度过长,那么,在对这些路径上的及诶单进行增删查操作时,效率也会大大降低。这个时候性质4和性质5用途就凸显了,有了这两个性质作为约束,即可保证任意节点到其每个叶子节点路径最长不会超过最短路径的2倍
      • 原因如下:
      • 当某条路径最短时,这条路径必然都是由黑色节点构成。当某条路径长度最长时,这条路径必然是由红色和黑色节点相间构成(性质限定了不能出现两个连续的红色节点)。而性质又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。此时,在路径最长的情况下,路径上红色节点数量 = 黑色节点数量。该路径长度为两倍黑色节点数量,也就是最短路径长度的2倍。(如下图)

    在这里插入图片描述

    • 红黑树的自平衡调整操作:
      • 因为每一个红黑树也是一个特化的二叉查找树,因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。
      • 此外,在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量(O(logn))的颜色变更(实际是非常快速的)和不超过三次树旋转结构变更(对于插入操作是两次)。
      • 虽然插入和删除很复杂,但操作时间仍可以保持为 O(logn) 次。
      • 具体的插入、构建、删除、和调整操作(代码相关的),可参见维基百科。
      • 红黑树调整

    1.4 B 树

    • B树也是一种用于查找的平衡树,但是它不是二叉树,它是多路搜索树。
    • 定义: B树(B-tree)是一种树状数据结构,能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作,都在对数时间内完成。B树即一般化的二叉查找树,可以拥有多于2个子节点。与自平衡二叉查找树不同,B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实现上。

    • B树作为一种多路搜索树(并不是二叉的)的性质:
      1. 定义任意非叶子结点最多只有M个儿子;且M>2
      2. 根结点的儿子数为[2, M], 非根非叶子结点的儿子数为[M/2, M];
      3. 每个结点存放至少 M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)
      4. 非叶子结点的关键字个数 = 指向儿子的指针个数-1
      5. 非叶子结点的关键字有序:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
      6. 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,
        P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
      7. 所有叶子结点位于同一层

    • M=3 的 B 树示例图:
      在这里插入图片描述

    • 比起正常的平衡二叉树,B树每个节点显然能存储的数据更多,在查找数据方面也显得比较高效。
    • B树创建的示意图:


      B 树生成示意图

    1.5 B+树

    B+树是B树的变体,也是一种多路搜索树:

    1. 其定义基本与B-树相同,除了:
    2. 非叶子结点的子树指针与关键字个数相同
    3. 非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);
    4. 为所有叶子结点增加一个链指针
    5. 所有关键字都在叶子结点出现
    • 下图为 M=3 的 B+ 树的示意图

    在这里插入图片描述

    • B+树的搜索与B树也基本相同,区别是B+树只有达到叶子结点才命中(B树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;

    B+ 树的性质:
    1.所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;
    2.不可能在非叶子结点命中;
    3.非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;
    4.更适合文件索引系统。

    • B + 树的创建示意图:


      创建示意图

    • B 树和 B+ 树的异同:

      • 结构上
        • B树中关键字集合分布在整棵树中,叶节点中不包含任何关键字信息,而B+树关键字集合分布在叶子结点中,非叶节点只是叶子结点中关键字的索引;
        • B树中任何一个关键字只出现在一个结点中,而B+树中的关键字必须出现在叶节点中,也可能在非叶结点中重复出现;
      • 性能上(也即为什么说B+树比B树更适合实际应用中操作系统的文件索引和数据库索引?)
        • 不同于B树只适合随机检索,B+树同时支持随机检索和顺序检索
        • B+树的磁盘读写代价更低。B+树的内部结点并没有指向关键字具体信息的指针,其内部结点比B树小,盘块能容纳的结点中关键字数量更多,可一次性将索引读入内存中可以查找的关键字也就越多,相对的,IO读写次数也就降低了。而IO读写次数是影响索引检索效率的最大因素。也就是说同样数据情况下,B+ 树会 B 树更加“矮胖”,因此查询效率更快。
        • B+树的查询效率更加稳定。B树搜索有可能会在非叶子结点结束,越靠近根节点的记录查找时间越短,只要找到关键字即可确定记录的存在,其性能等价于在关键字全集内做一次二分查找。而在B+树中,顺序检索比较明显,随机检索时,任何关键字的查找都必须走一条从根节点到叶节点的路,所有关键字的查找路径长度相同,导致每一个关键字的查询效率相当。
        • (数据库索引采用B+树的主要原因是,)B-树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。B+树的叶子节点使用指针顺序连接在一起,只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作(或者说效率太低)。

    1.6 B* 树

    • B* 树是 B+ 树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针,将结点的最低利用率从1/2提高到2/3。

    • 图示如下:
      在这里插入图片描述

    • B* 树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2);

    • B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;

    • B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;

    所以,B*树分配新结点的概率比B+树要低,空间使用率更高。

    二、字典树 ( Trie树 )

    Trie树称为字典树,又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

    Tire树的三个基本性质:

    1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符;
    2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串;
    3. 每个节点的所有子节点包含的字符都不相同。

    Tire树的应用:

    • 串的快速检索

    给出N个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。在这道题中,我们可以用数组枚举,用哈希,用字典树,先把熟词建一棵树,然后读入文章进行比较,这种方法效率是比较高的。

    • “串”排序

    给定N个互不相同的仅由一个单词构成的英文名,让你将他们按字典序从小到大输出。用字典树进行排序,采用数组的方式创建字典树,这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。

    • 最长公共前缀

    对所有串建立字典树,对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数,于是,问题就转化为求公共祖先的问题。

    三、决策树(利用信息论的熵依靠决策树做决策选择)

    • 作为一个Coder,经常遇到敲if, else if, else,其实就就是决策树的思想。只是这么多条件,哪个条件特征先做if,哪个条件特征后做if比较优呢?怎么准确定量选择这个标准就是决策树算法的要做的事情。
    • 信息论中熵的概念。熵度量了事物的不确定性,越不确定的事物,它的熵就越大。具体的,随机变量X的熵的表达式如下:
    • 单随机变量 X 的熵

    H(X)=i=1npilogpi H(X) = -\sum\limits_{i=1}^{n}p_i logp_i

    • 双变量 X和Y 的联合熵
      H(X,Y)=i=1np(xi,yi)logp(xi,yi) H(X,Y) = -\sum\limits_{i=1}^{n}p(x_i,y_i)logp(x_i,y_i)
    • 条件熵的表达式H(X|Y),条件熵类似于条件概率,它度量了我们的X在知道Y以后剩下的不确定性。表达式如下:

    H(XY)=i=1np(xi,yi)logp(xiyi)=j=1np(yj)H(Xyj) H(X|Y) = -\sum\limits_{i=1}^{n}p(x_i,y_i)logp(x_i|y_i) = \sum\limits_{j=1}^{n}p(y_j)H(X|y_j)

    • 根据决策树构建的过程,可以按照特征选择方式分成如下三种大类:

    在这里插入图片描述

    • 信息增益(又称为互信息),定义为: H(X) - H(X|Y) ,记为I(X,Y)。
    • 在决策树 ID3 算法中叫做信息增益。ID3算法就是用信息增益来判断当前节点应该用什么特征来构建决策树。信息增益大,则越适合用来分类。
    • ID3 的缺点:
      • 没有考虑连续特征,比如长度,密度都是连续值,无法在ID3运用。
      • 取值比较多的特征比取值少的特征信息增益大。
      • ID3算法对于缺失值的情况没有做考虑等
      • 没有考虑过拟合的问题
    • 于是提出了 C4.5
      • 对于使用信息增益作为标准容易偏向于取值较多的特征的问题。引入一个信息增益率的变量Ir(X,Y),它是信息增益和特征熵的比值。表达式如下:

    IR(D,A)=I(A,D)HA(D) I_R(D,A) = \frac{I(A,D)}{H_A(D)}

    • C4.5 的缺点:
      • 决策树算法非常容易过拟合
      • C4.5生成的是多叉树,在计算机科学中二叉树往往运算效率更高。
      • C4.5只能用于分类,如果能将决策树用于回归的话可以扩大它的使用范围。
      • C4.5由于使用了熵模型,里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。是否可以通过适当的降低结果准确性来简化模型的运算强度。
    • 前面两种方式都是基于信息论的熵模型,有耗时的计算问题,CART分类树算法使用基尼系数来代替信息增益比,基尼系数代表了模型的不纯度,基尼系数越小,则不纯度越低,特征越好。这和信息增益(比)是相反的。(其实就是加了一个负号,对比信息熵的定义)
    • 在分类问题中,假设有K个类别,第k个类别的概率为pk, 则基尼系数的表达式为:

    Gini(p)=k=1Kpk(1pk)=1k=1Kpk2 Gini(p) = \sum\limits_{k=1}^{K}p_k(1-p_k) = 1- \sum\limits_{k=1}^{K}p_k^2

    • 如果是二类分类问题,概率是p,则基尼系数简化为:

    Gini(p)=2p(1p) Gini(p) = 2p(1-p)

    在这里插入图片描述

    四、梅克尔帕特里夏树( Merkle Patricia Tree, MPT)

    • MPT: 基于加密学的,自校验防篡改的数据结构,用来存储键值对关系。MPT是确定的。确定性是指同样内容的键值,将被保证找到同样的结果,有同样的根哈希。关于效率方面,对树的插入,查找,删除的时间复杂度控制在O(log(n))。
    • 前言:基数树(Radix Tree)
    • 在一个标准的基数树里,要存储的数据,按下述所述:
    [i0, i1, ... iN, value]
    
    • 其中的i0到iN的表示一般是二进制或十六进制的格式的字母符号。value表示的是树节点中存储的最终值。每一个i0到iN槽位的值,要么是NULL,要么是指向另一个节点的指针(在当前这个场景中,存储的是其它节点的哈希值)。这样我们就实现了一个简单的键值对存储。举个例子来说,如果你想在这个基数树中,找到键dog所对应的值。首先需要将dog转换为比如ascii码值(十六进制表示是646f67)。然后按字母序形成一个逐层向下的树。沿着字母组成的路径,在树的底部叶节点上,即找到dog对应的值。具体来说,首先找到存储这个键值对数据的根节点,找到下一层的第6个节点,然后再往下一层,找到节点4,然后一层一层往下找,直到完成了路径 root -> 6 -> 4 -> 6 -> f -> 6 -> 7。这样你将最终找到值的对应节点。
    • 基数树的缺点:
      • 基数树另一个主要的缺陷是低效。即使你只想存一个键值对,但其中的键长度有几百字符长,那么每个字符的那个层级你都需要大量的额外空间。每次查找和删除都会有上百个步骤。在这里我们引入Patricia树来解决这个问题。
    • Patricia 树
    • Patricia树,或称Patricia trie,或 crit bit tree,压缩前缀树,是一种更节省空间的Trie。对于基数树的每个节点,如果该节点是唯一的儿子的话,就和父节点合并。

    在这里插入图片描述

    • Merkle 树
    • Merkle Tree,通常也被称作Hash Tree,顾名思义,就是存储hash值的一棵树。Merkle树的叶子是数据块(例如,文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。
    • Merkle Tree 由 Hash List演化而来:
    • 在点对点网络中作数据传输的时候,会同时从多个机器上下载数据,而且很多机器可以认为是不稳定或者不可信的。为了校验数据的完整性,更好的办法是把大的文件分割成小的数据块(例如,把分割成2K为单位的数据块)。这样的好处是,如果小块数据在传输过程中损坏了,那么只要重新下载这一快数据就行了,不用重新下载整个文件。
      怎么确定小的数据块没有损坏哪?只需要为每个数据块做Hash。BT下载的时候,在下载到真正数据之前,我们会先下载一个Hash列表。那么问题又来了,怎么确定这个Hash列表本身是正确的哪?答案是把每个小块数据的Hash值拼到一起,然后对这个长字符串在作一次Hash运算,这样就得到Hash列表的根Hash(Top Hash or Root Hash)。下载数据的时候,首先从可信的数据源得到正确的根Hash,就可以用它来校验Hash列表了,然后通过校验后的Hash列表校验数据块。

    在这里插入图片描述

    • Merkle Tree 可以看做Hash List的泛化(Hash List可以看作一种特殊的Merkle Tree,即树高为2的多叉Merkle Tree。
    • 在最底层,和哈希列表一样,我们把数据分成小的数据块,有相应地哈希和它对应。但是往上走,并不是直接去运算根哈希,而是把相邻的两个哈希合并成一个字符串,然后运算这个字符串的哈希,这样每两个哈希就结婚生子,得到了一个”子哈希“。如果最底层的哈希总数是单数,那到最后必然出现一个单身哈希,这种情况就直接对它进行哈希运算,所以也能得到它的子哈希。于是往上推,依然是一样的方式,可以得到数目更少的新一级哈希,最终必然形成一棵倒挂的树,到了树根的这个位置,这一代就剩下一个根哈希了,我们把它叫做 Merkle Root。

    在这里插入图片描述

    • 在p2p网络下载网络之前,先从可信的源获得文件的Merkle Tree树根。一旦获得了树根,就可以从其他从不可信的源获取Merkle tree。通过可信的树根来检查接受到的MerkleTree。如果Merkle Tree是损坏的或者虚假的,就从其他源获得另一个Merkle Tree,直到获得一个与可信树根匹配的MerkleTree。
    • Merkle Tree和HashList的主要区别是,可以直接下载并立即验证 Merkle Tree的一个分支。因为可以将文件切分成小的数据块,这样如果有一块数据损坏,仅仅重新下载这个数据块就行了。如果文件非常大,那么Merkle tree和Hash list都很到,但是Merkle tree可以一次下载一个分支,然后立即验证这个分支,如果分支验证通过,就可以下载数据了。而Hash list只有下载整个hash list才能验证。
    • MPT(Merkle Patricia Tree)
    • MPT(Merkle Patricia Tree)就是这两者混合的数据结构。
    • MPT树中的节点包括空节点、叶子节点、扩展节点和分支节点:
      • 空节点,简单的表示空,在代码中是一个空串。
      • 叶子节点(leaf),表示为[key,value]的一个键值对,其中key是key的一种特殊十六进制编码,value是value的RLP编码。
      • 扩展节点(extension),也是[key,value]的一个键值对,但是这里的value是其他节点的hash值,这个hash可以被用来查询数据库中的节点。也就是说通过hash链接到其他节点。
      • 分支节点(branch),因为MPT树中的key被编码成一种特殊的16进制的表示,再加上最后的value,所以分支节点是一个长度为17的list,前16个元素对应着key中的16个可能的十六进制字符,如果有一个[key,value]对在这个分支节点终止,最后一个元素代表一个值,即分支节点既可以搜索路径的终止也可以是路径的中间节点。
      • MPT 树中另一个重要的概念是十六进制前缀(hex-prefix, HP)编码,用来对key进行编码。因为字母表是16进制的,所以每个节点可能有16个孩子。因为有两种[key,value]节点(叶节点和扩展节点),引进一种特殊的终止符标识来标识key所对应的是值是真实的值,还是其他节点的hash。如果终止符标记被打开,那么key对应的是叶节点,对应的值是真实的value。如果终止符标记被关闭,那么值就是用于在数据块中查询对应的节点的hash。

    MPT

    五、计算机科学中的树结构

    在这里插入图片描述

    参考文献:
    1、http://blog.jobbole.com/111680/
    2、https://blog.csdn.net/mine_song/article/details/63251546
    3、https://www.cnblogs.com/pinard/p/6050306.html
    4、https://blog.csdn.net/qq_33935254/article/details/55505472

    展开全文
  • 树结构大全

    万次阅读 多人点赞 2018-11-10 10:58:38
    文章目录说明树结构的一些基本定义树结构的性质二叉树二叉树的定义满二叉树与完全二叉树二叉树的性质结点定义二叉树的创建二叉树的遍历基于深度遍历二叉树基于层次遍历二叉树(方法一)基于层次遍历二叉树(方法二)...

    说明


    • 主要讲解二叉树及其相关内容
    • 次要说明其他树结构
    • 以后会进行不定期更新

    主要参考以下书籍

    • 程序员面试笔记
    • 慕课网:数据算法与结构
    • 其他…

    树结构的一些基本定义


    示意图

    树

    • 结点的度:结点拥有的子树的数目。eg:结点 A 的度为3
    • 树的度:树种各结点度的最大值。eg:树的度为3
    • 叶子结点:度为 0 的结点。g:E、F、C、G 为叶子结点
    • 孩子结点:一个结点的子树的根节点。eg:B、C、D 为 A 的子结点
    • 双亲结点:B 为 A 的子结点,那么 A 为 B 的双亲结点
    • 兄弟结点:一个双亲结点结点的孩子互为兄弟结点。eg:B、C、D 为兄弟结点
    • 结点的层次:根节点为第一层,子结点为第二层,依次向下递推…eg:E、F、G 的层次均为 3
    • 树的深度:树种结点的最大深度。eg:该树的深度为 3
    • 森林:m 棵互不相交的树称为森林

    树结构的性质


    1. 非空树的结点总数等于树种所有结点的度之和加 1
    2. 度为 K 的非空树的第 i 层最多有 ki-1 个结点(i >= 1)
    3. 深度为 h 的 k 叉树最多有(kh - 1)/(k - 1)个结点
    4. 具有 n 个结点的 k 叉树的最小深度为 logk(n(k-1)+1))

    二叉树(Binary-Tree)


    二叉树的定义

    二叉树是一种特殊的树:它或者为空,或者由一个根节点加上根节点的左子树和右子树组成,这里要求左子树和右子树互不相交,且同为二叉树,很显然,这个定义是递归形式的。

    满二叉树与完全二叉树

    满二叉树: 如果一棵二叉树的任意一个结点或者是叶子结点,或者有两棵子树,同时叶子结点都集中在二叉树的最下面一层上,这样的二叉树称为满二叉树

    完全二叉树: 若二叉树中最多只有最下面两层结点的度小于 2 ,并且最下面一层的结点(叶子结点)都依次排列在该层最左边的位置上,具有这样结构特点的树结构称为完全二叉树。

    在这里插入图片描述

    二叉树的性质

    1. 在二叉树中第 i 层上至多有 2i-1 个结点(i >=1)
    2. 深度为 k 的二叉树至多有 2k-1 个结点(k >=1)
    3. 对于任何一棵二叉树,如果其叶子结点数为 n0 ,度为 2 的结点数为 n2 ,那么 n0 = n2 + 1
    4. 具有 n 个结点的完全二叉树的深度为 log2n + 1

    结点定义

    typedef struct BiTNode{
    	ElemType data;
    	struct BiTNode * lchild, * rchild;
    } BiTNode, *BiTree;
    

    二叉树的创建

    /*创建一棵二叉树*/
    void CreatBiTree(BiTree *T) {
        char c;
        scanf("%c", &c);
        if(c == ' ') *T = NULL;
        else {
            *T = (BiTNode * )malloc(sizeof(BiTNode));  /*创建根结点*/
            (*T)->data = c;    /*向根结点中输入数据*/
            CreatBiTree(&((*T)->lchild));  /*递归地创建左子树*/
            CreatBiTree(&((*T)->rchild));  /*递归地创建右子树*/
        }
    }
    

    二叉树的遍历

    基于深度遍历二叉树

    分为先序(DLR)、中序(LDR)、后序遍历(LRD)

    #include "stdio.h"
    #include "malloc.h"
    
    typedef struct BiTNode {
        char data;   /*结点的数据域*/
        struct BiTNode *lchild, *rchild;   /*指向左孩子和右孩子*/
    } BiTNode, *BiTree;
    
    /*创建一棵二叉树*/
    void CreatBiTree(BiTree *T) {
        char c;
        scanf("%c", &c);
        if(c == ' ') *T = NULL;
        else {
            *T = (BiTNode * )malloc(sizeof(BiTNode));  /*创建根结点*/
            (*T)->data = c;    /*向根结点中输入数据*/
            CreatBiTree(&((*T)->lchild));  /*递归地创建左子树*/
            CreatBiTree(&((*T)->rchild));  /*递归地创建右子树*/
        }
    }
    
    /*前序遍历二叉树*/
    void PreOrderTraverse(BiTree T ) {
        if(T) {  /*递归结束条件,T为空*/
            printf("%3c", T->data); /*访问根结点,将根结点内容输出*/
            PreOrderTraverse(T->lchild);  /*先序遍历T的左子树*/
            PreOrderTraverse(T->rchild);  /*先序遍历T的右子数*/
        }
    }
    
    /*中序遍历二叉树*/
    void InOrderTraverse(BiTree T) {
        if(T) {  /*如果二叉树为空,递归遍历结束*/
            InOrderTraverse(T->lchild);  /*中序遍历T的左子树*/
            printf("%3c", T->data);      /*访问根结点*/
            InOrderTraverse(T->rchild);  /*中序遍历T的右子数*/
        }
    }
    
    /*后序遍历二叉树*/
    void PosOrderTraverse(BiTree T) {
        if(T) {  /*如果二叉树为空,递归遍历结束*/
            PosOrderTraverse(T->lchild);  /*后序遍历T的左子树*/
            PosOrderTraverse(T->rchild);  /*后序遍历T的右子数*/
            printf("%3c", T->data);       /*访问根结点*/
        }
    }
    
    
    int main() {
        BiTree T = NULL;  /*最开始T指向空*/
        printf("Input some characters to create a binary tree\n");
        CreatBiTree(&T);  /*创建二叉树*/
        printf("The squence of preorder traversaling binary tree\n");
        PreOrderTraverse(T); /*先序遍历二叉树*/
        printf("\nThe squence of inorder traversaling binary tree\n");
        InOrderTraverse(T);  /*中序遍历二叉树*/
        printf("\nThe squence of posorder traversaling binary tree\n");
        PosOrderTraverse(T); /*后序遍历二叉树*/
        getchar();
        getchar();
    }
    

    基于层次遍历二叉树

    方法一

    #include "stdio.h"
    
    typedef struct BiTNode {
       char data;   /*结点的数据域*/
       struct BiTNode *lchild, *rchild;   /*指向左孩子和右孩子*/
    } BiTNode, *BiTree;
    
    /*创建一棵二叉树*/
    void CreatBiTree(BiTree *T) {
       char c;
       scanf("%c", &c);
       if(c == ' ') *T = NULL;
       else {
          *T = (BiTNode * )malloc(sizeof(BiTNode));  /*创建根结点*/
          (*T)->data = c;    /*向根结点中输入数据*/
          CreatBiTree(&((*T)->lchild));  /*递归地创建左子树*/
          CreatBiTree(&((*T)->rchild));  /*递归地创建右子树*/
       }
    }
    
    /*遍历二叉树*/
    void PreOrderTraverse(BiTree T ) {
       if(T) {  /*递归结束条件,T为空*/
          printf("%3c", T->data); /*访问根结点,将根结点内容输出*/
          PreOrderTraverse(T->lchild);  /*先序遍历T的左子树*/
          PreOrderTraverse(T->rchild);  /*先序遍历T的右子数*/
       }
    }
    
    void visit(BiTree p) {
       printf("%3c", p->data);
    }
    
    void layerOrderTraverse(BiTree T) {
       BiTree queue[20], p;
       int front, rear;
       if(T != NULL) {
          queue[0] = T;       /*将根结点的指针(地址)入队列*/
          front = -1;
          rear = 0;
          while(front < rear) {   /*当队列不为空时进入循环*/
             p = queue[++front]; /*取出队头元素*/
             visit(p);       /*访问p指向的结点元素*/
             if(p->lchild != NULL) /*将p结点的左孩子结点指针入队列*/
                queue[++rear] = p->lchild;
             if(p->rchild != NULL) /*将p结点的右孩子结点指针入队列*/
                queue[++rear] = p->rchild;
          }
       }
    }
    
    main() {
       BiTree T = NULL;  /*最开始T指向空*/
       printf("Input some characters to create a binary tree\n");
       CreatBiTree(&T);  /*创建二叉树*/
    
       printf("\nThe squence of layerorder traversaling binary tree\n");
       layerOrderTraverse(T);
       getchar();
       getchar();
    }
    

    方法二

    void layerOrderTraverse(BiTree T){
    	BiTree p;
    	queue<BiTree> q;
    	if(T != NULL){
    		q.push(T);
    		while(!q.empty()){
    			p = q.front();
    			q.pop();
    			visit(p);  // 自定义访问操作
    			if(p->lchild != NULL)
    				q.push(p->lchild);
    			if(p->rchild != NULL)
    				q.push(p->rchild);
    		}
    	}
    }
    

    二叉树的深度

    方法一

    #include "stdio.h"
    #include "malloc.h"
    
    typedef struct BiTNode{
        char data;   /*结点的数据域*/
        struct BiTNode *lchild , *rchild;  /*指向左孩子和右孩子*/
    } BiTNode , *BiTree;
    
    /*创建一棵二叉树*/
    void CreatBiTree(BiTree *T)
    {
        char c;
        scanf("%c",&c);
        if(c == ' ') *T = NULL;
        else{
           *T = (BiTNode * )malloc(sizeof(BiTNode));  /*创建根结点*/
            (*T)->data = c;    /*向根结点中输入数据*/
            CreatBiTree(&((*T)->lchild));  /*递归地创建左子树*/
            CreatBiTree(&((*T)->rchild));  /*递归地创建右子树*/
        }
    }
    
    /*计算二叉树的深度*/
    void getDepth(BiTree T,int n,int *level)
    {
       if(T!=NULL)
       {
            if(n> *level)
            {
                *level = n;
            }
            getDepth(T->lchild,n+1,level);
            getDepth(T->rchild,n+1,level);
       }
    }
    
    int getBitreeDepth(BiTree T)
    {
        int level = 0;
        int n = 1;
        getDepth(T,n,&level);
        return level ;
    }
    
    main()
    {
        BiTree T = NULL;    /*最开始T指向空*/
        printf("Input some characters to create a binary tree \n");
        CreatBiTree(&T);    /*创建二叉树*/
        printf("\nThe depth of the binary tree is %d\n",getBitreeDepth(T));
        getchar() ;
    	getchar() ;
    }
    

    方法二

    int getBitreeDepth(BiTree T){
    	int leftHeight, rightHeight, maxHeight;
    	if(T != NULL){
    		leftHeight = getBitreeDepth(T->lchild);  // 计算左子树的深度
    		rightHeight = getBitreeDepth(T->rchild);  // 计算右子树的深度
    		maxHeight = leftHeight > rightHeight ? leftHeight : rightHeight;  // 比较左右子树的深度
    		return maxHeight + 1;  // 返回二叉树的深度
    	else{
    		return 0;
    	}
    }
    

    二叉树叶子结点个数

    #include "string.h" 
    #include "stdio.h" 
    #include "malloc.h"
    
    typedef struct BiTNode{
        char data;   /*结点的数据域*/
        struct BiTNode *lchild , *rchild;  /*指向左孩子和右孩子*/
    } BiTNode , *BiTree;
    
    void CreatBiTree(BiTree *T){
        char c;
        scanf("%c",&c);
        if(c == ' ') *T = NULL;
        else{
           *T = (BiTNode * )malloc(sizeof(BiTNode));  /*创建根结点*/
            (*T)->data = c;    /*向根结点中输入数据*/
            CreatBiTree(&((*T)->lchild));  /*递归地创建左子树*/
            CreatBiTree(&((*T)->rchild));  /*递归地创建右子树*/
        }
    }
    
    void getLeavesConut (BiTree T,int *count){
        if(T!=NULL && T->lchild==NULL && T->rchild==NULL){   /*访问到叶结点*/
            *count = *count + 1;
        }
        if(T){
            getLeavesConut (T->lchild,count);  /*先序遍历T的左子树*/
            getLeavesConut (T->rchild,count);  /*先序遍历T的右子数*/
        }
    }
    
    int getBiTreeLeavesCount(BiTree T) {
    	int count = 0;				/*在主调函数中定义变量count,初始值为0*/
    	getLeavesConut(T, &count);	/*调用递归函数getLeavesConut计算叶子结点个数*/
    	return count;				/*返回叶子结点个数*/
    }
    
    main()
    {
       BiTree T = NULL;				/*初始化T */
       int count = 0;
       printf("Input some characters to create a binary tree \n");
       CreatBiTree(&T);				/*创建一棵二叉树*/
       getLeavesConut (T,&count);	/*计算二叉树中叶子结点的个数 */
       printf("The number of leaves of BTree are %d\n",count);
       getchar();
       getchar();
    }
    

    二叉排序树(Binary-Sort-Tree)


    什么是二叉排序树

    二又排序树或者为一棵空树,或者是具有下列性质的二又树:

    1. 若它的左子树不为空,则左子树上的所有结点的值均小于根结点的值
    2. 若它的右子树不为空,则右子树上的所有结点的值均大于根节点的值
    3. 二叉排序树的左右子树也都是二叉排序树

    在这里插入图片描述

    二叉排序树的查找

    BiTree SearchBST(BiTree T, dataTYpe){
    	if(T == NULL)
    		return NULL;
    	if(T->data == key)
    		return T;
    	if(key < T->data)
    		return SearchBST(T-> lchild, key);
    	else
    		return SearchBST(T-> rchild, key);
    }
    

    最低公共祖先

    在这里插入图片描述

    分析

    从整棵二又排序树的根结点出发,
    当访间的当前结点同时大于给定的两个结点时、沿左指前进;
    当访间的当前结点同时小于給定的两个结点时,沿右指针前进;
    当第一次访问到介于给定的两个结点值之间的那个结点时即是它们的最低公共祖先结点

    然鹅,这个算法并不完善,因为这个算法适用的前提是给定的两个结点分别位于二叉排序树中某个结点的左右子树上

    假设给定的两个结点分别为a和b,并且 a 是 b 的祖先,那么结点 a 和 b 的最低公共祖先就是 a 的父结点,因为 a 的父结点一定也是 b 的祖先,同时该结点也必然是 a 和 b 的最低公共祖先。

    另外,如果给定的 a 或 b 其中一个为根结点的值,那么这种情况是不存在公共最低祖先的,因为根结点没有祖先,所以也应把这种情况考虑进去。

    #include "stdio.h"
    #include "malloc.h"
    #include "string.h"
    
    typedef struct BiTNode{
        int data;   /*结点的数据域*/
        struct BiTNode *lchild;
        struct BiTNode *rchild;  /*指向左孩子和右孩子*/
    } BiTNode , *BiTree;
    
    int findLowestCommonAncestor(BiTree T,int value1, int value2) {
    	BiTree curNode = T;  /*curNode为当前访问结点,初始化为T*/
    	if(T->data == value1 || T->data == value2) {
    		return -1;    /*value1和value2有一个为根结点,因此没有公共祖先,返回-1*/
    	}
    	while(curNode != NULL){
    		if (curNode->data > value1 &&
    			curNode->data > value2 && curNode->lchild->data != value1 &&
    			curNode->lchild->data != value2) {
    /*当前结点的值同时大于value1和value2,且不是value1和value2的父结点*/
    				curNode = curNode->lchild;  
    		} else if (curNode->data < value1 &&
    			curNode->data < value2 && curNode->rchild->data != value1 &&
    			curNode->rchild->data != value2) {
    /*当前结点的值同时小于value1和value2,且不是value1和value2的父结点*/
    				curNode = curNode->rchild;
    		} else {
    			return curNode->data;	/*找到最低公共祖先*/
    		}
    	}
    }
    
    void CreatBiTree(BiTree *T){
        int d;
        scanf("%d",&d);
        if(d == 0) *T = NULL;
        else{
           *T = (BiTNode * )malloc(sizeof(BiTNode));  /*创建根结点*/
            (*T)->data = d;    /*向根结点中输入数据*/
            CreatBiTree(&((*T)->lchild));  /*递归地创建左子树*/
            CreatBiTree(&((*T)->rchild));  /*递归地创建右子树*/
        }
    }
    
    main()
    {
    	BiTree T;
    	int value1,value2;
    	int ancestorValue;
    	printf("Please create a binary sort tree\n");
    	CreatBiTree(&T);
    	printf("Input two values for searching lowest common ancestor\n");
    	scanf("%d,%d",&value1,&value2);
    	ancestorValue = findLowestCommonAncestor(T,value1,value2);
    	if (ancestorValue != -1) {
    		printf("The  lowest common ancestor is %d\n", ancestorValue);
    	} else {
    		printf("There is no ancestor\n");
    	}
    	getchar();
    }
    

    二叉排序树 VS 二叉堆(Binary-Heap)


    在这里插入图片描述

    两者的相同点与不同点

    相同点

    二叉堆也是一种树结构

    不同点

    1. 任何一个结点都不大于父亲节点(亦即左右结点均不大于父节点)
    2. 必须是一棵完全二叉树(结点必须集中在最左侧),亦即最大堆
    3. 用数组存储二叉堆,原因在于满二叉树的结点索引存在倍数关系

    在这里插入图片描述

    关系描述为:左结点是父节点的 2 倍,右结点为父节点的 2 倍 加 1(根结点的序列为 1)

    二叉堆主要表现为最大堆(Max-Heap),主要涉及以下内容

    最大堆的一些基本操作(Max-Heap)

    • 创建
    • 删除
    • 元素个数
    • 插入
    • 堆顶元素
    • 最大元素
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    template<typename Item>
    class MaxHeap{
    
    private:
        Item *data;
        int count;
        int capacity;
    
        void shiftUp(int k){
            while( k > 1 && data[k/2] < data[k] ){
                swap( data[k/2], data[k] );
                k /= 2;
            }
        }
    
        void shiftDown(int k){
            while( 2*k <= count ){
                int j = 2*k;
                if( j+1 <= count && data[j+1] > data[j] ) j ++;
                if( data[k] >= data[j] ) break;
                swap( data[k] , data[j] );
                k = j;
            }
        }
    
    public:
    
        // 构造函数, 构造一个空堆, 可容纳capacity个元素
        MaxHeap(int capacity){
            data = new Item[capacity+1];
            count = 0;
            this->capacity = capacity;
        }
    
        // 构造函数, 通过一个给定数组创建一个最大堆
        // 该构造堆的过程, 时间复杂度为O(n)
        MaxHeap(Item arr[], int n){
            data = new Item[n+1];
            capacity = n;
    
            for( int i = 0 ; i < n ; i ++ )
                data[i+1] = arr[i];
            count = n;
    
            for( int i = count/2 ; i >= 1 ; i -- )
                shiftDown(i);
        }
    
        ~MaxHeap(){
            delete[] data;
        }
    
        // 返回堆中的元素个数
        int size(){
            return count;
        }
    
        // 返回一个布尔值, 表示堆中是否为空
        bool isEmpty(){
            return count == 0;
        }
    
        // 像最大堆中插入一个新的元素 item
        void insert(Item item){
            assert( count + 1 <= capacity );
            data[count+1] = item;
            shiftUp(count+1);
            count ++;
        }
    
        // 从最大堆中取出堆顶元素, 即堆中所存储的最大数据
        Item extractMax(){
            assert( count > 0 );
            Item ret = data[1];
            swap( data[1] , data[count] );
            count --;
            shiftDown(1);
            return ret;
        }
    
        // 获取最大堆中的堆顶元素
        Item getMax(){
            assert( count > 0 );
            return data[1];
        }
    };
    

    最大索引堆(Max-Heap-Index)

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    // 最大索引堆
    template<typename Item>
    class IndexMaxHeap{
    
    private:
        Item *data;     // 最大索引堆中的数据
        int *indexes;   // 最大索引堆中的索引, indexes[x] = i 表示索引i在x的位置
        int *reverse;   // 最大索引堆中的反向索引, reverse[i] = x 表示索引i在x的位置
    
        int count;
        int capacity;
    
        // 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
        void shiftUp( int k ){
    
            while( k > 1 && data[indexes[k/2]] < data[indexes[k]] ){
                swap( indexes[k/2] , indexes[k] );
                reverse[indexes[k/2]] = k/2;
                reverse[indexes[k]] = k;
                k /= 2;
            }
        }
    
        // 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
        void shiftDown( int k ){
    
            while( 2*k <= count ){
                int j = 2*k;
                if( j + 1 <= count && data[indexes[j+1]] > data[indexes[j]] )
                    j += 1;
    
                if( data[indexes[k]] >= data[indexes[j]] )
                    break;
    
                swap( indexes[k] , indexes[j] );
                reverse[indexes[k]] = k;
                reverse[indexes[j]] = j;
                k = j;
            }
        }
    
    public:
        // 构造函数, 构造一个空的索引堆, 可容纳capacity个元素
        IndexMaxHeap(int capacity){
    
            data = new Item[capacity+1];
            indexes = new int[capacity+1];
            reverse = new int[capacity+1];
            for( int i = 0 ; i <= capacity ; i ++ )
                reverse[i] = 0;
    
            count = 0;
            this->capacity = capacity;
        }
    
        ~IndexMaxHeap(){
            delete[] data;
            delete[] indexes;
            delete[] reverse;
        }
    
        // 返回索引堆中的元素个数
        int size(){
            return count;
        }
    
        // 返回一个布尔值, 表示索引堆中是否为空
        bool isEmpty(){
            return count == 0;
        }
    
        // 向最大索引堆中插入一个新的元素, 新元素的索引为i, 元素为item
        // 传入的i对用户而言,是从0索引的
        void insert(int i, Item item){
            assert( count + 1 <= capacity );
            assert( i + 1 >= 1 && i + 1 <= capacity );
    
            // 再插入一个新元素前,还需要保证索引i所在的位置是没有元素的。
            assert( !contain(i) );
    
            i += 1;
            data[i] = item;
            indexes[count+1] = i;
            reverse[i] = count+1;
            count++;
    
            shiftUp(count);
        }
    
        // 从最大索引堆中取出堆顶元素, 即索引堆中所存储的最大数据
        Item extractMax(){
            assert( count > 0 );
    
            Item ret = data[indexes[1]];
            swap( indexes[1] , indexes[count] );
            reverse[indexes[count]] = 0;
            reverse[indexes[1]] = 1;
            count--;
            shiftDown(1);
            return ret;
        }
    
        // 从最大索引堆中取出堆顶元素的索引
        int extractMaxIndex(){
            assert( count > 0 );
    
            int ret = indexes[1] - 1;
            swap( indexes[1] , indexes[count] );
            reverse[indexes[count]] = 0;
            reverse[indexes[1]] = 1;
            count--;
            shiftDown(1);
            return ret;
        }
    
        // 获取最大索引堆中的堆顶元素
        Item getMax(){
            assert( count > 0 );
            return data[indexes[1]];
        }
    
        // 获取最大索引堆中的堆顶元素的索引
        int getMaxIndex(){
            assert( count > 0 );
            return indexes[1]-1;
        }
    
        // 看索引i所在的位置是否存在元素
        bool contain( int i ){
            assert( i + 1 >= 1 && i + 1 <= capacity );
            return reverse[i+1] != 0;
        }
    
        // 获取最大索引堆中索引为i的元素
        Item getItem( int i ){
            assert( contain(i) );
            return data[i+1];
        }
    
        // 将最大索引堆中索引为i的元素修改为newItem
        void change( int i , Item newItem ){
    
            assert( contain(i) );
            i += 1;
            data[i] = newItem;
    
            // 找到indexes[j] = i, j表示data[i]在堆中的位置
            // 之后shiftUp(j), 再shiftDown(j)
    //        for( int j = 1 ; j <= count ; j ++ )
    //            if( indexes[j] == i ){
    //                shiftUp(j);
    //                shiftDown(j);
    //                return;
    //            }
    
            // 有了 reverse 之后,
            // 我们可以非常简单的通过reverse直接定位索引i在indexes中的位置
            shiftUp( reverse[i] );
            shiftDown( reverse[i] );
        }
    };
    

    堆排序

    #include <iostream>
    #include <algorithm>
    
    // 优化的shiftDown过程, 使用赋值的方式取代不断的swap,
    // 该优化思想和我们之前对插入排序进行优化的思路是一致的
    template<typename T>
    void __shiftDown(T arr[], int n, int k){
    
        T e = arr[k];
        while( 2*k+1 < n ){
            int j = 2*k+1;
            if( j+1 < n && arr[j+1] > arr[j] )
                j += 1;
    
            if( e >= arr[j] ) break;
    
            arr[k] = arr[j];
            k = j;
        }
    
        arr[k] = e;
    }
    
    // 不使用一个额外的最大堆, 直接在原数组上进行原地的堆排序
    template<typename T>
    void heapSort(T arr[], int n){
    
        // 注意,此时我们的堆是从0开始索引的
        // 从(最后一个元素的索引-1)/2开始
        // 最后一个元素的索引 = n-1
        for( int i = (n-1-1)/2 ; i >= 0 ; i -- )
            __shiftDown2(arr, n, i);
    
        for( int i = n-1; i > 0 ; i-- ){
            swap( arr[0] , arr[i] );
            __shiftDown(arr, i, 0);
        }
    }
    

    二分搜索树(Binary-Search-Tree)


    什么是二分搜索树

    二分搜索树具有以下特点

    • 依然是一棵二叉树
    • 每个结点大与左孩子
    • 每个结点大于右孩子
    • 以左右孩子为根的子树仍然是二分搜索树
    • 不存在相同的结点
    • 不一定是完全二叉树
    • 用 Node 结点来表示

    二分搜索树的一些基本操作

    • 创建
    • 删除
    • 结点个数
    • 插入
    • 判断是否存在一个元素
    • 前序遍历
    • 中序遍历
    • 后序遍历
    • 删除最大值
    • 删除最小值
    • 删除指定值
    #include <iostream>
    #include <queue>
    #include <cassert>
    
    using namespace std;
    
    // 二分搜索树
    template <typename Key, typename Value>
    class BST{
    
    private:
        // 树中的节点为私有的结构体, 外界不需要了解二分搜索树节点的具体实现
        struct Node{
            Key key;
            Value value;
            Node *left;
            Node *right;
    
            Node(Key key, Value value){
                this->key = key;
                this->value = value;
                this->left = this->right = NULL;
            }
    
            Node(Node *node){
                this->key = node->key;
                this->value = node->value;
                this->left = node->left;
                this->right = node->right;
            }
        };
    
        Node *root; // 根节点
        int count;  // 树中的节点个数
    
    public:
        // 构造函数, 默认构造一棵空二分搜索树
        BST(){
            root = NULL;
            count = 0;
        }
    
        // 析构函数, 释放二分搜索树的所有空间
        ~BST(){
            destroy( root );
        }
    
        // 返回二分搜索树的节点个数
        int size(){
            return count;
        }
    
        // 返回二分搜索树是否为空
        bool isEmpty(){
            return count == 0;
        }
    
        // 向二分搜索树中插入一个新的(key, value)数据对
        void insert(Key key, Value value){
            root = insert(root, key, value);
        }
    
        // 查看二分搜索树中是否存在键key
        bool contain(Key key){
            return contain(root, key);
        }
    
        // 在二分搜索树中搜索键key所对应的值。如果这个值不存在, 则返回NULL
        Value* search(Key key){
            return search( root , key );
        }
    
        // 二分搜索树的前序遍历
        void preOrder(){
            preOrder(root);
        }
    
        // 二分搜索树的中序遍历
        void inOrder(){
            inOrder(root);
        }
    
        // 二分搜索树的后序遍历
        void postOrder(){
            postOrder(root);
        }
    
        // 二分搜索树的层序遍历
        void levelOrder(){
    
            queue<Node*> q;
            q.push(root);
            while( !q.empty() ){
    
                Node *node = q.front();
                q.pop();
    
                cout<<node->key<<endl;
    
                if( node->left )
                    q.push( node->left );
                if( node->right )
                    q.push( node->right );
            }
        }
    
        // 寻找二分搜索树的最小的键值
        Key minimum(){
            assert( count != 0 );
            Node* minNode = minimum( root );
            return minNode->key;
        }
    
        // 寻找二分搜索树的最大的键值
        Key maximum(){
            assert( count != 0 );
            Node* maxNode = maximum(root);
            return maxNode->key;
        }
    
        // 从二分搜索树中删除最小值所在节点
        void removeMin(){
            if( root )
                root = removeMin( root );
        }
    
        // 从二分搜索树中删除最大值所在节点
        void removeMax(){
            if( root )
                root = removeMax( root );
        }
    
        // 从二分搜索树中删除键值为key的节点
        void remove(Key key){
            root = remove(root, key);
        }
    
    private:
        // 向以node为根的二分搜索树中, 插入节点(key, value), 使用递归算法
        // 返回插入新节点后的二分搜索树的根
        Node* insert(Node *node, Key key, Value value){
    
            if( node == NULL ){
                count ++;
                return new Node(key, value);
            }
    
            if( key == node->key )
                node->value = value;
            else if( key < node->key )
                node->left = insert( node->left , key, value);
            else    // key > node->key
                node->right = insert( node->right, key, value);
    
            return node;
        }
    
        // 查看以node为根的二分搜索树中是否包含键值为key的节点, 使用递归算法
        bool contain(Node* node, Key key){
    
            if( node == NULL )
                return false;
    
            if( key == node->key )
                return true;
            else if( key < node->key )
                return contain( node->left , key );
            else // key > node->key
                return contain( node->right , key );
        }
    
        // 在以node为根的二分搜索树中查找key所对应的value, 递归算法
        // 若value不存在, 则返回NULL
        Value* search(Node* node, Key key){
    
            if( node == NULL )
                return NULL;
    
            if( key == node->key )
                return &(node->value);
            else if( key < node->key )
                return search( node->left , key );
            else // key > node->key
                return search( node->right, key );
        }
    
        // 对以node为根的二分搜索树进行前序遍历, 递归算法
        void preOrder(Node* node){
    
            if( node != NULL ){
                cout<<node->key<<endl;
                preOrder(node->left);
                preOrder(node->right);
            }
        }
    
        // 对以node为根的二分搜索树进行中序遍历, 递归算法
        void inOrder(Node* node){
    
            if( node != NULL ){
                inOrder(node->left);
                cout<<node->key<<endl;
                inOrder(node->right);
            }
        }
    
        // 对以node为根的二分搜索树进行后序遍历, 递归算法
        void postOrder(Node* node){
    
            if( node != NULL ){
                postOrder(node->left);
                postOrder(node->right);
                cout<<node->key<<endl;
            }
        }
    
        // 释放以node为根的二分搜索树的所有节点
        // 采用后续遍历的递归算法
        void destroy(Node* node){
    
            if( node != NULL ){
                destroy( node->left );
                destroy( node->right );
    
                delete node;
                count --;
            }
        }
    
        // 返回以node为根的二分搜索树的最小键值所在的节点, 递归算法
        Node* minimum(Node* node){
            if( node->left == NULL )
                return node;
    
            return minimum(node->left);
        }
    
        // 返回以node为根的二分搜索树的最大键值所在的节点, 递归算法
        Node* maximum(Node* node){
            if( node->right == NULL )
                return node;
    
            return maximum(node->right);
        }
    
        // 删除掉以node为根的二分搜索树中的最小节点, 递归算法
        // 返回删除节点后新的二分搜索树的根
        Node* removeMin(Node* node){
    
            if( node->left == NULL ){
    
                Node* rightNode = node->right;
                delete node;
                count --;
                return rightNode;
            }
    
            node->left = removeMin(node->left);
            return node;
        }
    
        // 删除掉以node为根的二分搜索树中的最大节点, 递归算法
        // 返回删除节点后新的二分搜索树的根
        Node* removeMax(Node* node){
    
            if( node->right == NULL ){
    
                Node* leftNode = node->left;
                delete node;
                count --;
                return leftNode;
            }
    
            node->right = removeMax(node->right);
            return node;
        }
    
        // 删除掉以node为根的二分搜索树中键值为key的节点, 递归算法
        // 返回删除节点后新的二分搜索树的根
        Node* remove(Node* node, Key key){
    
            if( node == NULL )
                return NULL;
    
            if( key < node->key ){
                node->left = remove( node->left , key );
                return node;
            }
            else if( key > node->key ){
                node->right = remove( node->right, key );
                return node;
            }
            else{   // key == node->key
    
                if( node->left == NULL ){
                    Node *rightNode = node->right;
                    delete node;
                    count --;
                    return rightNode;
                }
    
                if( node->right == NULL ){
                    Node *leftNode = node->left;
                    delete node;
                    count--;
                    return leftNode;
                }
    
                // node->left != NULL && node->right != NULL
                Node *successor = new Node(minimum(node->right));
                count ++;
    
                successor->right = removeMin(node->right);
                successor->left = node->left;
    
                delete node;
                count --;
    
                return successor;
            }
        }
    };
    

    四叉树(Quad-Tree)


    什么是四叉树

    参考博客:四叉树空间索引原理及其实现

    四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间,如此递归下去,直至树的层次达到一定深度或者满足某种要求后停止分割。

    四叉树的结构比较简单,并且当空间数据对象分布比较均匀时,具有比较高的空间数据插入和查询效率,因此四叉树是GIS中常用的空间索引之一。

    常规四叉树的结构如图所示,地理空间对象都存储在叶子节点上,中间节点以及根节点不存储地理空间对象。

    在这里插入图片描述

    四叉树的一些应用

    参考博客:一个四叉树的简单实现

    参考博客:四叉树Quadtrees在游戏领域应用

    八叉树(Octree)


    参考博客:八叉树(Octree)

    参考博客:八叉树

    参考博客:八叉树及K-D树的应用和实现

    参考博客:图像量化法——八叉树算法

    kd 树(Kd-Tree)


    参考博客:Kd-Tree算法原理简析

    参考博客:KDTree

    参考博客:KD tree

    参考博客:详解 KDTree

    红黑树(Red-Black-Tree)


    参考博客:红黑树(一)之 原理和算法详细介绍

    参考博客:红黑树(二)之 C语言的实现

    参考博客:红黑树(三)之 Linux内核中红黑树的经典实现

    参考博客:红黑树(四)之 C++的实现

    参考博客:红黑树(六)之 参考资料

    哈夫曼树(Huffman-Tree)


    定义

    具有最小带权路径长度的二叉树称为哈夫曼树。

    参考博客:哈夫曼树

    参考博客:哈夫曼树与哈夫曼编码

    参考博客:哈夫曼树

    参考博客:哈夫曼树

    展开全文
  • js树结构转数组 扁平化 树结构平铺

    tree数据扁平化

    /**
    * tree数据扁平化
    * 添加深度
    * 添加父级节点(不能添加,只能使用父节点ID,添加echart会爆栈)
    */
    flatTree(data, treeMap = [], depth = 0) {
     if (!(data && data.length)) return;
     depth++;
     return data.reduce((acc, cur) => {
       cur.depth = depth;
       acc.push(cur);
       if (cur.children && cur.children.length) {
         this.flatTree(cur.children, treeMap, depth);
       }
       return acc;
     }, treeMap);
    }
    

    tree 铺平方法

    // tree 铺平方法
    const getNodeMap = (node, parentNode) => {
      node.parentNode = parentNode;
      const nodeMap = [node];
      if (node.children && node.children.length) {
        node.children.forEach(item => nodeMap.push(...getNodeMap(item, node)));
      }
      return nodeMap;
    };
    
    export const getTreeMap = tree => {
      if (!(tree instanceof Array)) return;
      const treeMap = [];
      tree.forEach(node => {
        treeMap.push(...getNodeMap(node, tree));
      });
      return treeMap;
    };
    

    获取树结构下某个字段的集合

    const getProvilegeCode = data => {
      return data.reduce((acc, { resourceCode, children }) => {
        acc.push(resourceCode);
        if (children && children.length) acc.push(...getProvilegeCode(children));
        return acc;
      }, []);
    };
    const mutations = {
      updatePrivilege(state, data) {
        if (!(data.privilegeList && data.privilegeList.length)) return;
        state.privilegeCode = getProvilegeCode(data.privilegeList);
      }
    };
    

    倒序数据

    let list = [];
    for (let i = 0; i < chartsDaLi.length; i += 1) {
    	list[i] = chartsDaLi[chartsDaLi.length - i - 1];
    }
    
    展开全文
  • 树结构概述

    千次阅读 2020-04-06 10:26:50
    文章目录什么是树结构?简介为什么要使用树结构?树的基本概念根节点双亲节点路径节点的度节点的权叶子节点子树层树的高度森林 什么是树结构? 树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为...
  • MySQL 查询 树结构

    万次阅读 2019-06-28 16:25:15
    1. 关于树结构 此类结构的数据,通常需要表结构中含有id 、parentId等自关联字段,有时为了提高查询效率还可增加更多冗余字段,如index,index的值为所有父级目录的id字符串集合。 关于树结构数据的组装,常见的...
  • redis存储树结构数据

    千次阅读 2019-10-03 08:00:51
    本文主要讲解两方面内容:1.redis如何存储树结构数据。2.java操作redis时选取哪种序列化器。 redis如何存储树结构数据 先抛出结论,树结构数据在redis中的存储顺序如下: ...
  • DOM树结构

    千次阅读 2017-11-12 11:26:49
    DOM树结构 1.所谓的DOM操作,操作是什么? 操作的是DOM树,进行增删改查。 (jq操作选择器获得节点) 2. 一般DOM树结构 父节点 兄弟节点 当前节点 属性节点 子节点 兄弟节点 3.绘制DOM树:childNodes,...
  • go语言菜单树结构

    千次阅读 2018-07-26 11:29:08
    GO语言菜单树结构实现,Menu是数据库表映射。MenuTree是树结构菜单,目前只考虑2级菜单。后面附源码,亲测可用 package models import ( "github.com/astaxie/beego/orm" "time" ) ...
  • 使用递归方式过滤树结构

    千次阅读 2018-11-10 22:09:04
    使用递归方式过滤树结构 本文介绍使用递归方法过滤树数据结构。 需求 给定叶子节点,过滤树。下面通过示例说明。 示例数据结构: 0 / | \ 1 2 3 / \ | / \ 4 5 6 7 8 给定条件为:4 和 6,如果所有...
  • 树结构的应用之基于树的索引结构介绍 转眼又七月份了。6月份后来就变成考试月了。因为图论要求写阅读报告,某天看数据库的空间索引时,又正好看到关于基于树的一些索引技术,于是产生了以此为主题写份阅读报告的...
  • JS递归遍历树结构

    千次阅读 2020-03-19 16:26:00
    JS递归遍历树结构上代码 上代码 // 树结构 const options = [ { value: 'zhejiang', label: 'Zhejiang', children: [ { value: 'hangzhou', label: 'Hangzhou', children: [ ...
  • MySQL 查询树结构

    千次阅读 2018-12-21 16:25:08
    MySQL 查询树结构 在 oracle 数据库中,通过 start with connect by prior 递归可以直接查出树结构,但是在 mysql 当中如何解决树查询问题呢? 思路: 我们可以通过自定义函数,遍历找出某一节点的所有子节点 (或者...
  • 扁平化数据转化为树结构

    千次阅读 2021-04-14 10:31:06
    扁平化数据转化为树结构 function toTree({arrayList, pidStr = 'pid', idStr = 'id', childrenStr = 'children'}) { let listOjb = {}; // 用来储存{key: obj}格式的对象 let treeList = []; // 用来储存最终树形...
  • NLP中的树结构

    千次阅读 2017-08-26 14:07:24
    NLP中的树结构树结构的分类
  • * 向树结构中添加数据 * * @param object elements 元素信息 * ps: elements 是元素的element类整个对象 * * @returns bool */ setChildren (elements) { let isOk = false let catalog = this.elem...
  • js数组和树结构数据相互转换

    万次阅读 多人点赞 2019-07-10 17:06:04
    数组转树结构采取递归和非递归两种方式,树结构转扁平化数组采取深度优先遍历(递归和非递归两种方式)和广度优先遍历实现。 let arr =[ {id:2,name:'部门B',parentId:0}, {id:3,name:'部门C',parentId:1}, {id:1...
  • Python 实现树结构

    万次阅读 多人点赞 2018-03-23 16:57:36
    自然界中的和计算机科学中的之间的区别在于数据结构的根在顶部,其叶在底部。 1 的相关定义 节点:的基本部分。它可以有一个名称,我们称之为“键”。节点也可以有附加信息。我们将这个附加信息称为...
  • 最近编译原理学到语法分析树,需要频繁、大量地画树结构,一开始我使用了画图、PPT等工具,或是在纸上画好然后拍下来,但很是麻烦。 经同学推荐,找到了这样一个树的自动生成工具:Syntax Tree Generator。它的使用...
  • 因项目需求,需修改tree树结构的图标,以及树形的字体样式等; 代码如下: <template> <div class="FormMaintain"> <el-tree :data="data" :props="defaultProps" @node-click="handleNodeClick...
  • 树结构工具-TreeUtil(注解的方式实现) 将有树结构的集合封装为树结构 使用步骤: 1. 添加依赖 <dependency> <groupId>com.github.appundefined</groupId> <artifactId>treeUtils</...
  • 需求:将具备树结构的线性表遍历出来,得到树形结构的对象 解决思路: 要不查询整条记录,要不查询具备树结构的部分数据。再通过具备树结构的部分数据,将整条记录封装到对象中 怎么查询具备树结构的部分数据 首先...
  • 最近项目用到了菜单树,想想菜单树等树结构在实际中应用还是挺广的,所以分析总结下。除了菜单树,还有权限树,商品分类列表也是树结构。 实际应用中的树结构树结构分析要说树结构中最具美感的应该是二叉树了,但是...
  • 树结构性质简介

    千次阅读 2013-03-05 16:24:33
    不过我们平常用树结构时都是树的倒序结构,就是根在上,分支和叶子在下面.这符合我们从简单到复杂,从少到多的习惯性认知思维. 我们平常看到的书的目录是树结构,windows上文件系统是以树形结构展示的.面向对...
  • react-native实现树结构选择组件

    千次阅读 热门讨论 2018-06-18 02:39:26
    react-native-tree-select,树结构选择组件 项目结构 --components: treeSelect组件 --treeSelectExample: 组件演示代码 --.gitignore:git忽略文件 --README.md:说明文档 Example usage: 1.基本用法 ...
  • python 实现树结构的七种遍历

    千次阅读 2018-06-03 07:58:21
    很好的复习树结构知识 python 实现树结构的七种遍历
  • 树结构相关术语 节点Node:组成树的基本部分 每个节点具有名称,或“键值”,节点还可以保存额外数据项,数据项根据不同的应用而变 边Edge:边是组成树的另一个基本部分 每条边恰好连接两个节点,表示节点之间具有...
  • 递归遍历树结构-已解决

    千次阅读 2017-08-28 11:58:19
    在项目中用到导航树结构,所以就用递归写了一个遍历导航树的功能。 表结构: /** * 递归获取菜单 * * @param roleKey * @param systemCode * @return */ public String getSysMenuJson(String ...
  • linux 查看文件树结构

    千次阅读 2018-09-14 08:56:33
    在linux下使用tree命令可以方便的查看指定目录下的文件树结构,但有些系统并未安装该命令,需要手动安装一下,下面以在Ubuntu的安装为例,其他linux系统类似。 在ubuntu下安装: 在接网络的情况下,在命令行中输入...
  • C++树结构

    千次阅读 2017-07-27 22:08:57
    树树是什么在计算机科学中,(英语:tree)是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 901,671
精华内容 360,668
关键字:

树的结构