js 쓰기 데이터 구조 (2) 정렬 이 진 트 리

function BinarySearchTree() {
    this.root = null;
}

//          
BinarySearchTree.prototype.insert = function( key ) {
    var Node = function(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }
    var node = new Node( key );
    if( this.root == null ) {
        this.root = node;
        return;
    }
    var e = this.root;
    while( true ) {
        //              。
        if( node.key <= e.key ) {
            if( e.left != null ) {
                e = e.left;
            }
            else {
                e.left = node;
                break;
            }
        }
        //              。
        else{
            if( e.right != null ) {
                e = e.right;
            }
            else{
                e.right = node;
                break;
            }
        }

    }
}
//        ，      ，   true；     ，   false；
BinarySearchTree.prototype.search = function( key ) {
    var e = this.root;
    var s = [];
    while( e ) {
        while( e ) {
            if( e.key == key ){
                return true;
            }
            if( e.right ) {
                s.push( e.right );
            }
            e = e.left;
        }
        e = s.pop();
    }
    return false;
}
//     
BinarySearchTree.prototype.inOrderTraverse = function() {
    if( this.root == null ) {
        return null;
    }
    var s = new Array();  //      。
    var result= [] ;  //      
    s.push( this.root );
    var e = this.root;
    while( s.length || e ) {
        while( e ){   //     。
            if( e != this.root ){
                s.push( e );
            }
            e = e.left;
        }

        e = s.pop();

        if( !e ){
            break;
        }
        result.push(e.key);
        e = e.right;
    
    }
    return result;
}
//     
BinarySearchTree.prototype.preOrderTraverse = function() {
    if( this.root == null ){
        return
    }
    var s = new Array(); //         。
    var result = [];    //      。
    var e = this.root;

    while( e ) {
        while( e ) {    //     
            if( e.right != null ){
                s.push( e.right );
            }
            result.push(e.key);
            e = e.left;
        }

        e = s.pop();
    }
    return result;
}
//     
BinarySearchTree.prototype.postOrderTraverse = function() {
    if( this.root == null ) {
        return null;
    }
    var s = new Array();  //      。
    var result= [] ;  //      
    var prev = null;
    s.push( this.root );
    var e = this.root;
    while( s.length || e ) {
        while( e ){   //     。
            if( e != this.root ) {
                s.push( e );
            }
            e = e.left;
        }

        e = s[ s.length - 1 ];
        if( e.right == prev || e.right == null ) {
            result.push( e.key );
            prev = s.pop();
            e = null;

        }else{
            e = e.right;
        } 

    
    }
    return result;
}
//         
BinarySearchTree.prototype.min = function() {
    var e = this.root;
    var min;
    if( !this.root ) {
        return;
    }
    while( e ) {
        min = e.key;
        e = e.left;
    }
    return min;
}
//         
BinarySearchTree.prototype.max = function() {
    var e = this.root;
    var max;
    if( !this.root ) {
        return;
    }
    while( e ) {
        max = e.key;
        e = e.right;
    }
    return max;
}
//        。
BinarySearchTree.prototype.remove = function( key ) {
    if( key == this.root.key ) {   //     。
        if( this.root.left && this.root.right ) {   //         
            var root = this.root;
            this.root = this.root.left;
            var temp =this.serarchCurrAddr(this.root,"right");
            temp.right = root.right;
        }
        else{           //            。
            this.root = this.root.left || this.root.right;
        }
        return;
    }
    //      
    else {
        var e = this.root;
        var s = [];
        while( e ) {
            while( e ) {
                if( e.left && e.left.key == key ){
                    this.delete(e,"left");
                    return;
                }else if( e.right && e.right.key == key ){
                    this.delete(e,"right");
                    return;
                }

                if( e.right ) {
                    s.push( e );
                }
                
                e = e.left;
            }
            e = s.pop();
        }
    }
}

BinarySearchTree.prototype.delete = function( parent, direction ) {
    var deleteTarget = parent[direction];
    if( deleteTarget.left && deleteTarget.right ) {
        var temp = this.serarchCurrAddr(deleteTarget.left,"right");
        temp.right = deleteTarget.right;
        parent[direction] = deleteTarget.left;
    }else{
        parent[direction] = deleteTarget.right || deleteTarget.left;
    }
}

//         /      。
BinarySearchTree.prototype.serarchCurrAddr = function( currentRoot, direction ) {
    var e = currentRoot;
    while( e ) {
        if( e[direction] == null ) {
            return e;
        }
        e = e[direction];
    }
}


///       
var a = new BinarySearchTree();

a.insert( 3 );
a.insert( 1 );
a.insert( 2 );
a.insert( 4 );
a.insert( 5 );
a.insert( 0 );

a.remove(3);
console.log(a.search(5));
console.log(a.postOrderTraverse());