天天看点

c/c++开发,无可避免的模板编程实践(篇七)-自定义类模板及运用

一、模板编程慎用

        模板是个好武器,应用得当则四两拔千斤,但应用不慎也容易伤己。对于模板应用,建议优先使用标准库的模板的容器、算法,能用尽用,它是经专业权威的、全面综合的验证过稳定可靠的,而自定函数模板、类模板或模板参数类型尽可能避免。原则是,标准库模板>自定义的普通函数、类>自定义的函数模板、类模板。

        如果确实项目需要用到自定义模板,那建议按需求满足来增加内容,每每对模板内容进行增删时,最好都建立原型测试程序进行验证,并通过组内其他成员一起研讨验证,才可用于实际项目中。

二、自定义模板类型设计

        经过本专栏前面几篇关于模板内容的讲述,本文将就如何自定义模板,并做原型测试就验证来展开阐述。

        假设现在自定义类模板、函数模板实现一个二叉树的创建、插入数据、删除数据、查找数据、遍历二叉树等功能,该二叉树模板支持到标准库的常规数据类型、自定义类型作为模板参数类型。

        2.1 模板文件格式建议

        创建BinaryTree.h/cpp两个源文件用来实现二叉树模板,建议文件格式如下,模板的声明部分放置在头文件,模板的定义部分放置在cpp文件,在头文件的末尾添加#include "***.cpp",即本质上模板的声明定义都是在头文件实现的,只是为了与普通函数、类的声明定义文件格式一致所采取的取巧设计:

/*BinaryTree.h文件*/
#ifndef _BINARY_TREE_H_
#define _BINARY_TREE_H_
//模板声明内容
#include "BinaryTree.cpp"    //尤其注意这里
#endif //_BINARY_TREE_H_

/*--------------------------------------*/
/*BinaryTree.cpp文件*/
#include "BinaryTree.h"
//模板定义内容
           

        2.2 类模板基本设计

        通常实现二叉树都会采用两个类模板,一个节点类型BTNode,是存储节点实际值,并有两个指针分别指向左右子节点,一个树类型BinaryTree,存储树,有一个指针指向根节点,根指针是BTNode*。由于BinaryTree类实际数值是由BTNode类来实现的,因此BinaryTree类常常会涉及到BTNode类内部的数据操作,为了可以直接操作数值,而不用通过函数中转,因此设定BinaryTree类为BTNode类的友元,并将BinaryTree类前置声明,便于在BTNode类内部声明友元时,能找到其声明(名称)。

template <typename T> class BinaryTree;//前置声明

template <typename T>
class BTNode
{
	public:

	private:
	T 	t_val;
	int i_cnt;
	BTNode* node_lchild;
	BTNode* node_rchild;
};

template <typename T>
class BinaryTree
{
	public:

	private:
	BTNode<T> *tree_root;
};
           

        在自定义类时,基本的成员函数如构造函数、拷贝构造函数、析构函数、赋值函数这是最基本的,需要及时添加进来。

template <typename T> class BinaryTree;//前置声明

template <typename T>
class BTNode
{
	public:
    BTNode(const T&);
	~BTNode();

	private:
	T 	t_val;
	int i_cnt;
	BTNode* node_lchild;
	BTNode* node_rchild;
};

template <typename T>
class BinaryTree
{
	public:
    BinaryTree();
	BinaryTree(const BinaryTree&);
	~BinaryTree();
	BinaryTree& operator=(const BinaryTree&);

	private:
	BTNode<T> *tree_root;
};
           

        建议所有成员函数的定义都放置在.cpp源文件内实现,这类模板的基本成员函数实现和普通类的成员函数定义区别就在于定义是,需要附带模板声明。

#include "BinaryTree.h"

template <typename T>
inline BTNode<T>::BTNode(const T& val) : t_val(val)
{
	i_cnt = 1;
	node_lchild = node_rchild = 0;
};

template <typename T>
inline BTNode<T>::~BTNode()
{
	
};

//
template <typename T>
inline BinaryTree<T>::BinaryTree() : tree_root(0)
{
	min_node = max_node = nullptr;
};

template <typename T>
inline BinaryTree<T>::BinaryTree(const BinaryTree& rhs) : tree_root(0)
{
    min_node = max_node = nullptr;
    //mycode for later do it
};

template <typename T>
inline BinaryTree<T>::~BinaryTree()
{
	//mycode for later do it
};

template <typename T>
inline BinaryTree<T>& 
BinaryTree<T>::operator=(const BinaryTree& rhs)
{
	//mycode for later do it
	return *this;
};
           

        将基本成员函数定义完成,其实类模板就可以使用了,虽然暂时没提供什么操作。可以定义个BinaryTree来编译测试一下是否可行,main.cpp:

#include "BinaryTree.h"

int main(int argc, char* argv[])
{
    BinaryTree<int> btree_test;
    return 0;
}
           

        2.3 为基本成员函数完善实现

        一般来说,类的基本成员函数如构造、析构这些,其实现内容都不复杂,因此建议优先需要其基本功能完善一下才进行实际功能的添加,为此按需增加一些辅助成员函数如empty、clear、copy等,来实现这些基本成员函数。需要注意几点:构造函数注意初始化相关成员变量,能列表初始化的就优先采用列表初始化;拷贝、赋值函数禁止赋值自身是必要的,应作为习惯记住。

//BinaryTree.h
template <typename T>
class BinaryTree
{
	public:
	BinaryTree();
	BinaryTree(const BinaryTree&);
	~BinaryTree();
	BinaryTree& operator=(const BinaryTree&);
	
	bool empty();    //根节点是否为空
	void clear();    //删除节点及内容
	
	private:
	BTNode<T> *tree_root;
	void copy(BTNode<T> *src);    //拷贝数据
	void clear(BTNode<T> *pnode); //删除某节点下的节点及数据
};


//BinaryTree.cpp
template <typename T>
inline BinaryTree<T>::BinaryTree() : tree_root(0)    //默认构造
{
	min_node = max_node = nullptr;
};

template <typename T>
inline BinaryTree<T>::BinaryTree(const BinaryTree& rhs) : tree_root(0) //拷贝构造
{
	min_node = max_node = nullptr;
	copy(rhs.tree_root);
};

