首页 > 其他分享 >树-BST基本实现

树-BST基本实现

时间：2024-08-12 21:04:51浏览次数：4  
标签：基本 node 遍历 log callback BST 实现 key 节点

之前的数组, 栈, 链表, 队列等都是顺序数据结构, 这里来介绍一个非顺序数据结构, 树. 树在处理有层级相关的数据时非常有用, 还有在存储数据如数据库查询实现等场景也是高频使用.

作为一种分层数据的抽象模型, 在现实中最常见的例子是族谱, 公司组织架构图等.

我个人觉得树, 图等非顺序的数据结构是不太好直观理解的, 它的实现都需要用到函数的递归. 就关于函数递归调用栈搞不清楚的话, 那也就很难理解代码了.

树的基本内容包括:

  • 树相关的术语
  • 创建二叉搜索树
  • 树的三种遍历
  • 添加和移除节点
  • AVL平衡树

树的核心术语

  • 节点: 树的每个元素都称为 "节点". 节点的祖先包括父节点, 祖父节点等; 节点的后代包括子节点, 孙节点等
  • 根节点: 一颗树顶部最上层有个唯一的根节点元素, 称为根节点
  • 内/外部节点: 至少有一个子节点的称为 "内部节点", 否则称 "外部节点 或 叶节点"
  • 边: 节点和节点之间的 "连线" 成为边, 类似链表中的指针
  • 子树: 节点和其子节点的集合, 构成一颗子树
  • 节点深度: 节点深度指其祖先节点的数量
  • 树高度: 所有节点深度的最大值

搜索二叉树

二叉树中的节点最多只能有两个子节点: 左子节点 和 右子节点.

这种只有2个路径的结构可以让我们写出更高效的数据插入, 查询, 删除节点的算法. 比如二分法, 关系型数据库的查询设计等, 就使用非常高频.

二叉搜索树 (BST) 是二叉树的一种, 强制要求:

  • 比父节点小的值, 存左侧子节点
  • 比父节点大的值, 存右侧子节点
// 节点类
class Node {
    constructor(key) {
        this.key = key     // 节点值
        this.left = null   // 左节点指针
        this.right = null  // 右节点指针
    }
}

// 二叉搜索树类
class BSTtree {
    constructor() {
        this.root = null  // 根节点对象
    }
}

主要实现的方法是有:

  • insert(key): 向树中插入一个新的键
  • search(key): 搜索 key, 如果存在返回 true, 否则返回 false
  • inOrderTraverse(): 中序遍历所有节点
  • preOrderTraverse(): 先序遍历所有节点
  • postOrderTraverse(): 后序遍历所有节点
  • min() : 返回树中最小值
  • max(): 返回树中最大值
  • remove(key): 从树中移除某个键

BST - 插入键

这里我们先来实现一个辅助的方法 insertNode(node, key) .

它的作用是帮我们找到新节点应该插入到哪个最合适的层级位置, 因此它是一个 递归函数.

**当插入的 key 小于 node.key 时: **

  • 如果 node.left 是叶子节点时, 则直接插入
  • 否则就递归往左下层子树查找

当插入的 key 大于 node 时:

  • 如果 node.right 是叶子节点时, 则直接插入
  • 否则就递归往右下层子树查找
// 从某节点开始, 插入新的 key
insertNode(node, key) {
    if (key < node.key) {
        // 左子树处理
        if (node.left == null) {
            node.left = new Node(key)
        } else {
            this.insertNOde(node.left, key)
        }
    } else {
        // 右子树处理
        if (node.right == null) {
            node.right = new Node(key)
        } else {
            this.insertNode(node.right, key)
        }
    }
}

这样插入的逻辑就是变成从根节点开始进行判断:

  • 根节点无值, 则新增的 key 节点就是根节点
  • 根节点有值, 则将根节点开始进行 insertNode(root, key) 找到合适位置插入
// 插入一个 key
insert(key) {
    if this.root == null {
        // 空树的话那就是根节点
        this.root = new Node(key)
    } else {
        // 有值则找到合适位置插入
        this.insertNode(this.root, key)
    }
}

二叉树遍历

二叉树的遍历方式基本就3种, 先序遍历, 后序遍历, 中序遍历.

先序步骤: 根 => 左 => 右

应用: 复制树, 序列化树, 前缀表达式解析.

