TypeScript 实战算法系列(十四):实现二叉搜索树

Easter79
• 阅读 151

TypeScript 实战算法系列(十四):实现二叉搜索树

本文由图雀社区认证作者 神奇的程序员 写作而成,图雀社区将连载其TypeScript 实战算法系列,点击阅读原文查看作者的掘金链接,感谢作者的优质输出,让我们的技术世界变得更加美好😆

前言

树是一种非顺序数据结构,它用于存储需要快速查找的数据。现实生活中也有许多用到树的例子,比如:家谱、公司的组织架构图等。

本文将详解二叉搜索树并用TypeScript将其实现,欢迎各位感兴趣的开发者阅读本文。

实现思路

二叉树中的节点最多只能有两个子节点:一个是左侧子节点, 另一个是右侧子节点。

二叉搜索树是二叉树的一种,它与二叉树的不同之处:

  • 每个节点的左子节点一定比自身小

  • 每个节点的右子节点一定比自身大

本文主要讲解树的具体实现,不了解树基础知识的开发者请移步: 数据结构: 二叉查找树

二叉搜索树的实现

根据二叉搜索树的特点我们可知: 每个节点都有2个子节点,左子节点一定小于父节点,右子节点一定大于父节点。

创建辅助类Node

首先,我们需要一个类来描述二叉树中的每个节点。由二叉树的特点可知,我们创建的类必须包含如下属性:

  • key   节点值

  • left   左子节点的引用

  • right  右子节点的引用

和链表一样,我们将通过指针来表示节点之间的关系,在双向链表中每个节点包含两个指针, 一个指向下一个节点,两一个指向上一个节点。树也采用同样的方式(使用两个指针), 但是树的指针一个指向左子节点,另一个指向右子节点。

下图描述了一个二叉树, 节点与节点之间的链接就是指针。TypeScript 实战算法系列(十四):实现二叉搜索树

创建二叉搜索树的基本结构

我们采用与链表相同的做法,通过声明一个变量来控制此数据结构的第一个节点(根节点), 在树中此节点为root。

接下来,我们来分析下实现一个二叉搜索树都需要实现的方法:

  • insert(key): 向树中插入一个节点

  • search(key): 在树中查找一个键。如果节点存在返回true, 否则返回false

  • min(): 返回树中最小的值 / 键

  • max(): 返回书中最大的值 / 键

  • remove(key): 从树中移除某个键

向树中插入一个新的节点
  • 验证插入操作是否为特殊情况: 根节点为null, 如果根节点为null则创建一个Node类的实例并将其赋值给root属性,将root指向新创建的节点

  • 如果根节点不为null, 则需要寻找合适的位置来插入子节点, 因此我们需要实现一个辅助方法 insertNode

  • insertNode方法接收两个参数: 要从哪里开始插,要插入节点的key

  • 由于二叉搜索树有一个特点是: 左子节点小于父节点, 右字节点大于父节点。所以我们需要创建一个比对方法 compareFn

  • compareFn方法接收两个参数: 要比对的值,原值。如果小于则返回-1, 如果大于则返回1, 相等则返回0

  • 调用compareFn方法判断要插入的键是否小于当前节点的键

  • 如果小于, 判断当前节点的左子节点是否为null, 如果为null则创建Node节点将其指向左子节点, 否则从当前节点的左子节点位置开始递归调用insertNode方法,寻找合适的位置

  • 如果大于, 判断当前节点的右子节点是否为null, 如果为null则创建Node节点将其指向右子节点,否则从当前节点的右子节点位置开始递归调用 insertNode方法, 寻找合适的位置

接下来,我们通过一个例子来描述下上述过程。

