[数据结构与算法]数据结构之简单二叉搜索树 前端必会算法

二叉搜索树的定义

二叉搜索树（Binary Search Tree）：是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

通俗来说就是每棵子树都满足，左子树节点小于根节点，右子树节点大于根节点。

二叉搜索树的创建

给定一个数组返回一棵二叉搜索树

// 二叉树的结构
function TreeNode(val, left, right) {
    this.val = val;
    this.left = left;
    this.right = right;
}

传入一个值，将这个值插入到二叉搜索树中。

1. 如果这个节点已经存在就不做操作
2. 遵循小于根节点的在左边，大于根节点的在右边
3. 这个新插入的节点一定是当前二叉搜索树的叶子节点。

function addNode(root, val) {
    if (!root || val == undefined || root.val === val) {
        return; // !0 也是true
    }
    if (val < root.val) {
        if (root.left) {
            addNode(root.left, val);
        } else {
            root.left = new TreeNode(val);
        }

    } else {
        if (root.right) {
            addNode(root.right, val);
        } else {
            root.right = new TreeNode(val);
        }
    }
}

有了addNode,生成一个二叉搜索树就很简单了。

/**
 *
 *
 * @param {Array} arr
 */
function createBinaryTree(arr) {
    if (!arr || arr.length === 0) {
        return null;
    }
    let root = new TreeNode(arr[0]);
    for (let i = 1; i < arr.length; i++) {
        addNode(root, arr[i]);
    }
    return root;
}

一般来说，直接写代码可能性不高。
可能会考到给你一个数组,让你画出二叉搜索树