template <typename T>
inline BinaryTree<T>::~BinaryTree()    //析构
{
	clear();
};

template <typename T>
inline BinaryTree<T>& 
BinaryTree<T>::operator=(const BinaryTree& rhs)    //赋值
{
	if(this==&rhs)    //赋值函数禁止赋值自身是必要的,应作为习惯记住
		return *this;
	clear();
	copy(rhs.tree_root);
	return *this;
};

template <typename T>
inline bool BinaryTree<T>::empty()    //根节点是否为空
{
	if(0==tree_root)
		return false;
	else
		return true;
};

template <typename T>
inline void BinaryTree<T>::clear()   //清除树
{
	if (tree_root)
	{
		clear(tree_root);
	}
	tree_root = 0;
	min_node = max_node = nullptr;
};

template <typename T>
void BinaryTree<T>::clear(BTNode<T> *pnode)//清除某节点
{
	if(pnode)
	{
		clear(pnode->node_lchild);
		clear(pnode->node_rchild);
		delete pnode;
	}
};

template <typename T>
void BinaryTree<T>::copy(BTNode<T> *src)//赋值内容到本对象
{
	if(0==tree_root)
	{
		tree_root = new BTNode<T>(src->t_val);
	}else{
		tree_root->insert_value(src->t_val);//添加数据
	}
	if(src->node_lchild)
	{
		copy(src->node_lchild);
	}
	if(src->node_rchild)
	{
		copy(src->node_rchild);
	}
}
           

        2.4 二叉树增删数据

        上述代码调用了一个未知函数,insert_value,这是用来给二叉树插入数据的成员函数。对于二叉树来说,首先要实现的就是添加数据和删除数,第一个数据添加时,往往作为根节点的值,其后添加的数值,原则从根节点开始遍历,与节点数据进行比较,比节点数值小的放置节点的左子树下,比节点数值大的放置节点的右子树下,如果和节点数值相等就节点计数+1。二叉树的机构特性决定了它们的很多功能(插入、删除、查找、遍历等)实现都是通过递归遍历来实现的。

//BinaryTree.h
template <typename T>
class BTNode
{
	public:
    ...
	void insert_value(const T&);
	...
};

template <typename T>
class BinaryTree
{
	public:
    ...
	void insert(const T&);
    ...
};

//BinaryTree.cpp
template <typename T>
void BTNode<T>::insert_value(const T& val)
{
	if(val==t_val)
	{
		i_cnt++;
		return;
	}
	if(val<t_val)
	{
		if(!node_lchild)
		{
			node_lchild = new BTNode<T>(val);
		}else
		{
			node_lchild->insert_value(val);
		}
	}else{
		if(!node_rchild)
		{
			node_rchild = new BTNode<T>(val);
		}else
		{
			node_rchild->insert_value(val);
		}
	}
};

template <typename T>
inline void BinaryTree<T>::insert(const T& val)
{
	if(!tree_root)
	{
		tree_root = new BTNode<T>(val);
	}else{
		tree_root->insert_value(val);
	}
	set_MinMaxNode();
};
           

        删除指定数据会复杂些,先需要递归找到要删除的数据,在删除时,先需要将被删除的节点的右节点取代被删节点,然后搬移原来的左子树到新取代节点的叶节点(无左子节点)上,若新取代节点上无左节点,原来的左子树直接添加为新取代节点左子树即可,否则需要找到新取代节点下的最左子叶节点再添加。根节点删除类似,只是根节点是起始位置,因此需要特殊处理一下。

//BinaryTree.h
template <typename T>
class BTNode
{
	public:
    ...
	void remove_value(const T&val, BTNode*& prev_node);
    void lchild_leaf(BTNode* leaf, BTNode* subtree);
	...
};

template <typename T>
class BinaryTree
{
	public:
    ...
	void remove(const T&);
    ...
    private:
    void remove_root();
};

//BinaryTree.cpp

template <typename T>
void BTNode<T>::remove_value(const T&val, BTNode*& prev_node)
{
	if(val<t_val)
	{
		if(!node_lchild)
		{
			return;//不在左子树中
		}else{
			node_lchild->remove_value(val,node_lchild);
		}
	}else{
		if (val>t_val)
		{
			if(!node_rchild)
			{
				return;//不在右子树中
			}else{
				node_rchild->remove_value(val,node_rchild);
			}
		}else{
			//val==t_val,匹配到节点
			if(node_rchild)//右子节点存在
			{
				prev_node = node_rchild;	//前置节点换成右子节点
				if(node_lchild)	//右子节点存在,并左子节点存在
				{
					if(!prev_node->node_lchild)
					{
						prev_node->node_lchild = node_lchild;
					}else{
						prev_node->lchild_leaf(node_lchild,prev_node->node_lchild);
					}
				}
			}else{
				prev_node = node_lchild;//前置节点换成左子节点
			}
			delete this;//删除该节点
		}
	}
}

template <typename T>
void BTNode<T>::lchild_leaf(BTNode* leaf, BTNode* subtree)//将指定节点leaf插入到节点树subtree下
{
	while (subtree->node_lchild)
	{
		subtree = subtree->node_lchild;
	}
	subtree->node_lchild = leaf;
}

template <typename T>
inline void BinaryTree<T>::remove(const T& val)
{
	if(tree_root)
	{
		if(tree_root->t_val==val)
		{
			remove_root();
		}else{
			tree_root->remove_value(val,tree_root);
		}
	}
}

template <typename T>
void BinaryTree<T>::remove_root()	//删除根节点
{
	if (!tree_root)
	{
		return;
	}
	BTNode<T> *tmp_node = tree_root;
	if (tree_root->node_rchild)
	{
		tree_root = tree_root->node_rchild;	//根节点换成右子节点
		//将左子树搬移到右子节点的左子树的最底部
		if(tmp_node->node_lchild)
		{
			BTNode<T> *l_child = tmp_node->node_lchild;
			BTNode<T> *new_l_child = tree_root->node_lchild;
			if(!new_l_child)
			{
				tree_root->node_lchild = l_child;
			}else{
				//遍历左子树,寻找可以挂接的空左子节点
				tree_root->lchild_leaf(l_child,new_l_child);
			}
		}
	}else{
		tree_root = tree_root->node_lchild;	//根节点换成左子节点
	}
	delete tmp_node;//删除先前的根节点
}
           

        通过上述代码后,就可以向建设后的树对象插入数据或删除数据,也可以调用拷贝构造函数。

