二叉树和二叉搜索树

date
Mar 22, 2023
slug
js-tree-init
status
Published
tags
JavaScript数据结构与算法
JavaScript
Tree
summary
Binary search tree initialization
type
Post
​ 二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。
​ 二叉搜索树（BST）是二叉树的一种，但是只允许你在左侧节点存储（比父节点）小的值， 在右侧节点存储（比父节点）大的值。
下图为二叉搜索树的组织结构：
notion image
在双向链表中，每个节点包含两个指针，一个指向下一个节点，另一个指向上一个节点。对于树， 使用同样的方式（也使用两个指针），但是一个指向左侧子节点，另一个指向右侧子节点。

创建BinarySearchTree类

创建 Node 类来表示二叉搜索树中的每个节点
class Node{
    constructor(key){
        this.key = key; //节点值
        this.left = null;//左侧子节点引用
        this.right = null;//右侧子节点引用
    }
}

const Compare = { 
    LESS_THAN: -1, 
    BIGGER_THAN: 1 
   }; 
function defaultCompare(a,b){
    if(a === b){
        return 0;
    }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

class BinarySearchTree{
    constructor(compareFn = defaultCompare){
        this.compareFn = compareFn;//比较节点值
        this.root = null;//Node类型的根节点
    }
}

二叉搜索树插入一个键

​ 对于二叉搜索树，检测尝试插入的树节点是否为第一个节点。如果是，创建一个 Node 类的实例并将它赋值给 root 属性来将 root 指向这个新节点。因为在 Node 构建函数的属性里，只需要向 构造函数传递我们想用来插入树的节点值（key），它的左指针和右指针的值会由构造函数自动设置为 null。
insert(key){
    if(this.root === null){
        this.root = new Node(key);
    }else{
        this.insertNode(this.root,key);
    }
}

insertNode(node,key){
    if(this.compareFn(key,node.key) === Compare.LESS_THAn){//新节点的键小于当前节点的键
        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);
        }
    }
}
  • 如果树非空，需要找到插入新节点的位置。因此，在调用 insertNode 方法时要通过参 数传入树的根节点和要插入的节点。
  • 如果新节点的键小于当前节点的键（现在，当前节点就是根节点），那么需要检查当前节点的左侧子节点。注意在这里，由于键可能是复杂的对象而不是数，我们使用传入二叉搜索树构造函数的 compareFn 函数来比较值。如果它没有左侧子节点， 就在那里插入新的节点。如果有左侧子节点，需要通过递归调用 insertNode 方法继续找到树的下一层。在这里，下次要比较的节点将会是当前节点的左侧 子节点（左侧节点子树）。
  • 如果节点的键比当前节点的键大，同时当前节点没有右侧子节点，就在那里插 入新的节点）。如果有右侧子节点，同样需要递归调用 insertNode 方法，但是 要用来和新节点比较的节点将会是右侧子节点（右侧节点子树）。
建立测试用例
​ 首先创建二叉搜索树：
const tree = new BinarySearchTree(); 
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);
插入一个值为 6 的键
tree.insert(6);
执行过程：
  1. 树不空，执行this.insertNode(this.root, key),insertNode 方法将会被调用（root, key[6]）
  1. 接下来检查this.compareFn(key, node.key) === Compare.LESS_THAN为真 (key[6] < root[11]),接下来判断node.left == null不满足条件（node.left[5] != null）,执行insertNode（node.left[7], key[6]）。
  1. 再次进入 insertNode 方法内部，但是使用了不同的参数。再次检查key[6] < key[7]，在检查key[7]的左节点（node.left[5]不是 null），接着调用 insertNode（node.left[5], key[6]）
  1. 将再一次进入 insertNode 方法内部。它会再次检测 this.compareFn(key, node.key) === Compare.LESS_THAN（key[6] < node[5]为假）， 然后到达if (node.right == null)（node.right 是 null——节点 5没有任何右侧的子节点），然后将会执行node.right = new Node(key);， 在节点 5 的右侧子节点位置插入键 6。
  1. 然后，方法调用会依次出栈，代码执行过程结束。
插入之后的树结构如下：
notion image

© shallrise 2024