javascript 데이터 구조 테마 - 이 진 트 리 기본 조작

//    
function Node(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
}
//      
Node.prototype = {
    show: function () {
        console.log(this.data);
    }
}
//     
function Tree() {
    this.root = null;
}
Tree.prototype = {
//  
//          :               ，
//               ，           
    insert: function (data) {
        var node = new Node(data, null, null);
        if(!this.root) {
            this.root = node;
            return;
        }
        var current = this.root;
        var parent = null;
        while (current) {
            parent = current;
            if (data < parent.data) {
                current = current.left;
                if(!current) {
                    parent.left  = node;
                    return;
                }
            } else {
                current = current.right;
                if(!current) {
                    parent.right = node;
                    return;
                }
            }
        }
    },
    //          。              ，         ，       null，
//           ，                    。
//          ，     ，       ，                  （               ），
//                 ，   ，            ，  ，              ，    。。。

//                    A，       ，     A；
//                    A，       ，     A。
//            （         ） ？                  ，          ，         ，              。
    delete: function(root, data) {
       if(!root) {
           console.log("    ")
           return root;
       }
       if(data < root.data) {//           ，             
           root.left = this.delete(root.left, data)
       } else if (data > root.data) {//           ，             
           root.right = this.delete(root.right, data)
       } else {           
          if(root.left === null && root .right === null) {//    
            root = null;
          } else if(root.left === null) {//     
            root = root.right
          } else if(root.right === null) {//     
            root = root.left
          } else {//        
            let prevNode = root.left;
            while(prevNode.right) {//                
                prevNode = prevNode.right
            }
            root.data = prevNode.data //   
            root.left = this.delete(root.left, prevNode.data);//     ，        
          }
       }
       return root
    },
    //    
    preOrder: function (node) {
        if (node) {
            node.show();
            this.preOrder(node.left);
            this.preOrder(node.right);
        }
    },
    //    
    middleOrder: function (node) {
        if (node) {
            this.middleOrder(node.left);
            node.show();
            this.middleOrder(node.right);
        }
    },
    //    
    laterOrder: function (node) {
        if(node) {
            this.laterOrder(node.left);
            this.laterOrder(node.right);
            node.show();
        }
    },
    //     
    getMin: function () {
        var current = this.root;
        while(current) {
            if(!current.left) {
                return current
            }
            current = current.left;
        }
    },
    //     
    getMax: function () {
        var current = this.root;
        while(current) {
            if(!current.right) {
                return current;
            }
            current = current.right;
        }
    },
    //    
    getDeep: function (node, deep) {
        deep = deep || 0;
        if(node == null) {
            return deep;
        }
        deep++;
        var dleft = this.getDeep(node.left, deep);
        var dright = this.getDeep(node.right, deep);
        return Math.max(dleft, dright);
    },
    //    
    getNode: function (data, node) {
        if(node) {
            if(node) {
                if(data === node.data) {
                    return node;
                } else if (data < node.data) {
                    return this.getNode(data, node.left);
                } else {
                    return this.getNode(data, node.right);
                }
            }
        } else {
            return null
        }
    }

}
var t = new Tree();
t.insert(3);
t.insert(9);
t.insert(1);
t.insert(8);
t.insert(2);
t.insert(7);
t.insert(4);
t.insert(5);
t.insert(0);
console.log(t);
t.middleOrder(t.root);
console.log("MIN/n", t.getMin(), "MAX/n", t.getMax(), "DEEP", t.getDeep(t.root, 0), "getNode", t.getNode(5,t.root))