//main.cpp
    int i_v[] = {6,3,5,9,3,8};
	BinaryTree<int> iptree;
	for (int i=0; i<sizeof(i_v)/sizeof(int); i++)
	{
		iptree.insert(i_v[i]);
	}

//拷贝构造
	BinaryTree<int> icpytree(iptree);
// 删除测试
	icpytree.remove(5);
           

        2.5 二叉树遍历及打印输出

        二叉树一般有三种遍历树的方法,分别是前置遍历、中置遍历、后置遍历,都是以根节点为起点,通过递归实现遍历的。区别就在于节点内容打印输出先后次序不同:前置遍历是指被遍历的节点本身先被打印,然后才打印做左子树内容,后面才轮到右子树内容;中置遍历就是先打印做子树内容,然后是节点本身,最后轮到右子树内容;后置遍历就是先打印左子树内容,然后打印出右子树内容,最后才是节点本身。本文借助ostream重定义BinaryTree类的operator<<操作符,实现前置遍历、中置遍历、后置遍历打印输出到屏幕。

//BinaryTree.h
template <typename T>
class BinaryTree
{
	public:
    ...
	void os_out(std::ostream &os);
	void pre_order(BTNode<T> *pnode,std::ostream &os);
	void in_order(BTNode<T> *pnode,std::ostream &os);
	void post_order(BTNode<T> *pnode,std::ostream &os);

    template <typename T1>
	friend std::ostream& operator<<(std::ostream &os,const BinaryTree<T1> &obj);
    ...
	private:
    ...
	void display_val(BTNode<T> *pnode,std::ostream &os);
};

template <typename T>
inline std::ostream& operator<<(std::ostream &os, BinaryTree<T> &obj);

//BinaryTree.cpp
template <typename T>
void BinaryTree<T>::os_out(std::ostream &os)
{
	os<< "pre_order:";
	pre_order(tree_root,os);
	os << "\n";
	os<< "in_order:";
	in_order(tree_root,os);
	os << "\n";
	os<< "post_order:";
	post_order(tree_root,os);
	os << "\n";
}

template <typename T>
void BinaryTree<T>::pre_order(BTNode<T> *pnode, std::ostream &os) 
{
	if(pnode)
	{
		display_val(pnode,os);
		if(pnode->node_lchild)
		{
			pre_order(pnode->node_lchild,os);
		}
		if(pnode->node_rchild)
		{
			pre_order(pnode->node_rchild,os);
		}
	}
}

template <typename T>
void BinaryTree<T>::in_order(BTNode<T> *pnode, std::ostream &os) 
{
	if(pnode)
	{
		if(pnode->node_lchild)
		{
			in_order(pnode->node_lchild,os);
		}
		display_val(pnode,os);
		if(pnode->node_rchild)
		{
			in_order(pnode->node_rchild,os);
		}
	}
}
	
template <typename T>
void BinaryTree<T>::post_order(BTNode<T> *pnode, std::ostream &os) 
{
	if(pnode)
	{
		if(pnode->node_lchild)
		{
			post_order(pnode->node_lchild,os);
		}
		if(pnode->node_rchild)
		{
			post_order(pnode->node_rchild,os);
		}
		display_val(pnode,os);
	}
}

template <typename T>
void BinaryTree<T>::display_val(BTNode<T> *pnode,std::ostream &os)
{
	if(pnode)
	{
		os <<"("<<pnode->i_cnt<<","<<pnode->t_val<<")";
	}
}

template <typename T>
inline std::ostream& operator<<(std::ostream &os,BinaryTree<T> &obj)
{
	os << "tree:" << std::endl;
	obj.os_out(os);
	return os;
};
           

        这样就可以打印输出显示了:

//main.cpp
    int i_v[] = {6,3,5,9,3,8};
	BinaryTree<int> iptree;
	for (int i=0; i<sizeof(i_v)/sizeof(int); i++)
	{
		iptree.insert(i_v[i]);
	}

	std::cout << iptree;	//三序遍历输出
           

        2.6 二叉树查找数据

        下来就是数据查找,本质上和数据插入、删除、遍历打印的查找一样,是通过递归变量节点来完成的。

//BinaryTree.h
template <typename T>
class BTNode
{
	public:
    ...
	BTNode* find(const T&);
};

template <typename T>
class BinaryTree
{
	public:
    ...
	BTNode<T> * find(const T&);
    ...
};

//BinaryTree.cpp
template <typename T>
BTNode<T>* BTNode<T>::find(const T&val)
{
	if(val==this->t_val)
	{
		return this;
	}else{
		if(val<this->t_val&&this->node_lchild)
		{
			return this->node_lchild->find(val);
		}
		if(val>this->t_val&&this->node_rchild)
		{
			return this->node_rchild->find(val);
		}
	}
	return nullptr;
}

template <typename T>
BTNode<T> * BinaryTree<T>::find(const T&val)
{
	if(!tree_root)
	{
		return nullptr;
	}
	return tree_root->find(val);
}
           

        从前面的代码中可以归纳出二叉树类模板功能实现特点及规律,由于操作都是从根节点开始进行遍历的,因此插入、删除、查找、遍历等功能,BinaryTree类只提供入口操作,真正实现还是跳转调用BTNode类的功能函数来完成的。

        2.7 二叉树比较及子树匹配

        接下来在提供一些二叉树分常规需要的一些功能来看看扩大模板的一些知识点运用,添加比较两个树的功能和在一个二叉树查找匹配子树的功能,先匹配根节点是否OK,OK的话,再递归遍历左、右子树去逐层比较:

