很久不写C++代码了, 最近复习数据结构, 算法.顺便重新写点代码, 把C++的基础找回来, 也实践一下Effective C++中的一些条款.
写了一个二叉搜索树的模板类. 把C++的一些基本知识都用上了, 比如类,模板,重载,引用,指针等等.

一些思考

  • 模板, 除了STL , 实际的程序中有模板到底使用情况如何?
  • 命名风格
  • 注释. C++ 有比较流行的文档注释方式吗?
  • Effective STL 条款21: 尽可能使用const . 这一条我是体会深刻啊.
  • 使用Graphviz 进行可视化还是不错的. 不过有时候还是不够灵活.

下面是代码, 其实里面有很多可以/需要说的地方….

template <class KT>
class Element
{
public:
	typedef KT key_type;
	Element(){}
	Element(KT key){this->_key = key;}
	Element(const Element<KT>& arg){this->_key = arg._key;}
	key_type key()const 
	{
		return this->_key;
	}
private:
	KT _key;
	//maybe something else
};
 
/**
BSTNode 二叉搜索树节点的定义 
DT 应该提供一个操作key(), 返回DT::key_type 类型的一个值 
DT::key_type 类型应该提供 < , == , <= 等比较操作符的实现 
*/ 
template <class DT>
class BSTNode
{
public:
	BSTNode<DT>()
	{
		uid = unique_id();
		left = NULL;
		right = NULL;
 
	}
	int uid;
	BSTNode<DT>* left;
	BSTNode<DT>* right;
	DT data;
	void output_as_dot(ostream& os);
};
 
template <class DT>
void BSTNode<DT>::output_as_dot(ostream& os)
{
	os<<"\tnode"<<this->uid<<"[label=""<<this->data.key()<<""];"<<endl;
	if(this->left != NULL)
	{
		os<<""node"<<this->uid<<"" -> "node"<<this->left->uid<<"";"<<endl;
		this->left->output_as_dot(os);
	}
	else
	{
		int tmp = unique_id();
		os<<"\tnode"<<tmp<<"[label="NIL",shape=box];"<<endl;
		os<<""node"<<this->uid<<"" -> "node"<<tmp<<"";"<<endl;       
	}
	if(this->right != NULL)
	{
		os<<""node"<<this->uid<<"" -> "node"<<this->right->uid<<"";"<<endl;
		this->right->output_as_dot(os);
	}
	else
	{
		int tmp = unique_id();
		os<<"\tnode"<<tmp<<"[label="NIL",shape=box];"<<endl;
		os<<""node"<<this->uid<<"" -> "node"<<tmp<<"";"<<endl;          
	}
}
 
 
template <class DT>
class BST
{
public:
	BST<DT>()
	{
		this->root = NULL;
	}
	DT* search(typename DT::key_type key);
	void output_as_dot(ostream& os);
 
	bool insert(const DT& toadd);
 
	DT* del(typename DT::key_type key);
private:
	void del(BSTNode<DT> * parent,BSTNode<DT> * todel);
 
private:
	BSTNode<DT> * root;
};
 
template <class DT>
DT* BST<DT>::search(typename DT::key_type key)
{
	BSTNode<DT>* node = this->root;
	while(node != NULL)
	{
		if(key == node->data.key())
			return &node->data;
		if(key < node->data.key())
			node = node->left;
		else
			node = node->right;
	}
	return NULL;
}
 
template <class DT>
bool BST<DT>::insert(const DT& toadd)
{
	BSTNode<DT>* node = this->root;
	BSTNode<DT>* p = NULL;
	while(node != NULL)
	{
		p = node;
		if(toadd.key() == node->data.key())
		{
			return false;
		}
		if(toadd.key() < node->data.key())
			node = node->left;
		else
			node = node->right;
	}
 
	BSTNode<DT> * new_node = new BSTNode<DT>();
	new_node->left = new_node->right = NULL;
	new_node->data = toadd;
 
	if (this->root == NULL)
	{
		this->root = new_node;
	}
	else
	{
		if(toadd.key() < p->data.key())
			p->left = new_node;
		else
			p->right = new_node;
	}
	return true;
 
}
 
template <class DT>
void BST<DT>::del(BSTNode<DT> * parent, BSTNode<DT> * todel)
{
	BSTNode<DT> *child;
	if(todel->left == NULL || todel->right == NULL)
	{
		child = todel->left==NULL ? todel->right : todel->left;
	}
	else
	{
		BSTNode<DT> * pc = parent;
		child = todel;
		while(child->left != NULL) 
		{
			pc = child;
			child = child->left;
		}
		pc->left = child->right;    //child为左子数中最小值 
		child->left = todel->left;
		child->right = todel->right;
	}
	if(parent == NULL)
	{
		this->root = child;
	}
	else
	{
		if(parent->left == todel)
			parent->left = child;
		else
			parent->right = child;
	}
 
 
}
 
template <class DT>
DT* BST<DT>::del(typename DT::key_type key)
{
	BSTNode<DT>* node = this->root;
	BSTNode<DT>* p = NULL;
	while(node != NULL && key != node->data.key())
	{
		p = node;
		if(key < node->data.key())
			node = node->left;
		else
			node = node->right;
	}
	if(node == NULL)
	{
		return NULL;
	}
	else
	{
		del(p,node);
		return &node->data;
	}
}
 
template <class DT>
void BST<DT>::output_as_dot(ostream& os)
{
	os<<"digraph G {"<<endl;
	os<<"splines=line;"<<endl;
	root->output_as_dot(os);
	os<<"}"<<endl;
}