二叉树的搜索

function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

// 新增一个节点
function addNode(root, num) {
    if (root == null) {
        return;
    }
    if (root.value == num) {
        return;
    }
    if (root.value < num) {   // 目标值比当前节点大
        if (root.right == null) { // 当前节点右侧为空，则创建右侧节点
            root.right = new Node(num);
        } else {  // 如果右侧不为空，则右侧进行递归
            return addNode(root.right, num);
        }
    } else {
        if (root.left == null) {
            root.left = new Node(num);
        } else {
            return addNode(root.left, num);
        }
    }
    return root;
}

// 二叉树的搜索
let num2 = 0;
function searchByTree(root, target) {
    if (root == null) {
        return false;
    }
    num2 += 1;
    if (root.value == target) {
        return true;
    }
    if (root.value > target) {
        return searchByTree(root.left, target)
    } else {
        return searchByTree(root.right, target);
    }
}

//构建二叉树
function buildSearchTree(arr) {
    if (arr == null || arr.length == 0) {
        return null;
    }
    let root = new Node(arr[0]);
    for (let i = 1; i < arr.length; i++) {
        addNode(root, arr[i]);
    }
    return root;
}

let arr = [];
for (let i = 0; i < 10000; i++) {
    arr.push(Math.floor(Math.random() * 10000));
}


let root = buildSearchTree(arr);
console.log(searchByTree(root, 1000));
console.log(num2);