//BinaryTree.h
template <typename T>
class BTNode
{
	public:
	...
	template <typename T1>
	friend bool  is_samenode(BTNode<T1> *obj1, BTNode<T1> *obj2);
	template <typename T1>
	friend bool  is_subnode(BTNode<T1> *pnode, BTNode<T1> *cnode);
	template <typename T1>
	friend bool  is_same_subnode(BTNode<T1> *pnode, BTNode<T1> *cnode);
    ...
};

template <typename T>
bool  is_samenode(BTNode<T> *obj1, BTNode<T> *obj2);//两个节点及子节点是否相同
template <typename T>
bool  is_subnode(BTNode<T> *pnode, BTNode<T> *cnode);//pnode是否包含cnode
template <typename T>
bool  is_same_subnode(BTNode<T> *pnode, BTNode<T> *cnode);//辅助函数

template <typename T>
class BinaryTree
{
	public:
    ...
	template <typename T1>
	friend bool  is_sametree(BinaryTree<T1> *obj1, BinaryTree<T1> *obj2);
	template <typename T1>
	friend bool  is_subtree(BinaryTree<T1> *pnode, BinaryTree<T1> *cnode);
    ...
};

template <typename T>
bool  is_sametree(BinaryTree<T> *obj1, BinaryTree<T> *obj2);//两个节点树是否相同
template <typename T>
bool  is_subtree(BinaryTree<T> *ptree, BinaryTree<T> *ctree);//ptree树是否包含ctree树

//BinaryTree.cpp

template <typename T>
bool  is_samenode(BTNode<T> *obj1, BTNode<T> *obj2)
{
	if((nullptr==obj1&&nullptr!=obj2)
		||(nullptr!=obj1&&nullptr==obj2))
	{
		return false;
	}
	if(nullptr==obj1&&nullptr==obj2)//都为空也OK
	{
		return true;
	}
	//值与数量是否相等
	if(obj1->t_val!=obj2->t_val||obj1->i_cnt!=obj2->i_cnt)
	{
		return false;
	}else{//值和值数量相等,继续下层
		return is_samenode(obj1->node_lchild,obj2->node_lchild)
			&&is_samenode(obj1->node_rchild,obj2->node_rchild);
	}
}

template <typename T>
bool  is_subnode(BTNode<T> *pnode, BTNode<T> *cnode)
{
	bool ret = false;
	if(nullptr!=pnode&&nullptr!=cnode)
	{
		if(pnode->t_val==cnode->t_val)
		{
			ret = is_same_subnode(pnode,cnode);
		}
		if(!ret)
		{
			ret = is_subnode(pnode->node_lchild,cnode);
		}
		if(!ret)
		{
			ret = is_subnode(pnode->node_rchild,cnode);
		}
	}
	return ret;
}

template <typename T>
bool  is_same_subnode(BTNode<T> *pnode, BTNode<T> *cnode)
{
	if(nullptr==cnode)
	{
		return true;
	}
	if(nullptr==pnode)
	{
		return false;
	}
	//值是否相等,父节点值数量不少于子节点
	if(pnode->t_val!=cnode->t_val||pnode->i_cnt<cnode->i_cnt)
	{
		return false;
	}else{
		return is_same_subnode(pnode->node_lchild,cnode->node_lchild)
			&&is_same_subnode(pnode->node_rchild,cnode->node_rchild);
	}
}
           

        原型测试一下:

int i_v[] = {6,3,5,9,3,8};
	BinaryTree<int> iptree;
	for (int i=0; i<sizeof(i_v)/sizeof(int); i++)
	{
		iptree.insert(i_v[i]);
	}
	std::cout << iptree;	//三序遍历输出
//
    BinaryTree<int> ictree;
	for (int i=0; i<sizeof(i_v)/sizeof(int); i++)
	{
		ictree.insert(i_v[i]);
	}
	std::cout << ictree;//三序遍历输出

    //比对测试
	std::cout << "is_sametree(&iptree,&ictree)?"<< (is_sametree(&iptree,&ictree)) << std::endl;
	std::cout << "is_subtree(&iptree,&ictree)?"<< (is_subtree(&iptree,&ictree)) << std::endl;
	iptree.insert(5);
	std::cout << "is_sametree(&iptree,&ictree)?"<< (is_sametree(&iptree,&ictree)) << std::endl;
	std::cout << "is_subtree(&iptree,&ictree)?"<< (is_subtree(&iptree,&ictree)) << std::endl;
	iptree.insert(10);
	std::cout << "is_sametree(&iptree,&ictree)?"<< (is_sametree(&iptree,&ictree)) << std::endl;
	std::cout << "is_subtree(&iptree,&ictree)?"<< (is_subtree(&iptree,&ictree)) << std::endl;
           

        2.8 节点别名-iterator

        在标准库中,容器会提供迭代器指向支持,二叉树虽然因为其结构特性一般不会迭代器操作,但是本文可以类迭代器提供一下节点指针的别名-iterator。

//BinaryTree.h
template <typename T>
class BTNode
{
	public:
    ...
	protected:
	BTNode* getMinNode(BTNode* ) const;    //获取最小值的节点
	BTNode* getMaxNode(BTNode* ) const;    //获取最大值的节点
	BTNode* getPNode(BTNode*) const;       //获取该节点的父节点
    ...
};

template <typename T>
class BinaryTree
{
	public:
    ..
	typedef BTNode<T>	value_type;
	typedef value_type* iterator;   //本质就是指针,指向BTNode<T>	*     

	iterator get_first() const;    //获取最小值的节点
	iterator get_last() const;    //获取最大值的节点
	iterator get_parent(iterator child) const;//获取该节点的父节点
	protected:
	iterator min_node;//最小值的节点的缓存
	iterator max_node;//最大值的节点的缓存
    private:
    void set_MinMaxNode();    //每次内容变更时调用,刷新min_node和max_node
    ...
};

//BinaryTree.cpp

template <typename T>
inline BTNode<T>* BTNode<T>::getMinNode(BTNode* pnode) const
{
	if(!pnode->node_lchild)
	{
		return const_cast<BTNode<T>*>(pnode);
	}else{
		return pnode->node_lchild->getMinNode(pnode->node_lchild);
	}
}