我们要将下述数据插入二叉树中:30 21 25 18 17 35 33 31

  • 首先,插入30,此时根节点为null,创建一个Node节点将其指向root TypeScript 实战算法系列(十四):实现二叉搜索树

  • 然后,插入21,此时比较21和30的大小,21 < 30。在30的左子节点插入, 30的左子节点为null。因此直接插入 TypeScript 实战算法系列(十四):实现二叉搜索树

  • 然后,插入25 < 30,在30的左子节点插入,此时30的左子节点已经有了21,递归调用insertNode,比较25和21的大小,25 > 21,因此在21的右子节点插入 TypeScript 实战算法系列(十四):实现二叉搜索树

  • 依此类推,直至所有节点都插入。 TypeScript 实战算法系列(十四):实现二叉搜索树

搜索树中的值

在树中,有三种经常执行的搜索类型:

  • 搜索最小值

  • 上个例子,我们将所有的节点插入到二叉树后,我们发现树最左侧的节点是这颗树中最小的键

  • 因此我们只需要从根节点一直沿着它的左子树往下找就可以找到最小节点了

  • 搜索最大值

  • 树最右侧的节点是这颗树中最大的键

  • 因此我们只需要从根节点一直沿着它的右子树往下找就可以找到最大节点了

  • 搜索特定的值

  • 首先声明一个方法search, search方法接收一个参数:要查找的键,它需要一个辅助方法searchNode

  • searchNode接收两个参数:要查找的节点,要查找的键,它可以用来查找一棵树或其任意子树的一个特定的值

  • 首先需要验证参数传入的节点是否合法(不是null或undefined), 如果是说明要找的键没找到,返回false

  • 调用compareFn方法比对要查找节点与当前节点的key进行大小比较

  • 如果要查找的节点小于当前节点的key,则递归调用searchNode方法,传当前节点的左子节点和要查找的key

  • 如果要查找的节点大于当前节点的key,则递归调用searchNode方法,传当前节点的右子节点和要抄着的key

  • 否则就是相等,则节点已找到,返回true

接下来,我们通过一个例子来描述下搜索特定的值的过程。

如下图所示为一个二叉搜索树,我们需要判断25是否在树中:

TypeScript 实战算法系列(十四):实现二叉搜索树

  • 调用search方法,要查找的键为25,调用searchNode方法,需要从根节点开始找,因此传root和要查找的key

  • 首先,node不为空,则继续判断key与根节点键的大小,25 < 30,递归它的左子树 TypeScript 实战算法系列(十四):实现二叉搜索树

  • 然后,比较25和21的大小,25 > 21,递归它的右子树 TypeScript 实战算法系列(十四):实现二叉搜索树

  • 此时,25 === 21,节点已找到,返回true

移除一个节点

移除树中的节点remove,它接收一个参数key,它需要一个辅助方法removeNode,它接收两个参数:节点,要移除的key。

removeNode实现思路如下:

  • 首先,判断节点是否为null,如果是则证明节点不存在返回null

  • 调用compareFn方法,比较要删除的key与当前节点key的大小

  • 如果要删除的key小于当前节点key,则递归调用removeNode方法,传当前节点的左子节点和key

  • 如果要删除的key大于当前节点key,则递归调用removeNode方法,传当前节点的右子节点和key

  • 否则就是找到了要删除的节点,删除节点可能出现三种情况:

  • 需要先找到它右边子树的最小节点

  • 用右子树最小节点的键去更新当前节点的键

  • 更新完成后,此时树中存在了多余的键,需要调用removeNode方法将其删除

  • 向其父节点更新节点的引用

  • 当前节点的左子节点和右子节点都为null,此时我们只需要将节点指向null来移除它 TypeScript 实战算法系列(十四):实现二叉搜索树

  • 当前节点包含一个左子节点或者右子节点,如果左子节点为null,将当前节点指向当前节点的右子节点。如果右子节点为null,将当前节点指向当前节点的左子节点。 TypeScript 实战算法系列(十四):实现二叉搜索树

  • 当前节点有两个子节点,需要执行4个步骤:

二叉搜索树的遍历

遍历一棵树是指访问树的每个节点并对它们进行某种操作的过程,访问树的所有节点有三种方式:

  • 中序遍历

  • 先序遍历

  • 后序遍历