中序步骤：左 => 根 => 右

应用: 排序, 中缀表达式解析 (a + b * c)

后序步骤：左 => 右 => 根

应用: 释放内存, 后缀表达式解析 (栈), 修改树.

      1
     / \
    2   3
   /   / \
  4   5   6

先序, 遍历的结果是: 1, 2, 4, 3, 5, 6

后序, 遍历的结果是: 4, 2, 5, 6, 3, 1

中序, 遍历的结果是: 4, 2, 1, 5, 3, 6

先序遍历

即按照 根 -> 左 -> 右 的顺序, 先会访问节点本身(父节点), 然后再访问左侧节点, 最后右侧节点.

这里对于节点访问处理可以传递一个通用的 回调函数 callback , 同时用一个辅助方法 preOrderTraverseNode(node, callback) 来接受一个节点和回调函数.

// 辅助方法: 节点遍历
preOrderTraverseNode(node, callback) {
    // 基本情况
    if (node == null) return 
    
    // 递归情况: 先访问自身
    callback(node.key)
    // 再访问左树, 再是右树
    this.preOrderTraverseNode(node.left, callback)
    this.preOrderTraverseNode(node.right, callback)
}

// 先序遍历: 从根节点开始输入
preOrderTraverse(callback) {
    this.preOrderTraver(this.root, callback)
}

中序遍历

即按照 左 -> 根 -> 右 的顺序, 先访问子节点(叶子), 然后再访问根节点, 最后右侧节点.

同样节点访问处理可以传递一个通用的 回调函数 callback , 同时用一个辅助方法 inOrderTraverseNode(node, callback) 来接受一个节点和回调函数.

// 辅助方法: 节点遍历
inOrderTraverseNode(node, callback) {
    // 基本情况
    if (node == null) return 
    
    // 递归情况:  先左侧到叶子节点
    this.inOrderTraverse(node.left, callback)
    // 访问节点
    callback(node.key)
    // 再是右侧节点
    this.inOrderTraverse(node.right, callback)
}

// 中序遍历
inOrderTraverse(callback) {
    this.inOrderTraverse(this.root, callback)
}

后序遍历

即按照 左 -> 右 -> 根 的顺序, 先访问子节点(叶子), 然后再访问根节点, 最后右侧节点.

同样节点访问处理可以传递一个通用的 回调函数 callback , 同时用一个辅助方法 postOrderTraverseNode(node, callback) 来接受一个节点和回调函数.

// 辅助方法: 节点遍历
postOrderTraverseNode(node, callback) {
    // 基本情况
    if (node == null) return 
    
    // 递归情况:
    this.postOrderTraverse(node.left, callback)
    this.postOrderTraverse(node.right, callback)
    // 访问节点
    callback(node.key)
    
}

// 后序遍历
postOrderTraverse(callback) {
    this.postOrderTraverse(this.root, callback)
}

最大最小值

// BST 树的最小值
min() {
    return this.minNode(this.root)
}

minNode(node) {
    let current = node 
    // 因为是 BST 树, 小的值一定在左侧, 从树一层层往下到底就行
    while (current != null && current.left != null) {
        current = current.left
    }
    return current
}


// BST 树的最大值
max() {
    return this.maxNode(this.root)
}

maxNode(node) {
    let current = node 
    while (current != null && current.right != null) {
        current = current.right
    }
    return current.key
}

树中查询值

因为是 BST 树, 左侧深度递归查找就是越来越小, 右侧深度递归查找的值就越来越大, 否则就基本条件, 没有找到喽.

// 查询值
searchNode(node, key) {
    // 基本情况, 没有找到就返回 false
    if (node == null) return false 
    
    // 若 key 小于当前节点, 则继续左侧深度递归搜索
    if (key < node.key) return this.searchNode(node.left, key)
    
    // 若 key 大于当前节点, 则继续右侧深度递归搜索
    else if (key > node.key) return this.searchNode(node.right, key)
    
    // 找到就返回
    else return false 
}

树中移除值

这个算是非常复杂的逻辑了, 既要分析不同场景, 不同场景下又要进行递归, 就很难搞.

首先要做的就是要通过对子树分析, 来确定将被删节点的位置,

然后根据将要被删的节点位置, 分情况进行讨论处理.

* 如果不为 null，我们需要在树中找到要移除的键