template <typename T>
inline BTNode<T>* BTNode<T>::getMaxNode(BTNode* pnode) const
{
	if(!pnode->node_rchild)
	{
		return const_cast<BTNode<T>*>(pnode);
	}else{
		return pnode->node_rchild->getMaxNode(pnode->node_rchild);
	}
};

template <typename T>
inline BTNode<T>* BTNode<T>::getPNode(BTNode<T>* child) const
{
	if(this->node_lchild==child||this->node_rchild==child)
	{
		return const_cast<BTNode<T>*>(this);
	}else{
		BTNode<T>* retsult = nullptr;
		if(this->node_lchild)
		{
			retsult = this->node_lchild->getPNode(child);
		}
		if(nullptr!=retsult)
			return retsult;
		if(this->node_rchild)
		{
			retsult = this->node_rchild->getPNode(child);
		}
		return retsult;
	}
}

template <typename T>
inline typename BinaryTree<T>::iterator BinaryTree<T>::get_first() const
{
	return min_node;
}

template <typename T>
inline typename BinaryTree<T>::iterator BinaryTree<T>::get_last() const
{
	return max_node;
}

template <typename T>
typename BinaryTree<T>::iterator BinaryTree<T>::get_parent(typename BinaryTree<T>::iterator child) const
{
	if(!this->tree_root)
	{
		return nullptr;
	}else{
		return (BinaryTree<T>::iterator)(this->tree_root->getPNode(child));
	}
}

template <typename T>
inline void BinaryTree<T>::set_MinMaxNode()
{
	if(!tree_root)
	{
		min_node = max_node = nullptr;
	}else{
		min_node = tree_root->getMinNode(tree_root);
		max_node = tree_root->getMaxNode(tree_root);
	}
}
           

        同样对这些功能进行测试:

std::cout <<"iptree min_val = " << iptree.get_first()->get_val()<< std::endl;//获取最小值节点
	std::cout <<"iptree max_val = " << iptree.get_last()->get_val()<< std::endl;//获取最大值节点
	BTNode<int> *node = iptree.find(5);	//查找
	if(nullptr!=node)
	{
		std::cout <<"find:"<< node->get_cnt()<< "," << node->get_val() << std::endl;
	}
	node = iptree.get_parent(node);//获取父节点
	if(nullptr!=node)
	{
		std::cout <<"get_parent:"<< node->get_cnt()<< "," << node->get_val() << std::endl;
	}
	node = iptree.get_parent(iptree.get_first());
	if(nullptr!=node)
	{
		std::cout <<"get_parent:"<< node->get_cnt()<< "," << node->get_val() << std::endl;
	}
	node = iptree.get_parent(iptree.get_last());
	if(nullptr!=node)
	{
		std::cout <<"get_parent:"<< node->get_cnt()<< "," << node->get_val() << std::endl;
	}
           

       2.9 自定义类型作为二叉树模板参数类型

         最后,在看看采用自定义类型作为BinaryTree类模板的模板参数类型是否可行:

//KeyObj.h,自定义数据类型,给出了比较操作符合,定义了operator<<输出操作
class KeyObj
{
public:
	KeyObj(int pid,int cid):p_id(pid),c_id(cid){};
	//
	static int cmp_Key(const KeyObj &obj1, const KeyObj &obj2)
    {
        int diff = obj1.p_id - obj2.p_id;
	    if (diff != 0) 		
            return diff;
	    diff = obj1.c_id - obj2.c_id;
	    if (diff != 0) 		
            return diff;
	    return 0;
    };

	int	p_id;
	int c_id;
private:
};
inline bool operator==(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) == 0; }
inline bool operator!=(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) != 0; }
inline bool operator>=(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) >= 0; }
inline bool operator<=(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) <= 0; }
inline bool operator>(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) > 0; }
inline bool operator<(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) < 0; }

inline std::ostream &operator<<(std::ostream &os, const KeyObj& obj)
{
	os << "(";
	os << obj.p_id << "," << obj.c_id;
	os <<")";
	return os;
};

//main.cpp
//自定义类型作为模板参数类型
	BinaryTree<KeyObj> itree_KeyObj;
	KeyObj vkey[6]={KeyObj(2,3),KeyObj(2,5),KeyObj(1,3),KeyObj(3,2),KeyObj(4,3),KeyObj(1,5)};
	for (int i=0; i<6; i++)
	{
		itree_KeyObj.insert(vkey[i]);
	}
	std::cout << itree_KeyObj;
           

三、编译、测试及源代码

        3.1 编译及测试

        本案例包含BinaryTree.h、BinaryTree.cpp、KeyObj.h、main.cpp四个源文件,放置同一目录下,采用命令g++ main.cpp -o test.exe编译程序:

c/c++开发,无可避免的模板编程实践(篇七)-自定义类模板及运用

         3.2 源代码

        BinaryTree.h

#ifndef _BINARY_TREE_H_
#define _BINARY_TREE_H_
#include <ostream>
#include <iostream>

template <typename T> class BinaryTree;//前置声明

template <typename T>
class BTNode
{
	public:
	BTNode(const T&);
	~BTNode();
	void insert_value(const T&);
	void remove_value(const T&val, BTNode*& prev_node);
	BTNode* find(const T&);
	void lchild_leaf(BTNode* leaf, BTNode* subtree);
	T get_val() const;
	int get_cnt() const;

	friend class BinaryTree<T>;
	template <typename T1>
	friend bool  is_samenode(BTNode<T1> *obj1, BTNode<T1> *obj2);
	template <typename T1>
	friend bool  is_subnode(BTNode<T1> *pnode, BTNode<T1> *cnode);
	template <typename T1>
	friend bool  is_same_subnode(BTNode<T1> *pnode, BTNode<T1> *cnode);
	protected:
	BTNode* getMinNode(BTNode* ) const;
	BTNode* getMaxNode(BTNode* ) const;
	BTNode* getPNode(BTNode*) const;
	private:
	T 	t_val;
	int i_cnt;
	BTNode* node_lchild;
	BTNode* node_rchild;
};

template <typename T>
bool  is_samenode(BTNode<T> *obj1, BTNode<T> *obj2);
template <typename T>
bool  is_subnode(BTNode<T> *pnode, BTNode<T> *cnode);
template <typename T>
bool  is_same_subnode(BTNode<T> *pnode, BTNode<T> *cnode);