树的遍历采用递归的形式访问,对递归不了解的开发者请移步:递归的理解与实现

中序遍历

中序遍历是一种上行顺序访问树节点的遍历方式,即从小到大的顺序访问所有节点。中序遍历的一种应用场景就是对树进行排序操作,接下来我们来分析下中序遍历的实现:

  • 声明inOrderTraverse方法接收一个回调函数作为参数,回调函数用来定义我们对遍历到的每个节点进行的操作,中序遍历采用递归实现,因此我们需要一个辅助方法inOrderTraverseNode

  • inOrderTraverseNode方法接收两个参数:节点,回调函数

  • 递归的基线条件node==null

  • 递归调用inOrderTraverseNode方法,传当前节点的左子节点和回调函数

  • 调用回调函数

  • 递归调用inOrderTraverseNode方法,传当前节点的右子节点和回调函数

接下来,我们通过一个例子来描述下中序遍历的过程TypeScript 实战算法系列(十四):实现二叉搜索树

如上图所示,蓝色字标明了节点的访问顺序,橙色线条表示递归调用直至节点为null然后执行回调函数。具体的执行过程如下:

11=>7=>5=>3 ode:3,     left:undefined     callback(node.key)  3     right:undefined     allback(node.key)   5 node:5,     right:6     left:undefined     callback(node.key)  6     right: undefined     callback(node.key)  7 node:7,     right:9     left:8     left:undefined     callback(node.key)  8     right:undefined     callback(node.key)  9     right:10     left:undefined     callback(node.key)  10     right:undefined     allback(node.key)   11 node:11,     right:15     left:13     left:12     left:undefined     callback(node.key)  12     right:undefined     callback(node.key)  13     right:14     left:undefined     callback(node.key)  14     right:undefined     ......             ...     right:25     left:undefined      25     callback(node.key)

先序遍历

先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档,接下来我们分析下先序遍历的具体实现:

  • 声明preOrderTraverse方法,接收的参数与中序遍历一样,它也需要一个辅助方法preOrderTraverseNode

  • preOrderTraverseNode方法接收的参数与中序遍历一样

  • 递归的基线条件: node == null

  • 调用回调函数

  • 递归调用preOrderTraverseNode方法,传当前节点的左子节点和回调函数

  • 递归调用preOrderTraverseNode方法,传当前节点的右子节点和回调函数

接下来,我们通过一个例子来描述下先序遍历的过程:TypeScript 实战算法系列(十四):实现二叉搜索树 如上图所示,蓝色字标明了节点的访问顺序,橙色线表示递归调用直至节点为null然后执行回调函数。

具体的执行过程如下:

node:11     callback(node.key)   11     node.left=7 ode:7     callback(node.key)   7     node.left=5 ode:5     callback(node.key)   5     ode.left=3 node:3     callback(node.key)   3     node.left=undefined,node.right=undefined => node:5 node:5     node.right = 6     callback(node.key)   6 node:6     node.left=undefined,node.right=undefined => node:7 node:7     node.right = 9     callback(node.key)   9 ......                 ...     callback(node.key)   25

后序遍历

后序遍历则是先访问节点的后代节点,再访问节点本身。后序遍历的一种应用是计算一个目录及其子目录中所有文件所占空间的大小,接下来我们来分析下后序遍历的实现:

  • 声明postOrderTraverse方法,接收的参数与中序遍历一致

  • 声明postOrderTraverseNode方法,接收的参数与中序遍历一致

  • 递归的基线条件为node == null

  • 递归调用postOrderTraverseNode方法,传当前节点的左子节点和回调函数

  • 递归调用postOrderTraverseNode方法,传当前节点的右子节点和回调函数

  • 调用回调函数

接下来,我们通过一个例子来描述下后序遍历的执行过程。TypeScript 实战算法系列(十四):实现二叉搜索树

如上图所示,蓝色字标示了节点的执行顺序,橙色线表示递归调用直至节点为null然后执行回调函数。