* 如果要找的键比当前节点的值小, 就沿着树的左边找到下一个节点

* 如果要找的键比当前节点的值大, 就那么就沿着树的右边找到下一个节点

也就是说我们要分析它的子树。如果我们找到了要找的键（键和 node.key 相等），就需要处理三种不同的情况:

  • 移除一个叶节点 (无腿)
  • 移除一个有左侧 或者 右侧子节点的节点 (一条腿)
  • 移除有2个子节点的节点 (2条腿)
// 移除BST树中的节点
removeNode(node, key) {
    if (node == null) return null 
    
    if (key < node.key) {
        // 从左子树深度递归查找
        node.left = this.removeNode(node.left, key)
        return node
        
    } else if (key > node.key) {
        // 从右子树深度递归查找
        node.right = this.removeNode(node.right, key)
        return node 
        
    } else {
        // 找到了 key 的位置, 即 key == node.key 时候, 分3中情况讨论
        
        // 情况-01: 移除一个叶节点
        if (node.left == null && node.right == null) {
            node = null
            // 通过返回 null 将父节点的指针指向 null
            return node  
        }
        
        // 情况-02: 移除一个有左或右节点的节点(1条腿)
        // 跳过子节点, 直接将父节点指向其子节点
        if (node.left == null) {
            node = node.right
            return node
            
        } else if (node.right == null) {
            node = node.left
            return node
        }
        
        // 情况03 移除有两个子节点的节点 (2条腿)
        
        // a. 找到它右子树中最小节点, 下下层元素 grandson
        // b. 用 grandson 去替换掉被删节点的值 (改了键, 则移除了)
        // c. 继续将右侧子树的最小节点移除 (删掉重复键节点)
        // d. 向父节点返回更新的引用
        const grandson = this.minNode(node.right)
        node.key = grandson.key
        node.right = this.removeNode(node.right, grandson.key)
        return node 
    }
}

测试

// 测试
const tree = new BSTtree()
tree.insert(11)
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);


// 中序遍历
function callback(value) {
  console.log('callback-log: ', value);
}

// 中序遍历
console.log('中序遍历:');
tree.inOrderTraverse(callback)
console.log();

// 先序遍历
console.log('先序遍历:');
tree.preOrderTraverse(callback)
console.log();
// 后序遍历
console.log('后序遍历:');
tree.postOrderTraverse(callback)

// 树的最小值
console.log();
console.log('树的最小值是: ', tree.min());

// 树的最大值
console.log();
console.log('树的最大值是: ', tree.max());

// 查找值
console.log();
console.log(tree.search(1));
console.log(tree.search(8));

// 删除值
console.log('删除值 25', tree.remove(25));
tree.inOrderTraverse(callback)

console.log('删除值 15', tree.remove(15));
tree.inOrderTraverse(callback)

输出:

PS F:\algorithms> node .\bst_tree.js
中序遍历:
callback-log:  3
callback-log:  5
callback-log:  6
callback-log:  7
callback-log:  8
callback-log:  9
callback-log:  10
callback-log:  11
callback-log:  12
callback-log:  13
callback-log:  14
callback-log:  15
callback-log:  18
callback-log:  20
callback-log:  25

先序遍历:
callback-log:  11
callback-log:  7
callback-log:  5
callback-log:  3
callback-log:  6
callback-log:  9
callback-log:  8
callback-log:  10
callback-log:  15
callback-log:  13
callback-log:  12
callback-log:  14
callback-log:  20
callback-log:  18
callback-log:  25

后序遍历:
callback-log:  3
callback-log:  6
callback-log:  5
callback-log:  8
callback-log:  10
callback-log:  9
callback-log:  7
callback-log:  12
callback-log:  14
callback-log:  13
callback-log:  18
callback-log:  25
callback-log:  20
callback-log:  15
callback-log:  11

树的最小值是:  Node { key: 3, left: null, right: null }

树的最大值是:  25

false
true
删除值 25 undefined
callback-log:  3
callback-log:  5
callback-log:  6
callback-log:  7
callback-log:  8
callback-log:  9
callback-log:  10
callback-log:  11
callback-log:  12
callback-log:  13
callback-log:  14
callback-log:  15
callback-log:  18
callback-log:  20