template <typename T>
class BinaryTree
{
	public:
	BinaryTree();
	BinaryTree(const BinaryTree&);
	~BinaryTree();
	BinaryTree& operator=(const BinaryTree&);
	
	bool empty();
	void clear();
	void insert(const T&);
	void remove(const T&);
	BTNode<T> * find(const T&);

	void os_out(std::ostream &os);
	void pre_order(BTNode<T> *pnode,std::ostream &os);
	void in_order(BTNode<T> *pnode,std::ostream &os);
	void post_order(BTNode<T> *pnode,std::ostream &os);

	template <typename T1>
	friend std::ostream& operator<<(std::ostream &os,const BinaryTree<T1> &obj);
	template <typename T1>
	friend bool  is_sametree(BinaryTree<T1> *obj1, BinaryTree<T1> *obj2);
	template <typename T1>
	friend bool  is_subtree(BinaryTree<T1> *pnode, BinaryTree<T1> *cnode);
	public:
	typedef BTNode<T>	value_type;
	typedef value_type* iterator;

	iterator get_first() const;
	iterator get_last() const;
	iterator get_parent(iterator child) const;
	protected:
	iterator min_node;
	iterator max_node;
	private:
	BTNode<T> *tree_root;
	void copy(BTNode<T> *src);
	void remove_root();
	void clear(BTNode<T> *pnode);
	void set_MinMaxNode();
	void display_val(BTNode<T> *pnode,std::ostream &os);
};

template <typename T>
inline std::ostream& operator<<(std::ostream &os, BinaryTree<T> &obj);
template <typename T>
bool  is_sametree(BinaryTree<T> *obj1, BinaryTree<T> *obj2);
template <typename T>
bool  is_subtree(BinaryTree<T> *ptree, BinaryTree<T> *ctree);

#include "BinaryTree.cpp"
#endif //_BINARY_TREE_H_
           

        BinaryTree.cpp

#include "BinaryTree.h"

template <typename T>
inline BTNode<T>::BTNode(const T& val) : t_val(val)
{
	i_cnt = 1;
	node_lchild = node_rchild = 0;
};

template <typename T>
inline BTNode<T>::~BTNode()
{
	
};

template <typename T>
void BTNode<T>::insert_value(const T& val)
{
	if(val==t_val)
	{
		i_cnt++;
		return;
	}
	if(val<t_val)
	{
		if(!node_lchild)
		{
			node_lchild = new BTNode<T>(val);
		}else
		{
			node_lchild->insert_value(val);
		}
	}else{
		if(!node_rchild)
		{
			node_rchild = new BTNode<T>(val);
		}else
		{
			node_rchild->insert_value(val);
		}
	}
};

template <typename T>
void BTNode<T>::remove_value(const T&val, BTNode*& prev_node)
{
	if(val<t_val)
	{
		if(!node_lchild)
		{
			return;//不在左子树中
		}else{
			node_lchild->remove_value(val,node_lchild);
		}
	}else{
		if (val>t_val)
		{
			if(!node_rchild)
			{
				return;//不在右子树中
			}else{
				node_rchild->remove_value(val,node_rchild);
			}
		}else{
			//val==t_val,匹配到节点
			if(node_rchild)//右子节点存在
			{
				prev_node = node_rchild;	//前置节点换成右子节点
				if(node_lchild)	//右子节点存在,并左子节点存在
				{
					if(!prev_node->node_lchild)
					{
						prev_node->node_lchild = node_lchild;
					}else{
						prev_node->lchild_leaf(node_lchild,prev_node->node_lchild);
					}
				}
			}else{
				prev_node = node_lchild;//前置节点换成左子节点
			}
			delete this;//删除该节点
		}
	}
}

template <typename T>
BTNode<T>* BTNode<T>::find(const T&val)
{
	if(val==this->t_val)
	{
		return this;
	}else{
		if(val<this->t_val&&this->node_lchild)
		{
			return this->node_lchild->find(val);
		}
		if(val>this->t_val&&this->node_rchild)
		{
			return this->node_rchild->find(val);
		}
	}
	return nullptr;
}

template <typename T>
T BTNode<T>::get_val() const
{
	return t_val;
}

template <typename T>
int BTNode<T>::get_cnt() const
{
	return i_cnt;
}

template <typename T>
void BTNode<T>::lchild_leaf(BTNode* leaf, BTNode* subtree)//将指定节点leaf插入到节点树subtree下
{
	while (subtree->node_lchild)
	{
		subtree = subtree->node_lchild;
	}
	subtree->node_lchild = leaf;
}

template <typename T>
bool  is_samenode(BTNode<T> *obj1, BTNode<T> *obj2)
{
	if((nullptr==obj1&&nullptr!=obj2)
		||(nullptr!=obj1&&nullptr==obj2))
	{
		return false;
	}
	if(nullptr==obj1&&nullptr==obj2)
	{
		return true;
	}
	//值与数量是否相等
	if(obj1->t_val!=obj2->t_val||obj1->i_cnt!=obj2->i_cnt)
	{
		return false;
	}else{//值和值数量相等
		return is_samenode(obj1->node_lchild,obj2->node_lchild)
			&&is_samenode(obj1->node_rchild,obj2->node_rchild);
	}
}

template <typename T>
bool  is_subnode(BTNode<T> *pnode, BTNode<T> *cnode)
{
	bool ret = false;
	if(nullptr!=pnode&&nullptr!=cnode)
	{
		if(pnode->t_val==cnode->t_val)
		{
			ret = is_same_subnode(pnode,cnode);
		}
		if(!ret)
		{
			ret = is_subnode(pnode->node_lchild,cnode);
		}
		if(!ret)
		{
			ret = is_subnode(pnode->node_rchild,cnode);
		}
	}
	return ret;
}