具体的执行过程如下:

11=>7=>5=>3 node:3     left:undefined     right:undefined     callback(node.key)  3 node:5     right:6 ode:6     left:undefined     right:undefined     callback(node.key)  6 node:5     callback(node.key)  5 node:7     right: 9 node:9     left:8 node:8     left:undefined     right:undefined     callback(node.key)  8 node:9     right:10 node:10     left:undefined     right:undefined     callback(node.key)  10 node:9     callback(node.key)  9 node:7     callback(node.key)  7 ...                   ...     callback(node.key)  11

实现代码

前面我们分析了二叉搜索树的实现思路,接下来我们就讲上述思路转换为代码。

创建辅助节点

  • 创建Node.ts文件

  • 创建Node类,根据节点的属性为类添加对应属性

``export class Node {
    public left: Node | undefined;
    public right: Node | undefined;
    constructor(public key: K) {
        this.left = undefined;
        this.right = undefined;
    }

    toString() {
        return ${this.key};
    }
}
``

完整代码请移步: Node.ts

创建二叉树的基本结构

  • 创建BinarySearchTree.ts文件

  • 声明root节点和比对函数

`protected root: Node | undefined;

constructor(protected compareFn: ICompareFunction = defaultCompare) {
    this.root = undefined;
};
`

`export type ICompareFunction = (a: T, b: T) => number;

export function defaultCompare(a:T, b:T) {
    if (a === b){
        return Compare.EQUALS;
    }else if(a > b) {
        return Compare.BIGGER_THAN;
    }else {
        return Compare.LESS_THAN;
    }
}
`

  • 实现节点插入

`insert(key: T){
    if (this.root == null){
        // 如果根节点不存在则直接新建一个节点
        this.root = new Node(key);
    }else {
        // 在根节点中找合适的位置插入子节点
        this.insertNode(this.root,key);
    }
}

protected insertNode(node: Node, key: T) {
    // 新节点的键小于当前节点的键,则将新节点插入当前节点的左边
    // 新节点的键大于当前节点的键,则将新节点插入当前节点的右边
    if (this.compareFn(key,node.key) === Compare.LESS_THAN){
        if (node.left == null){
            // 当前节点的左子树为null直接插入
            node.left = new Node(key);
        }else {
            // 从当前节点(左子树)向下递归,找到null位置将其插入
            this.insertNode(node.left,key);
        }
    }else{
        if (node.right == null){
            // 当前节点的右子树为null直接插入
            node.right = new Node(key);
        }else {
            // 从当前节点(右子树)向下递归,找到null位置将其插入
            this.insertNode(node.right,key);
        }
    }
}
`

  • 获取节点的最大值、最小值以及特定节点

`// 搜索特定节点的值
search(key: T){
    return this.searchNode(<Node>this.root, key);
}

private searchNode(node: Node, key: T): boolean | Node{
   if (node == null){
       return false;
   }

   if (this.compareFn(key, node.key) === Compare.LESS_THAN){
       // 要查找的key在节点的左侧
       return this.searchNode(<Node>node.left, key);
   } else if(this.compareFn(key, node.key) === Compare.BIGGER_THAN){
       // 要查找的key在节点的右侧
       return this.searchNode(<Node>node.right, key);
   } else{
       // 节点已找到
       return true;
   }
}

// 获取树的最小节点
min(){
    return this.minNode(<Node>this.root);
}

protected minNode(node: Node): Node{
    let current = node;
    while (current != null && current.left != null){
        current = current.left;
    }
    return current;
}

// 获取树的最大节点
max(){
    return this.maxNode(<Node>this.root);
}

private maxNode(node: Node){
    let current = node;
    while (current != null && current.right != null){
        current = current.right;
    }
    return current;
}
`

  • 实现节点移除

