二叉树

二叉树和二叉查找树

树的定义

树由一组以边连接的节点组成

数的相关概念

1. 路径：一个节点到另一个节点的一组边
2. 遍历：以某种特定顺序访问树中所有节点
3. 深度：树的层数

实现二叉查找树

    //构建Node对象
    function Node(data, left, right) {
        this.data = data;
        this.left = left;
        this.right = right;
        this.show = show;
    }

    function show() {
        return this.data;
    }
    //实现二叉查找树
    function BST() {
        this.root = null;
        this.insert = insert;
        this.inOrder = inOrder;
        this.preOrder = preOrder;
        this.postOrder = postOrder;
        this.getMin = getMin;
        this.getMax = getMax;
        this.find = find;
    }
    //插入节点
    function insert(data) {
        var n = new Node(data, null, null);
        if(this.root == null) {
            this.root = n;
        }
        else {
            var curr = this.root;
            var parent;
            while(true) {
                parent = curr;
                if(data < curr.data) {
                    curr = curr.left;
                    if(curr == null) {
                        parent.left = n;
                        break;
                    }
                }
                else {
                    curr = curr.right;
                    if(curr == null) {
                        parent.right = n;
                        break;
                    }
                }
            }
        }
    }
    //中序遍历
    function inOrder(node) {
        if(!(node == null)) {
            inOrder(node.left);
            console.log(node.show() + " ");
            inOrder(node.right);
        }
    }
    //先序遍历
    function preOrder(node) {
        if(!(node == null)) {
            console.log(node.show() + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }
    //后序遍历
    function postOrder(node) {
        if(!(node == null)) {
            postOrder(node.left);
            postOrder(node.right);
            console.log(node.show() + " ");
        }
    }
    //查找最小值
    function getMin() {
        var curr = this.root;
        while(!(curr.left == null)) {
            curr = curr.left;
        }
        return curr.data;
    }
    //查找最大值
    function getMax() {
        var curr = this.root;
        while(!(curr.right == null)) {
            curr = curr.right;
        }
        return curr.data;
    }
    //查找任意值
    function find(data) {
        var curr = this.root;
        while(curr != null) {
            if(curr.data == data) {
                return curr;
            }
            else if(data < curr.data) {
                curr = curr.left;
            }
            else {
                curr = curr.right;
            }
        }
        return null;
    }