template <typename T>
bool  is_same_subnode(BTNode<T> *pnode, BTNode<T> *cnode)
{
	if(nullptr==cnode)
	{
		return true;
	}
	if(nullptr==pnode)
	{
		return false;
	}
	//值是否相等,父节点值数量不少于子节点
	if(pnode->t_val!=cnode->t_val||pnode->i_cnt<cnode->i_cnt)
	{
		return false;
	}else{
		return is_same_subnode(pnode->node_lchild,cnode->node_lchild)
			&&is_same_subnode(pnode->node_rchild,cnode->node_rchild);
	}
}

template <typename T>
inline BTNode<T>* BTNode<T>::getMinNode(BTNode* pnode) const
{
	if(!pnode->node_lchild)
	{
		return const_cast<BTNode<T>*>(pnode);
	}else{
		return pnode->node_lchild->getMinNode(pnode->node_lchild);
	}
}

template <typename T>
inline BTNode<T>* BTNode<T>::getMaxNode(BTNode* pnode) const
{
	if(!pnode->node_rchild)
	{
		return const_cast<BTNode<T>*>(pnode);
	}else{
		return pnode->node_rchild->getMaxNode(pnode->node_rchild);
	}
};

template <typename T>
inline BTNode<T>* BTNode<T>::getPNode(BTNode<T>* child) const
{
	if(this->node_lchild==child||this->node_rchild==child)
	{
		return const_cast<BTNode<T>*>(this);
	}else{
		BTNode<T>* retsult = nullptr;
		if(this->node_lchild)
		{
			retsult = this->node_lchild->getPNode(child);
		}
		if(nullptr!=retsult)
			return retsult;
		if(this->node_rchild)
		{
			retsult = this->node_rchild->getPNode(child);
		}
		return retsult;
	}
}
//
template <typename T>
inline BinaryTree<T>::BinaryTree() : tree_root(0)
{
	min_node = max_node = nullptr;
};

template <typename T>
inline BinaryTree<T>::BinaryTree(const BinaryTree& rhs): tree_root(0)
{
	min_node = max_node = nullptr;
	copy(rhs.tree_root);
	set_MinMaxNode();
};

template <typename T>
inline BinaryTree<T>::~BinaryTree()
{
	clear();
};

template <typename T>
inline BinaryTree<T>& 
BinaryTree<T>::operator=(const BinaryTree& rhs)
{
	if(this==&rhs)
		return *this;
	clear();
	copy(rhs.tree_root);
	return *this;
};

template <typename T>
inline bool BinaryTree<T>::empty()
{
	if(0==tree_root)
		return false;
	else
		return true;
};

template <typename T>
inline void BinaryTree<T>::clear()
{
	if (tree_root)
	{
		clear(tree_root);
	}
	tree_root = 0;
	min_node = max_node = nullptr;
};

template <typename T>
void BinaryTree<T>::clear(BTNode<T> *pnode)
{
	if(pnode)
	{
		clear(pnode->node_lchild);
		clear(pnode->node_rchild);
		delete pnode;
	}
};

template <typename T>
inline void BinaryTree<T>::insert(const T& val)
{
	if(!tree_root)
	{
		tree_root = new BTNode<T>(val);
	}else{
		tree_root->insert_value(val);
	}
	set_MinMaxNode();
};

template <typename T>
inline void BinaryTree<T>::remove(const T& val)
{
	if(tree_root)
	{
		if(tree_root->t_val==val)
		{
			remove_root();
		}else{
			tree_root->remove_value(val,tree_root);
		}
	}
	set_MinMaxNode();
}

template <typename T>
void BinaryTree<T>::copy(BTNode<T> *src)
{
	if(0==tree_root)
	{
		tree_root = new BTNode<T>(src->t_val);
	}else{
		tree_root->insert_value(src->t_val);
	}
	if(src->node_lchild)
	{
		copy(src->node_lchild);
	}
	if(src->node_rchild)
	{
		copy(src->node_rchild);
	}
}

template <typename T>
void BinaryTree<T>::remove_root()	//删除根节点
{
	if (!tree_root)
	{
		return;
	}
	BTNode<T> *tmp_node = tree_root;
	if (tree_root->node_rchild)
	{
		tree_root = tree_root->node_rchild;	//根节点换成右子节点
		//将左子树搬移到右子节点的左子树的最底部
		if(tmp_node->node_lchild)
		{
			BTNode<T> *l_child = tmp_node->node_lchild;
			BTNode<T> *new_l_child = tree_root->node_lchild;
			if(!new_l_child)
			{
				tree_root->node_lchild = l_child;
			}else{
				//遍历左子树,寻找可以挂接的空左子节点
				tree_root->lchild_leaf(l_child,new_l_child);
			}
		}
	}else{
		tree_root = tree_root->node_lchild;	//根节点换成左子节点
	}
	delete tmp_node;//删除先前的根节点
}

template <typename T>
BTNode<T> * BinaryTree<T>::find(const T&val)
{
	if(!tree_root)
	{
		return nullptr;
	}
	return tree_root->find(val);
}

template <typename T>
inline typename BinaryTree<T>::iterator BinaryTree<T>::get_first() const
{
	return min_node;
}

template <typename T>
inline typename BinaryTree<T>::iterator BinaryTree<T>::get_last() const
{
	return max_node;
}

template <typename T>
typename BinaryTree<T>::iterator BinaryTree<T>::get_parent(typename BinaryTree<T>::iterator child) const
{
	if(!this->tree_root)
	{
		return nullptr;
	}else{
		return (BinaryTree<T>::iterator)(this->tree_root->getPNode(child));
	}
}

template <typename T>
inline void BinaryTree<T>::set_MinMaxNode()
{
	if(!tree_root)
	{
		min_node = max_node = nullptr;
	}else{
		min_node = tree_root->getMinNode(tree_root);
		max_node = tree_root->getMaxNode(tree_root);
	}
}

template <typename T>
void BinaryTree<T>::os_out(std::ostream &os)
{
	os<< "pre_order:";
	pre_order(tree_root,os);
	os << "\n";
	os<< "in_order:";
	in_order(tree_root,os);
	os << "\n";
	os<< "post_order:";
	post_order(tree_root,os);
	os << "\n";
}

