# 6，23，39二叉树(1) 打印，深度，重建 Binary Search Tree (1)

Author posted @ 2013年10月05日 16:32 in 剑指Offer with tags c++ , 2790 阅读

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

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);
}
}
}


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

seo 说:
2021年10月01日 02:39

Never knew that Caldwells would be this great. I just saw their portfolio from a blog and bought customized doors from them. Check their site through https://caldwells.com/interior-doors/caldwells-signature-door-series link.

merckseo 说:
2021年10月10日 08:06

Best Social Plan is the most trusted company for providing social media marketing services. Best Social Plan

anonymous 说:
2023年7月28日 05:27

Welcome to the party of my life      here you will learn everything about me. Kissimmee Bed Bug Control

anonymous 说:
2023年8月04日 23:38

You bear through a awesome vacancy. I sanity definitely quarry it moreover personally suggest to my buddys. I am self-possessed they determination be benefited from this scene. Termite Treatment Orlando

anonymous 说:
2023年8月04日 23:41

It is especially decent, though look into the tips during this home address. Termite Treatment Oviedo

(输入验证码)
or Ctrl+Enter