`remove(key: T){
    this.removeNode(<Node>this.root,key);
}

protected removeNode(node: Node | null, key: T){
    // 正在检测的节点为null,即键不存在于树中
    if (node == null){
        return null;
    }

    // 不为null,需要在树中找到要移除的键
    if (this.compareFn(key,node.key) === Compare.LESS_THAN){ // 目标key小于当前节点的值则沿着树的左边找
        node.left = <Node>this.removeNode(<Node>node.left, key);
        return node;
    } else if (this.compareFn(key,node.key) === Compare.BIGGER_THAN){ // 目标key大于当前节点的值则沿着树的右边找
        node.right = <Node>this.removeNode(<Node>node.right, key);
        return node;
    } else{
        // 键等于key,需要处理三种情况
        if (node.left == null && node.right == null){ // 移除一个叶节点,即该节点没有左、右子节点
            // 将节点指向null来移除它
            node = null;
            return node;
        }

        if (node.left == null){ // 移除一个左侧子节点的节点
            // node有一个右侧子节点,因此需要把对它的引用改为对它右侧子节点的引用
            node = <Node>node.right;
            // 返回更新后的节点
            return node;
        } else if(node.right == null){ // 移除一个右侧子节点的节点
            // node有一个左侧子节点,因此需要把对它的引用改为对它左侧子节点的引用
            node = node.left;
            // 返回更新后的节点
            return node;
        }

        // 移除有两个子节点的节点
        const aux = this.minNode(node.right); // 当找到了要移除的节点后,需要找到它右边子树最小的节点,即它的继承者
        node.key = aux.key; // 用右侧子树最小的节点的键去更新node的键
        // 更新完node的键后,树中存在了两个相同的键,因此需要移除多余的键
        node.right = <Node>this.removeNode(node.right, aux.key) // 移除右侧子树中的最小节点
        return node; // 返回更新后的节点
    }
}
`

二叉树的遍历

接下来我们实现中序、先序、后序遍历

  • 实现中序遍历

`inOrderTraverse(callback: Function){
    this.inOrderTraverseNode(<Node>this.root,callback);
}

private inOrderTraverseNode(node: Node,callback: Function){
    if (node !=null){
        this.inOrderTraverseNode(<Node>node.left,callback);
        callback(node.key);
        this.inOrderTraverseNode(<Node>node.right,callback);
    }
}
`

  • 实现先序遍历

`preOrderTraverse(callback: Function){
    this.preOrderTraverseNode(<Node>this.root, callback);
}

private preOrderTraverseNode(node: Node, callback: Function){
    if (node != null){
        callback(node.key);
        this.preOrderTraverseNode(<Node>node.left, callback);
        this.preOrderTraverseNode(<Node>node.right, callback);
    }
}
`

  • 实现后序遍历

`postOrderTraverse(callback: Function){
    this.postOrderTraverseNode(<Node>this.root, callback);
}

private postOrderTraverseNode(node: Node, callback: Function) {
    if (node != null){
        this.postOrderTraverseNode(<Node>node.left, callback);
        this.postOrderTraverseNode(<Node>node.right, callback);
        callback(node.key);
    }
}
`

完整代码请移步: BinarySearchTree.ts

编写测试代码

前面我们实现了二叉搜索树以及它的基本方法,接下来我们来测试下上述代码是否都能正常执行。

const binarySearchTree = new BinarySearchTree(); binarySearchTree.insert(11); binarySearchTree.insert(7); binarySearchTree.insert(15); binarySearchTree.insert(5); binarySearchTree.insert(3); binarySearchTree.insert(9); binarySearchTree.insert(8); binarySearchTree.insert(10); binarySearchTree.insert(13); binarySearchTree.insert(12); binarySearchTree.insert(14); binarySearchTree.insert(20); binarySearchTree.insert(18); binarySearchTree.insert(25); binarySearchTree.insert(6); // 测试中序遍历函数 const printNode = (value) => console.log(value); console.log("中序遍历"); binarySearchTree.inOrderTraverse(printNode); // 测试先序遍历 console.log("先序遍历"); binarySearchTree.preOrderTraverse(printNode); // 测试后序遍历 console.log("后序遍历"); binarySearchTree.postOrderTraverse(printNode); // 测试获取最小值函数 console.log("树的最小值",binarySearchTree.min()); // 测试获取最大值函数 console.log("树的最大值",binarySearchTree.max()); // 测试搜索节点函数 console.log("8在二叉树中",binarySearchTree.search(8)); console.log("100在二叉树中",binarySearchTree.search(100)); // 测试节点删除 console.log("删除节点3"); binarySearchTree.remove(3); binarySearchTree.inOrderTraverse(printNode);