template <typename T>
void BinaryTree<T>::pre_order(BTNode<T> *pnode, std::ostream &os) 
{
	if(pnode)
	{
		display_val(pnode,os);
		if(pnode->node_lchild)
		{
			pre_order(pnode->node_lchild,os);
		}
		if(pnode->node_rchild)
		{
			pre_order(pnode->node_rchild,os);
		}
	}
}

template <typename T>
void BinaryTree<T>::in_order(BTNode<T> *pnode, std::ostream &os) 
{
	if(pnode)
	{
		if(pnode->node_lchild)
		{
			in_order(pnode->node_lchild,os);
		}
		display_val(pnode,os);
		if(pnode->node_rchild)
		{
			in_order(pnode->node_rchild,os);
		}
	}
}
	
template <typename T>
void BinaryTree<T>::post_order(BTNode<T> *pnode, std::ostream &os) 
{
	if(pnode)
	{
		if(pnode->node_lchild)
		{
			post_order(pnode->node_lchild,os);
		}
		if(pnode->node_rchild)
		{
			post_order(pnode->node_rchild,os);
		}
		display_val(pnode,os);
	}
}

template <typename T>
void BinaryTree<T>::display_val(BTNode<T> *pnode,std::ostream &os)
{
	if(pnode)
	{
		os <<"("<<pnode->i_cnt<<","<<pnode->t_val<<")";
	}
}

template <typename T>
inline std::ostream& operator<<(std::ostream &os,BinaryTree<T> &obj)
{
	os << "tree:" << std::endl;
	obj.os_out(os);
	return os;
};

template <typename T>
bool  is_sametree(BinaryTree<T> *obj1, BinaryTree<T> *obj2)
{
	return is_samenode(obj1->tree_root,obj2->tree_root);
}

template <typename T>
bool  is_subtree(BinaryTree<T> *ptree, BinaryTree<T> *ctree)
{
	return is_subnode(ptree->tree_root,ctree->tree_root);
}
           

        KeyObj.h

#ifndef _KEY_OBJ_H_
#define _KEY_OBJ_H_

#include <ostream>

class KeyObj
{
public:
	KeyObj(int pid,int cid):p_id(pid),c_id(cid){};
	//
	static int cmp_Key(const KeyObj &obj1, const KeyObj &obj2)
    {
        int diff = obj1.p_id - obj2.p_id;
	    if (diff != 0) 		
            return diff;
	    diff = obj1.c_id - obj2.c_id;
	    if (diff != 0) 		
            return diff;
	    return 0;
    };

	int	p_id;
	int c_id;
private:
};
inline bool operator==(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) == 0; }
inline bool operator!=(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) != 0; }
inline bool operator>=(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) >= 0; }
inline bool operator<=(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) <= 0; }
inline bool operator>(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) > 0; }
inline bool operator<(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) < 0; }

inline std::ostream &operator<<(std::ostream &os, const KeyObj& obj)
{
	os << "(";
	os << obj.p_id << "," << obj.c_id;
	os <<")";
	return os;
};

#endif //_KEY_OBJ_H_
           

        main.cpp

#include "BinaryTree.h"
#include "KeyObj.h"

int main(int argc, char* argv[])
{
	int i_v[] = {6,3,5,9,3,8};
	BinaryTree<int> iptree;
	for (int i=0; i<sizeof(i_v)/sizeof(int); i++)
	{
		iptree.insert(i_v[i]);
	}
	//iptree.insert(5);
	std::cout << iptree;	//三序遍历输出
	std::cout <<"iptree min_val = " << iptree.get_first()->get_val()<< std::endl;//获取最小值节点
	std::cout <<"iptree max_val = " << iptree.get_last()->get_val()<< std::endl;//获取最大值节点
	BTNode<int> *node = iptree.find(5);	//查找
	if(nullptr!=node)
	{
		std::cout <<"find:"<< node->get_cnt()<< "," << node->get_val() << std::endl;
	}
	node = iptree.get_parent(node);//获取父节点
	if(nullptr!=node)
	{
		std::cout <<"get_parent:"<< node->get_cnt()<< "," << node->get_val() << std::endl;
	}
	node = iptree.get_parent(iptree.get_first());
	if(nullptr!=node)
	{
		std::cout <<"get_parent:"<< node->get_cnt()<< "," << node->get_val() << std::endl;
	}
	node = iptree.get_parent(iptree.get_last());
	if(nullptr!=node)
	{
		std::cout <<"get_parent:"<< node->get_cnt()<< "," << node->get_val() << std::endl;
	}
	BinaryTree<int> ictree;
	for (int i=0; i<sizeof(i_v)/sizeof(int); i++)
	{
		ictree.insert(i_v[i]);
	}
	std::cout << ictree;//三序遍历输出
	//拷贝构造
	BinaryTree<int> icpytree(ictree);
	std::cout << icpytree;//三序遍历输出
	//比对测试
	std::cout << "is_sametree(&iptree,&ictree)?"<< (is_sametree(&iptree,&ictree)) << std::endl;
	std::cout << "is_subtree(&iptree,&ictree)?"<< (is_subtree(&iptree,&ictree)) << std::endl;
	iptree.insert(5);
	std::cout << "is_sametree(&iptree,&ictree)?"<< (is_sametree(&iptree,&ictree)) << std::endl;
	std::cout << "is_subtree(&iptree,&ictree)?"<< (is_subtree(&iptree,&ictree)) << std::endl;
	iptree.insert(10);
	std::cout << "is_sametree(&iptree,&ictree)?"<< (is_sametree(&iptree,&ictree)) << std::endl;
	std::cout << "is_subtree(&iptree,&ictree)?"<< (is_subtree(&iptree,&ictree)) << std::endl;
	// 删除测试
	ictree.remove(5);
	std::cout << ictree;
	//自定义类型作为模板参数类型
	BinaryTree<KeyObj> itree_KeyObj;
	KeyObj vkey[6]={KeyObj(2,3),KeyObj(2,5),KeyObj(1,3),KeyObj(3,2),KeyObj(4,3),KeyObj(1,5)};
	for (int i=0; i<6; i++)
	{
		itree_KeyObj.insert(vkey[i]);
	}
	std::cout << itree_KeyObj;
	return 0;
};
           

继续阅读