删除值 15 
callback-log:  3
callback-log:  5
callback-log:  6
callback-log:  7
callback-log:  8
callback-log:  9
callback-log:  10
callback-log:  11
callback-log:  12
callback-log:  13
callback-log:  14
callback-log:  18
callback-log:  20

PS F:\algorithms>

至此, 关于树, 二叉搜索树的基本实现就到这里啦.

标签：基本,node,遍历,log,callback,BST,实现,key,节点
From： https://www.cnblogs.com/chenjieyouge/p/18355748

相关文章

  • 设计模式实战：交通管理系统的设计与实现
    系统功能需求交通信号控制：管理交通信号灯的状态，如红灯、绿灯和黄灯。交通策略应用：根据不同的交通状况（如高峰期、紧急状况）应用不同的交通控制策略。交通事件监控：实时监控交通事件（如事故、交通拥堵）并通知相关部门采取行动。设计分析状态模式状态模式用于表示对象在不......
  • PyTorch：从零实现一个双向循环神经网络
    从零实现一个双向循环神经网络（Bi-directionalRecurrentNeuralNetwork,Bi-RNN）从零开始，可以帮助我们深入理解RNN的机制。以下是实现步骤：定义RNN单元：实现一个简单的RNN单元，能够处理单个时间步长的数据。定义双向RNN：实现前向和后向的RNN，组合它们的输出。定义损失函......
  • KMP算法的两种实现形式
    以leetcode28.实现strStr()为例：给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从0开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。示例1：输入：haystack="sadbutsad",needle="sad"......
  • 抽象类、实现类、接口的区别
    抽象类、实现类、接口的区别接口和抽象类的区别：1.抽象类中的方法可以有方法体，也就是可以实现具体的方法，但是接口中的方法必须是抽象的，只能声明，没有方法体2.抽象类的成员变量修饰随便（public,private,protected等等），接口的成员变量必须是public,static,final修饰（默认）（可以用来做定......
  • NDT算法详解与C++实现
    点云匹配在感知环节是一个很重要的信息获取手段，而其中的算法也有几个比较经典了，例如ICP（IterativeClosestPoint，迭代最近点）算法，而本文决定记录学习的是NDT算法，也就是NormalDistributionTransform，正态分布变换算法。什么是正态分布变换算法呢，简言之，就是把空间中的点云进行整......
  • python-xlsxwriter的基本使用
    安装xlsxwriter：pipinstallXlsxWriter简单实例：#coding：utf-8importxlsxwriterworkbook=xlsxwriter.Workbook（'demo1.xlsx'）#创建一个Excel文件worksheet=workbook.add_worksheet（）#创建一个工作表对象worksheet.set_column（'A：A'，20）#设定第一列（A）宽度为20像素bold=......
  • C语言问答进阶--4、基本运算符
    赋值运算符A：下面将介绍赋值操作符。它的符号就是 = .A：赋值操作符，就是把一个值赋值给左边的变量。正如以前说的形如a=1之类的表达就是赋值运算符的具体应用。也许有的人在编写代码的时候写过这种代码：#include "iostream.h"int main(){    int x;    1=x;......
  • 用layui +echarts 曲线图实现子页面向父页面传值，点击曲线图表上的点后删除该点，并在删
    下面是一个完整的示例，展示了如何使用layui和ECharts实现以下功能：子页面向父页面传值。点击曲线图上的点后删除该点。删除后自动刷新layui表格列表。根据子页面传值和起止时间刷新父页面。文件结构假设你有两个文件：父页面(index.html)子页面(child.html)1.子页面......
  • Unity新输入系统 之 InputAction（输入配置文件最基本的单位）
    本文仅作笔记学习和分享，不用做任何商业用途本文包括但不限于unity官方手册，unity唐老狮等教程知识，如有不足还请斧正​首先你应该了解新输入系统的构成结构：Unity新输入系统结构概览-CSDN博客InputSystem-Unity手册1.InputAction概览还是需要强调，InputAction中定义了所......
  • Docker 的基本概念和优势，以及在应用程序开发中的实际应用
    Docker是一种用于虚拟化和部署应用程序的开源平台，它采用容器化技术，可以将应用程序及其依赖项打包成一个独立的、可移植的容器。以下是Docker的基本概念和优势：容器：Docker利用操作系统层面的虚拟化技术，将应用程序及其依赖项打包成一个独立的容器。每个容器都是独立的、可互......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99