二叉搜索树的应用

const arr = [];
/**
 * 生成数字
 * @param {Number} len 数据的长度
 */
function createArr(len) {
    for (let i = 0; i < len; i++) {
        arr.push(Math.floor(Math.random() * 10000))
    }
}
createArr(10000)
/**
 * Node类
 */
class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
/**
 * 生成二叉搜索树
 * @param {Array} arr 数组
 */
function buildSearchTree(arr) {
    if (arr == null || arr.length == 0) return;
    let root = new Node(arr[0]);
    for (let i = 1; i < arr.length; i++) {
        addNode(root, arr[i])
    }
    return root;
}
/**
 * 生成子树
 * @param {Object} root 根节点
 * @param {Number} num  需要比对的数字
 */
function addNode(root, num) {
    if (num == null) return;
    if (root.value == num) return;
    if (root.value < num) {// num大于root num会在root的右子树
        if (root.right == null) root.right = new Node(num);
        else addNode(root.right, num);
    } else { // num小于root，num会在root的左子树
        if (root.left == null) root.left = new Node(num);
        else addNode(root.left, num);
    }
}
let root = buildSearchTree(arr)
/**
 * 二叉树搜索
 * @param {Object} root 根节点
 * @param {Number} target 目标值
 */
function searchNode(root, target) {
    num++;
    if(root == null ) return false;
    if(root.value == target) return true;
    if(root.value < target) return searchNode(root.right,target)
    else return searchNode(root.left, target);
}
let result = searchNode(root , 1000)
console.log(result , num)