树

[funnycoderstar]

树的相关术语

二叉树和二叉搜索树

• 二叉树: 二叉树的中的节点最多只能有两个节点: 一个是左侧子节点, 另一个是右侧子节点
• 二叉搜索树(BST): 二叉树的一种, 只允许在左侧节点存储(比父节点)小的值,在右侧节点存储(比父节点大或者等于)的值

JS实现树

let insertNode = function(node, newNode) {
    if(newNode.key < node.key) {
        if(node.left == null) {
            node.left = newNode;
        } else {
            insertNode(node.left, newNode)
        }
    } else {
        if(node.right === null) {
            node.right = newNode;
        } else {
            insertNode(node.right, newNode)
        }
    }
}
function BinarySearchTree() {
    let Node = function(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
    let root = null;
    this.insert = function(key) {
        let newNode = new Node();
        if (root == null) {
            root = newNode;
        } else {
            insertNode(root, newNode);
        }
    }
    // 中序遍历
    this.inOrderTraverse = function(callback) {

    }
    // 后序遍历
    
}