Binary Search Tree(BST) 是很基础的数据结构，书中不止一条关于binary tree的题目，所以这里集中讨论三个问题。

首先是BST的实现，目前我参考了[1],[2],[3]的程序，总结写出了一个基本的类，包含insert, remove, destroy_tree, search等函数。

花时间最多的是remove函数的实现。难点是当要移除的节点有2个子节点。我采用了[2]中的程序，[2]中的方法正是[3]中提到的思路。

如图中所示：

如果要删除的节点N=7,那么不要直接删N，而是在节点7的左子树中找到最右边的节点R=6，然后用把N的值换成R的值，即让N=6,然后再把原来的节点 R删除。

void BinaryTree::remove(int key){
    Node* current = search(key);
    Node* parent = predecessor(key);
    if(current != NULL){
	if(current->left && current->right){
	    // if 2 children
	    // goes to the LEFT subtreexs
	    Node* replace = current;
	    parent = current;
	    current = current->left;
	    // keep on parse through the subtree until 
	    // reach the rightmost node of the LEFT subtree
	    while(current->right){
		parent = current;
		current = current->right;
	    }
	    // replace the value_to_be_removed with the rightmost value 
	    // then remove the rightmost node later
	    replace->value = current->value;
	}

	// 1 or 0 child case
	// if 1 child,  tmp is the non-null child
	// if 0 child,  tmp is null
	Node *tmp = (current->left ? current->left: current->right);
	if(parent == NULL){ // this means a one-node tree
	    root = tmp;
	}else{
	    if (parent->value < current->value)
		// the number to be removed is actually the righ child of this parent
		parent->right = tmp;
	    else
		parent->left = tmp;
	}
	
	delete current;
    }
    return;
}

39题是求BST的深度，这题目用递归就可以实现：

int BinaryTree::depth_subtree(Node* leaf){
    if(leaf==NULL)
	return 0;
    int depth_left = depth_subtree(leaf->left);
    int depth_right = depth_subtree(leaf->right);
    
    return (depth_left > depth_right) ? depth_left : depth_right; 
}

int BinaryTree::depth(){
    return depth_subtree(root);
}

23题要求从上到下依次输出树节点的值：解法用了STL中的deque，用了队列“先入先出”的特性。

void BinaryTree::print_top_to_bottom(){
    if(root==NULL)
	return;
    
    deque<Node*> deque_tree_nodes;
    deque_tree_nodes.push_back(root);
    while(deque_tree_nodes.size()){
	Node* current = deque_tree_nodes.front();
	cout<<current->value<<" "<<endl;
	deque_tree_nodes.pop_front();
	if(current->left != NULL){
	    deque_tree_nodes.push_back(current->left);
	}
	if(current->right != NULL){
	    deque_tree_nodes.push_back(current->right);
	}
    }
}

最后是第6题，输入某BST的前序遍历和中序遍历的结果，重建出此BST. （这题目真的很奇怪，如果遇到我就只能呵呵了。不喜欢这题目，看懂了作者的程序，这里我就不多说了）

完整程序在：

git clone https://github.com/zhutiti/Hehaitao.git

参考：

[1]Binary Trees in C++: Part 1 http://www.cprogramming.com/tutorial/lesson18.html

[2]Binary Search Tree http://code.activestate.com/recipes/577552-binary-search-tree/

[3]Binary Search Tree http://en.wikipedia.org/wiki/Binary_search_tree