|
說 明 |
應用問題區首頁 |
樣板二元搜尋樹 ( binary search tree )
| |
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <string>
#include <sstream>
#include <vector>
using namespace std ;
template <typename T>
struct Node {
T data ;
Node<T> *left , *right ;
Node( const T& d ) : data(d) , left(NULL) , right(NULL) {}
bool is_leaf_node() const {
return ( left == NULL && right == NULL ) ? true : false ;
}
} ;
template <typename T>
ostream& operator<<( ostream& out , const Node<T>& foo ) {
return out << foo.data ;
}
template <typename T>
class BST {
private :
Node<T> *root ;
// 列印 ptr 指向的 subtree
void print_subtree( ostream& out , const Node<T>* ptr , int depth = 1 ) const ;
// 找出最靠近 ptr 指向的 subtree 的節點位置
Node<T>* max_subtree( const Node<T>* ptr ) const ;
// 找出 ptr 指向的 subtree 的深度
int subtree_depth( const Node<T>* ptr ) const ;
// 清除 ptr 指向的 subtreem, 同時 ptr 設為 NULL
void erase_subtree( Node<T>* &ptr ) const ;
// 複製 q 指向的 subtree 到 ptr
void copy_subtree( Node<T>* &ptr , const Node<T> *q ) const ;
// 由小到大列印 ptr 指向的 subtree 的所有元素
void list_tree_nodes( const Node<T> *ptr , ostringstream& ostr ) const ;
// 將 ptr 指向的 subtree 由小到大存入 foo
void get_tree_nodes( const Node<T> *ptr , vector<T>& foo ) const ;
// 去除根節點
void delete_root() ;
// 去除非根節點 : p 指向所要去除的節點, q 為 p 的父節點
void delete_non_root_node ( Node<T>* p , Node<T> *q ) ;
// 去除一筆資料 d
bool erase_element( const T& d ) ;
public :
BST() : root(NULL) {}
// 複製建構函式
BST( const BST<T>& foo ) ;
// 指定運算子
BST<T>& operator= ( const BST<T>& foo ) ;
// 解構函式
~BST () { erase_subtree(root) ; }
// 清除 tree
void erase_tree() { erase_subtree(root) ; }
// 插入資料 d : 若 d 較節點資料值大, 則存入右邊, 否則存入左邊
void insert ( const T& d ) ;
// 由小到大輸出所有元素成字串
string tree_nodes() const ;
// 計算樹的深度
int depth() const { return subtree_depth(root) ; }
// 找尋資料 d, 回傳找到的位置
const Node<T>* find( const T& d ) const ;
// 去除所有資料 d, 回傳刪除的個數
int erase( const T& d ) ;
// 插入一個元素
BST<T>& operator+= ( const T& d ) ;
// 兩樹合成
BST<T>& operator+= ( const BST<T>& foo ) ;
// 去除所有資料 d
BST<T>& operator-=( const T& d ) ;
// 兩樹合成
template <typename S>
friend BST<S> operator+ ( const BST<S>& a , const BST<S>& b ) ;
// 列印
template <typename S>
friend ostream& operator<<( ostream& out , const BST<S>& foo ) ;
};
int main() {
BST<int> foo , bar ;
srand( static_cast<unsigned>(time(NULL)) ) ;
int random ;
for ( int i = 0 ; i < 10 ; ++i ) {
random = rand() % 10 ;
foo += random ;
bar += random+rand()%5 ;
}
cout << "> foo : \n"
<< foo << endl << endl ;
cout << "> bar : \n"
<< bar << endl << endl ;
BST<int> c = foo + bar ;
cout << "> c (foo+bar) : \n"
<< c << "\n\n\n" ;
bar = c ;
cout << "> bar :\n"
<< bar << endl << endl ;
cout << "> elements : " << bar.tree_nodes() << endl ;
int d ;
while ( 1 ) {
cout << "> element to be deleted : " ;
cin >> d ;
cout << "> Nodes of being deleted : " << bar.erase(d) << endl ;
cout << bar << endl ;
cout << "> elements : " << bar.tree_nodes() << endl ;
}
return 0 ;
}
// 列印 ptr 指向的 subtree
template <typename T>
void BST<T>::print_subtree( ostream& out , const Node<T>* ptr , int depth ) const {
if ( ptr == NULL ) {
out << setw((depth-1)*5) << "|--> "
<< setw(5) << left << "." << right << "\n" ;
} else {
if ( depth > 1 ) out << setw((depth-1)*5) << "|--> " ;
out << setw(5) << left << ptr->data << right << endl ;
if ( ! ptr->is_leaf_node() ) {
print_subtree( out , ptr->right , depth+1 ) ;
print_subtree( out , ptr->left , depth+1 ) ;
if ( ptr->left == NULL || ( ptr->left != NULL && ptr->left->is_leaf_node() ) ) out << endl ;
}
}
}
// 找出最靠近 ptr 指向的 subtree 的節點位置
template <typename T>
Node<T>* BST<T>::max_subtree( const Node<T>* ptr ) const {
if ( ptr == NULL || ptr->left == NULL )
return NULL ;
else {
Node<T> *p = ptr->left ;
while ( p->right != NULL ) p = p->right ;
return p ;
}
}
// 找出 ptr 指向的 subtree 的深度
template <typename T>
int BST<T>::subtree_depth( const Node<T>* ptr ) const {
if ( ptr == NULL )
return 0 ;
else
return 1 + max( subtree_depth(ptr->left) , subtree_depth(ptr->right) ) ;
}
// 清除 ptr 指向的 subtreem, 同時 ptr 設為 NULL
template <typename T>
void BST<T>::erase_subtree( Node<T>* &ptr ) const {
if ( ptr == NULL )
return ;
else {
erase_subtree( ptr->left ) ;
erase_subtree( ptr->right ) ;
delete ptr ;
ptr = NULL ;
}
}
// 複製 q 指向的 subtree 到 ptr
template <typename T>
void BST<T>::copy_subtree( Node<T>* &ptr , const Node<T> *q ) const {
if ( q == NULL ) {
ptr = NULL ;
} else {
ptr = new Node<T>(q->data) ;
copy_subtree( ptr->left , q->left ) ;
copy_subtree( ptr->right , q->right ) ;
}
}
// 由小到大列印 ptr 指向的 subtree 的所有元素
template <typename T>
void BST<T>::list_tree_nodes( const Node<T> *ptr , ostringstream& ostr ) const {
if ( ptr != NULL ) {
list_tree_nodes(ptr->left,ostr) ;
ostr << ptr->data << " " ;
list_tree_nodes(ptr->right,ostr) ;
}
}
// 將 ptr 指向的 subtree 由小到大存入 foo
template <typename T>
void BST<T>::get_tree_nodes( const Node<T> *ptr , vector<T>& foo ) const {
if ( ptr != NULL ) {
get_tree_nodes(ptr->left,foo) ;
foo.push_back(ptr->data) ;
get_tree_nodes(ptr->right,foo) ;
}
}
// 去除根節點
template <typename T>
void BST<T>::delete_root() {
if ( root == NULL ) {
return ;
} else if ( root->is_leaf_node() ) {
delete root ;
root = NULL ;
} else if ( root->left == NULL ) {
Node<T> *p = root ;
root = root->right ;
delete p ;
} else if ( root->right == NULL ) {
Node<T> *p = root ;
root = root->left ;
delete p ;
} else {
Node<T> *q = root ;
Node<T> *p = root->left ;
if ( p->right == NULL ) {
p->right = root->right ;
root = p ;
delete q ;
} else {
q = p ;
p = p->right ;
while ( p->right != NULL ) {
q = p ;
p = p->right ;
}
root->data = p->data ;
delete_non_root_node( p , q ) ;
}
}
}
// 去除非根節點 : p 指向所要去除的節點, q 為 p 的父節點
template <typename T>
void BST<T>::delete_non_root_node ( Node<T>* p , Node<T> *q ) {
if ( p->is_leaf_node() || p->left == NULL ) {
// p is a leaf node or its left pointer is null
if ( q->left == p )
q->left = p->right ;
else
q->right = p->right ;
delete p ;
} else if ( p->left->right == NULL ) {
// p left right pointer is null
if ( q->left == p ) {
q->left = p->left ;
q->left->right = p->right ;
} else {
q->right = p->left ;
q->right->right = p->right ;
}
delete p ;
} else {
Node<T> *r = p ;
q = r->left ;
r = r->left->right ;
while ( r->right != NULL ) {
q = r ;
r = r->right ;
}
p->data = r->data ;
delete_non_root_node( r , q ) ;
}
}
// 去除一筆資料 d
template <typename T>
bool BST<T>::erase_element( const T& d ) {
if ( root == NULL ) {
return false ;
} else if ( root->data == d ) {
delete_root() ;
return true ;
} else {
Node<T> *p = root ;
Node<T> *q ;
while ( p != NULL ) {
if ( p->data == d ) {
delete_non_root_node(p,q) ;
return true ;
} else {
q = p ;
p = ( p->data < d ? p->right : p->left ) ;
}
}
return false ;
}
}
// 複製建構函式
template <typename T>
BST<T>::BST( const BST<T>& foo ) {
if ( foo.root == NULL )
root = NULL ;
else {
root = new Node<T>(foo.root->data) ;
copy_subtree( root , foo.root ) ;
}
}
// 指定運算子
template <typename T>
BST<T>& BST<T>::operator= ( const BST<T>& foo ) {
if ( root == foo.root ) {
return *this ;
} else {
erase_subtree( root ) ;
copy_subtree( root , foo.root ) ;
}
}
// 插入資料 d,
// 若 d 較節點資料值大, 則存入右邊, 否則存入左邊
//
template <typename T>
void BST<T>::insert ( const T& d ) {
Node<T> *tmp = new Node<T>(d) ;
Node<T> *p = root , *q ;
if ( root == NULL )
root = tmp ;
else {
while( p != NULL ) {
q = p ;
p = ( p->data < tmp->data ? p->right : p->left ) ;
}
if ( q->data < tmp->data )
q->right = tmp ;
else
q->left = tmp ;
}
}
// 插入一個元素
template <typename T>
BST<T>& BST<T>::operator+= ( const T& d ) {
insert(d) ;
return *this ;
}
// 由小到大輸出所有元素
template <typename T>
string BST<T>::tree_nodes() const {
ostringstream ostr ;
list_tree_nodes( root , ostr ) ;
return ostr.str() ;
}
// 找尋資料 d, 回傳找到的位置
template <typename T>
const Node<T>* BST<T>::find( const T& d ) const {
Node<T> *p = root ;
while ( p != NULL ) {
if ( p->data == d )
return p ;
else
p = ( p->data < d ? p->right : p->left ) ;
}
return p ;
}
// 去除所有資料 d, 回傳刪除的個數
template <typename T>
int BST<T>::erase( const T& d ) {
int c = 0 ;
while ( erase_element(d) ) ++c ;
return c ;
}
// 去除所有資料 d
template <typename T>
BST<T>& BST<T>::operator-=( const T& d ) {
erase(d) ;
return *this ;
}
// 兩樹合成
template <typename T>
BST<T>& BST<T>::operator+= ( const BST<T>& foo ) {
return *this = *this + foo ;
}
// 兩樹合成
template <typename T>
BST<T> operator+ ( const BST<T>& a , const BST<T>& b ) {
vector<T> nodes ;
b.get_tree_nodes(b.root,nodes) ;
BST<T> sum = a ;
for ( int i = 0 ; i < nodes.size() ; ++i ) sum.insert(nodes[i]) ;
return sum ;
}
// 列印
template <typename T>
ostream& operator<<( ostream& out , const BST<T>& foo ) {
foo.print_subtree( out , foo.root ) ;
return out ;
}
|
輸 出 |
|---|
> foo :
7
|--> 9
|--> .
|--> 9
|--> .
|--> 8
|--> .
|--> 8
|--> 1
|--> 2
|--> 7
|--> .
|--> 0
|--> .
|--> 0
> bar :
8
|--> 10
|--> 11
|--> 12
|--> .
|--> 10
|--> 3
|--> 8
|--> .
|--> 4
|--> 1
|--> 3
|--> .
> c (foo+bar) :
7
|--> 9
|--> 10
|--> 11
|--> 12
|--> .
|--> 10
|--> 9
|--> .
|--> 8
|--> .
|--> 8
|--> .
|--> 8
|--> .
|--> 8
|--> 1
|--> 2
|--> 7
|--> .
|--> 3
|--> 4
|--> 3
|--> .
|--> 0
|--> 1
|--> 0
> bar :
7
|--> 9
|--> 10
|--> 11
|--> 12
|--> .
|--> 10
|--> 9
|--> .
|--> 8
|--> .
|--> 8
|--> .
|--> 8
|--> .
|--> 8
|--> 1
|--> 2
|--> 7
|--> .
|--> 3
|--> 4
|--> 3
|--> .
|--> 0
|--> 1
|--> 0
> elements : 0 0 1 1 2 3 3 4 7 7 8 8 8 8 9 9 10 10 11 12
> element to be deleted : 7
> Nodes of being deleted : 2
4
|--> 9
|--> 10
|--> 11
|--> 12
|--> .
|--> 10
|--> 9
|--> .
|--> 8
|--> .
|--> 8
|--> .
|--> 8
|--> .
|--> 8
|--> 1
|--> 2
|--> 3
|--> .
|--> 3
|--> .
|--> 0
|--> 1
|--> 0
> elements : 0 0 1 1 2 3 3 4 8 8 8 8 9 9 10 10 11 12
> element to be deleted : 8
> Nodes of being deleted : 4
4
|--> 9
|--> 10
|--> 11
|--> 12
|--> .
|--> 10
|--> 9
|--> 1
|--> 2
|--> 3
|--> .
|--> 3
|--> .
|--> 0
|--> 1
|--> 0
> elements : 0 0 1 1 2 3 3 4 9 9 10 10 11 12
....
| |
|