完整代码请移步: BinarySearchTreeTest.js

执行结果如下:TypeScript 实战算法系列(十四):实现二叉搜索树 TypeScript 实战算法系列(十四):实现二叉搜索树 TypeScript 实战算法系列(十四):实现二叉搜索树 TypeScript 实战算法系列(十四):实现二叉搜索树

❤️爱心三连击

1.看到这里了就点个在看支持下吧,你的在看是我创作的动力。

2.关注公众号图雀社区「带你一起学优质实战技术教程」

3.特殊阶段,带好口罩,做好个人防护。

4.添加微信【little-tuture】,拉你进技术交流群一起学习。

                 ● TypeScript 实战算法系列(一):实现数组栈与对象栈 
                 ● TypeScript 实战算法系列(二):实现队列与双端队列 
                 ● TypeScript 实战算法系列(十):实现动态规划 
                 
                
               
              
             
            
           
          
         
       
   
      
      
      
  
     
     
     
 
    
    
    

   
   
   

·END·

图雀社区

汇聚精彩的免费实战教程

TypeScript 实战算法系列(十四):实现二叉搜索树

关注公众号回复 z 拉学习交流群

喜欢本文,点个“在看”告诉我

TypeScript 实战算法系列(十四):实现二叉搜索树

本文分享自微信公众号 - 图雀社区(tuture-dev)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
Jacquelyn38 Jacquelyn38
1年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Easter79 Easter79
1年前
swap空间的增减方法
(1)增大swap空间去激活swap交换区:swapoff v /dev/vg00/lvswap扩展交换lv:lvextend L 10G /dev/vg00/lvswap重新生成swap交换区:mkswap /dev/vg00/lvswap激活新生成的交换区:swapon v /dev/vg00/lvswap
Wesley13 Wesley13
1年前
Java爬虫之JSoup使用教程
title:Java爬虫之JSoup使用教程date:201812248:00:000800update:201812248:00:000800author:mecover:https://imgblog.csdnimg.cn/20181224144920712(https://www.oschin
Stella981 Stella981
1年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Wesley13 Wesley13
1年前
Java日期时间API系列36
  十二时辰,古代劳动人民把一昼夜划分成十二个时段,每一个时段叫一个时辰。二十四小时和十二时辰对照表:时辰时间24时制子时深夜11:00凌晨01:0023:0001:00丑时上午01:00上午03:0001:0003:00寅时上午03:00上午0
Wesley13 Wesley13
1年前
MySQL查询按照指定规则排序
1.按照指定(单个)字段排序selectfromtable_nameorderiddesc;2.按照指定(多个)字段排序selectfromtable_nameorderiddesc,statusdesc;3.按照指定字段和规则排序selec
Stella981 Stella981
1年前
Angular material mat
IconIconNamematiconcode_add\_comment_addcommenticon<maticonadd\_comment</maticon_attach\_file_attachfileicon<maticonattach\_file</maticon_attach\
Wesley13 Wesley13
1年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
helloworld_34035044 helloworld_34035044
6个月前
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
京东云开发者 京东云开发者
1个月前
为什么mysql不推荐使用雪花ID作为主键
作者:毛辰飞背景在mysql中设计表的时候,mysql官方推荐不要使用uuid或者不连续不重复的雪花id(long形且唯一),而是推荐连续自增的主键id,官方的推荐是auto_increment,那么为什么不建议采用uuid,使用uuid究