SOURCE

function Stack(){
	var items = [];
    this.push = function(item){
        items.push(item);
    }
    this.pop = function(){
        return items.pop();
    }
    this.top = function(){
       return items[items.length -1];
    }
    this.isEmpty = function(){
       return items.length === 0;
    }
    this.size = function(){
       return items.length;
    }
    this.clear = function(){
       items = [];
    }
}

function BinaryTreeNode(data){
    this.data = data; // 数据域
    this.leftChild = null; // 左孩子
    this.rightChild = null; // 右孩子
    this.parentNode = null; // 父节点
}

function BinaryTree(){
    var root = null; // 根节点

    // 采用广义表表示的建立二叉树方法
    this.init_tree = function(string){
	    var stack = new Stack();
        var k = 0; // 标识识别的左子树还是右子树
        var new_node = null;

        for(var i = 0 ; i< string.length ; i++ ){
            var item = string[i];
            if(item == "#"){
                break;
            }
            else if(item == "("){
                stack.push(new_node);
                k = 1;
            }
            else if(item == ","){
                 k = 2;
            }
            else if(item == ")"){
                stack.pop();
            }
            else{
                new_node = new BinaryTreeNode(item); // 创建节点
                if(root== null){
                	root = new_node;
                }else{

                    if(k === 1){ // new_node是做孩子
						var top_item = stack.top(); // 父节点
						top_item.leftChild = new_node;
                        new_node.parentNode  = top_item;
                    }else if(k === 2){ // 右孩子
						var top_item = stack.top(); // 父节点
						top_item.rightChild = new_node;
                        new_node.parentNode  = top_item;
                    }

                }

            }
        }
    }
    this.get_root = function(){
		return root;
    }
    
    // 中序遍历
    // 先遍历左孩子，最后遍历右孩子
    this.in_order = function(node){
		if(node === null){
			return;
		}
		this.in_order(node.leftChild);
		console.log(node.data);
		this.in_order(node.rightChild);
    }

    this.pre_order = function(node){
		if(node === null){
			return;
		}
		console.log(node.data);
		this.pre_order(node.leftChild);
		this.pre_order(node.rightChild);
    }
    
    this.post_order = function(node){
		if(node === null){
			return;
		}
		this.post_order(node.leftChild);
		this.post_order(node.rightChild);
		console.log(node.data);
    }
    var tree_node_count = function(node){
		// 左子树的节点数量 + 右子树的节点数量 + 当前节点（1）
		if(node==null){
            return 0;
        }
        var left_node_count = tree_node_count(node.leftChild); 
        var right_node_count = tree_node_count(node.rightChild);
        return left_node_count + right_node_count + 1;
        
	}
	this.size = function(node){
		return tree_node_count(node);
	}
    this.height = function(node){
        return tree_height(node);
    }
    var tree_height = function(node){
        if(node==null){
            return 0;
        }
        
        // 先计算左子树的高度
        var left_node_height = tree_height(node.leftChild); 
        // 再计算右子树的高度
        var right_node_height = tree_height(node.rightChild);
        return Math.max(left_node_height,right_node_height) + 1;
        
    }
    this.height = function(node){
        return tree_height(node);
    }
}

function pre_order(node){ 
    var curr_node = node ;
    
    var stack = new Stack();
    while(curr_node){
        console.log(curr_node.data); 
		if(curr_node.rightChild){
            stack.push(curr_node.rightChild);
        }
        curr_node = curr_node.leftChild||stack.pop();
    }
};


// A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))#
// A(B(D,E(G,)),C(,F))#
var new_tree = new BinaryTree();
new_tree.init_tree('A(B(D,E(G,)),C(,F))#');
var root_node = new_tree.get_root();
console.log('new_tree.in_order');
new_tree.in_order(root_node);

console.log("new_tree.height");
console.log(new_tree.height(root_node));

console.log('pre_order');
pre_order(root_node);
console.log('new_tree.post_order');
new_tree.post_order(root_node);


// > new_tree.in_order
// > D
// > B
// > G
// > E
// > A
// > C
// > F
// > new_tree.height
// > 4
// > pre_order
// > A
// > B
// > D
// > E
// > G
// > C
// > F
// > new_tree.post_order
// > D
// > G
// > E
// > B
// > F
// > C
// > A