天天看點
傳回

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;
};
c++實戰案例 c++ 二叉樹 泛型程式設計 類模闆 函數模闆
上一篇: 【機器學習執行個體】Titanic生存預測
下一篇: 二叉搜尋樹的第K個節點（思路與實作）

繼續閱讀