이 진 트 리 - 자바 script 구현

/**
     *
     * @param val
     * @constructor
     */
    function Node(val, left, right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
    Node.prototype.show = function() {
        return this.val;
    }
    /**
     *
     * @constructor
     */
    function BTree() {
        this.root = null;
        this.depthBT = 0;
    }
    BTree.prototype = {
        constructor : BTree,
        add : function(val){
            //      ，    ，
            // 1.              ，         
            // 2.      ，      ，                         
            // 3.     ，        ，        ，              ，      
            // 4.              ，    ，          
            // 5.      ，       ，              ，      
            var newNode = new Node(val, null, null);
            if(!this.root) {
                //       
                this.root = newNode;
            }else {
                var current = this.root,
                    parent;//   current  ，     
                while(current) {
                    parent = current;
                    if(val < current.val) {
                        //          
                        current = current.left;
                        if(current == null ) {
                            parent.left = newNode;
                            return;
                        }
                    }else {
                        current = current.right;
                        if(current == null) {
                            parent.right = newNode;
                            return;
                        }
                    }
                }
            }
        },
        depth : function(node) {
            //      ，       ，    ，          
            //       ，    node.left node.right，  return 0
            //   ldepth rdepth，      +1，  1          
            //       ，               ，                    

            return !node ? 0 : Math.max(this.depth(node.left),this.depth(node.right)) + 1;
//            if(!node) {
//                return 0;
//            }else {
//                var ldepth = this.depth(node.left);
//                var rdepth = this.depth(node.right);
//                return ldepth > rdepth ? ldepth + 1 : rdepth + 1;
//            }
        },
        preorder : function(node) {
            //   ：        23→16→45
            //      ，      ，         node （23）
            //      ，    node  ，        （16），       .left  ，      
            //     .right  ，      
            //      ，    node  ，        （45），       .left  ，      
            //     .right  ，      

            //     
            if(node) {
                console.log(node.show());
                this.preorder(node.left);
                this.preorder(node.right);
            }
        },
        inorderTraversal : function(node) {
            //     
            if(node){
                this.inorderTraversal(node.left);
                console.log(node.show());
                this.inorderTraversal(node.right);
            }
        },
        postorderTraversal : function(node) {
            //     
            if(node) {
                this.postorderTraversal(node.left);
                this.postorderTraversal(node.right);
                console.log(node.show());
            }
        },
        BFS : function(node) {
            // 1.        （    ），     
            // 2.        ，       
            // 3.               ，         

            //       
            var nodes = [];

            if(!node) {
                console.log('empty tree');
            }else {
                nodes.push(node);

                while(nodes.length !== 0) {
                    node = nodes.shift();//     
                    console.log(node.val);

                    if(node.left) {
                        nodes.push(node.left);
                    }
                    if(node.right) {
                        nodes.push(node.right);
                    }
                }
            }
        },
        searchMin : function(node) {
            //           ，              

            //      
            while(node.left) {
                node = node.left;
            }
            return node;

        },
        searchMax : function(node) {
            //      
            while(node.right) {
                node = node.right;
            }
            return node;
        },
        find : function(val) {
            //                ，              

            //      
            var node = this.root,
                parent = node;//      

            while(node) {
                if(node.val === val) {
                    //               
                    return {nodeParent : parent,findNode : node};
                }else{
                    parent = node;
                    if(node.val > val) {
                        node = node.left;
                    }else {
                        node = node.right;
                    }
                }
            }
            return null;
        },
        removeNode : function(val) {
            // 1.        ，     ，             null
            // 2.         ，                 
            // 3.         ，（1）                        （2）                       

            //     
            var currentobj = this.find(val),
                parentNode,//    
                currentNode;//     

            if(currentobj){
                parentNode = currentobj.nodeParent;//      
                currentNode = currentobj.findNode;//       

                if(currentNode.left == null && currentNode.right == null){
                    choosePos(null);

                }else if(currentNode.left && currentNode.right){
                    var max = this.searchMax(currentNode.right).val,//        
                        maxNode = this.find(max);//                 ，    

                    currentNode.val = max;//              
                    maxNode.nodeParent.right = null;//        ，            null

                }else if(currentNode.right){//      ，      
                    choosePos(currentNode.right);
                }else if(currentNode.left) {//      ，      
                    choosePos(currentNode.left);
                }
            }else{
                return '        ';
            }
            //             ，         ，        ，  
            function choosePos(setValue){
                currentNode.val > parentNode.val ? parentNode.right = setValue : parentNode.left = setValue;
            }
        }
    }

    var bt = new BTree(),
        arrTree = [23,45,16,37,3,4,99,22,44,52,42,10,100,1];

    arrTree.forEach(function(i){
        //      
        bt.add(i);
    });
    console.log(bt);

    console.log('  ');
    bt.preorder(bt.root);
    console.log('  ');
    bt.inorderTraversal(bt.root);
    console.log('  ');
    bt.postorderTraversal(bt.root);

    //      
    console.log(bt.depth(bt.root));

    //         
    console.log('      ' + bt.searchMin(bt.root).val);
    //         
    console.log('      ' + bt.searchMax(bt.root).val);

    //      
    console.log('         ：' + bt.find(99).nodeParent.val);
    console.log('      ：' + bt.find(99).findNode.val);

    //     
    console.log('             ：' + bt.find(52).nodeParent.val);
    bt.removeNode(52);
    console.log('          ：' + bt.find(52));
    console.log(bt.removeNode(55));