這一章通過講解二叉樹的template的實現過程，來講解template的語法，以及一些需要注意的地方。
首先了解一下二叉樹的一些基本操作，二叉樹支持插入，刪除，遍歷的操作。第一個安插至空白樹的值，會成為此樹的根節點。接下來的每個節點按特定的規則插入。如果小于根節點，就被置于左側指數，大于根節點就被置于右子樹。string類型按照字典排序。如下圖
?
?
遍歷又分前序遍歷，中序遍歷，后序遍歷。
?
按照上圖，前序遍歷結果： Piglet,Ek,Chris,Kanga,Roo,Pooh,Trigger.?
?
中序遍歷結果：Chris Ek Kanga Piglet ??Pooh Roo Trigger
?
后序遍歷結果：Chris Kanga Ek Pooh Trigger Roo Piglet
?
下面先實現一個節點類型BTnode。如果不實現泛型，
?
?
?
- class ?string_node?{??
- public :??
- ??
- private :??
- ????string?_val;??? //節點的值 ??
- ???? int ?_cnt;?????? //節點計數 ??
- ????string_node?*_lchild;???? //左節點 ??
- ????string_node?*_rchild;???? //右節點 ??
- ??
- };??
?
如果要實現存儲int類型的節點則又要定義一個int_node類。這顯然太麻煩。我們可以定義一個支持泛型的節點。
?
- template < typename ?valType>??
- class ?BTnode?{??
- ???? friend ? class ?BinaryTree<valType>;???? //把二叉樹類型BinaryTree聲明為友元類，這樣BinaryTree就可以訪問BTnode的私有成員?_val,_cnt,_lchild,_rchild等 ??
- public :??
- ????BTnode(){}??
- ????BTnode( const ?valType?&val);??
- ???? void ?insert_value( const ?valType&?elem);??
- ???? void ?remove_value(? const ?valType?&val,?BTnode?*&?prev);??
- ???? static ? void ?lchild_leaf(?BTnode?*leaf,?BTnode?*subtree);??
- private :??
- ????valType?_val;??
- ???? int ?????_cnt;??
- ????BTnode?*_lchild;??
- ????BTnode?*_rchild;??
- };??
?
為了通過class template產生實體類，我們必須在class tempalte名稱之后，緊接一個尖括號，其內放置一個實際類。例如:BTnode<int> 則將valType綁定至int， BTnode<string>則講valType綁定至string。這樣我們就實現了泛型。沒有必要再為
?
每個類型都定義一個節點類型了。什么情況下我們需要 模板參數列表(template parameter list)去修飾 模板類(class template）呢。 一般的規則是，在class template 以及其members的定義式中，不需要之外。其他的場合都需要以parameter list 加以修飾。如：
?
- template < typename ?elemType>??
- class ?BinaryTree?{??
- public :??
- ...??
- private :??
- ????BTnode<strong><elemType></strong>?*_root;??
- };??
- ??
下面給出BTnode完整的定義：
- template < typename ?Type>??
- class ?BinaryTree;??
- ??
- template < typename ?valType>??
- class ?BTnode?{??
- ???? friend ? class ?BinaryTree<valType>;??
- public :??
- ????BTnode(){}??
- ????BTnode( const ?valType?&val);??
- ???? void ?insert_value( const ?valType&?elem);??
- ???? void ?remove_value(? const ?valType?&val,?BTnode?*&?prev);??
- ???? static ? void ?lchild_leaf(?BTnode?*leaf,?BTnode?*subtree);??
- private :??
- ????valType?_val;??
- ???? int ?????_cnt;??
- ????BTnode?*_lchild;??
- ????BTnode?*_rchild;??
- };??
- ??
- template < typename ?valType>??
- BTnode<valType>::BTnode( const ?valType?&val)??
- ????????:?_val(val)??
- {??
- ????_cnt?=?1;??
- ????_lchild?=?_rchild?=?0;??
- }??
- ??
- template < typename ?valType>??
- void ?BTnode<valType>::insert_value( const ?valType?&val)?{??
- ???? if ?(? this ->_val?==?val)?{??
- ???????? this ->_cnt++;???????????
- ???????? return ?;??
- ????}??
- ??
- ???? if ( this ->_val?>?val?)?{??
- ???????? if (! this ->_lchild)??
- ???????????? this ->_lchild?=? new ?BTnode<valType>(val);??
- ???????? else ??
- ???????????? this ->_lchild->insert_value(val);??
- ????}? else ?{??
- ???????? if (! this ->_rchild)??
- ???????????? this ->_rchild?=? new ?BTnode<valType>(val);??
- ???????? else ??
- ???????????? this ->_rchild->insert_value(val);??
- ????}??
- ??
- }??
- ??
- template < typename ?valType>??
- void ?BTnode<valType>::remove_value(? const ?valType?&val,?BTnode?*&?prev)?{?????
- ? //找到相應的值，刪除該節點。prev是起始的節點。?這里需要修改BTnode?*指針本身，所以我們定義為?BTnode?*&?prev ??
- ??
- ???? if (?val?<?_val?)?{??
- ???????? if ?(?!_lchild)??
- ???????????? return ;??
- ???????? else ??
- ????????????_lchild->remove_value(val,?_lchild);??
- ????}??
- ???? else ? if ?(?val?>?_val)?{??
- ???????? if (?!_rchild)??
- ???????????? return ;??
- ???????? else ??
- ????????????_rchild->remove_value(val,_rchild);??
- ????}??
- ???? else ?{??
- ???????? if ?(_rchild)?{??
- ????????????prev?=?_rchild;??
- ???????????? if (_lchild)??
- ???????????????? if (?!prev->_lchild)??
- ????????????????????prev->_lchild?=?_lchild;??
- ???????????????? else ??
- ????????????????????BTnode<valType>::lchild_leaf(_lchild,prev->_lchild);??
- ????????}??
- ???????? else ??
- ????????????prev?=?_lchild;??
- ???????? delete ? this ;??
- ????}??
- ??
- }??
- ??
- template < typename ?valType>??
- inline ? void ?BTnode<valType>::lchild_leaf(?BTnode?*leaf,?BTnode?*subtree)?{??
- //使leaf成為subtree的左子樹的葉子節點 ??
- ???? while ?(subtree->_lchild)??
- ????????subtree?=?subtree->_lchild;??
- ????subtree->_lchild?=?leaf;??
- }??
?
- template < typename ?valType>??
- BTnode<valType>::BTnode( const ?valType?&val)??
- ????????:?_val(val)??
- {??
- ????_cnt?=?1;??
- ????_lchild?=?_rchild?=?0;??
- }??
為 什么這里第二次出現BTnode的時候不需要<valType>去修飾了呢，因為在class scope運算符出現之后 BTnode<valType>::，其后所有東西被視為位于class定義域內：還記得上面所說的規則嗎在class template 以及其members的定義式中，不需要之外。其他的場合都需要以parameter list 加以修飾。
BTnode<valType>:: ?//在class定義域之外。
?
BTnode() ? ?//在class定義域之內。
?
關于函數參數的規則是，若是非基本類型，則使用傳址的方式(by reference)傳遞 ，如果這個參數確認了，在函數內是只讀的則加上const 修飾詞。如：
?
- insert_value( const ?valType?&val)??
?
下面給出BinaryTree的模板實現：
?
- template < typename ?elemType>??
- class ?BinaryTree?{??
- public :??
- ????BinaryTree();??
- ????BinaryTree( const ?BinaryTree&);??
- ????~BinaryTree();??
- ????BinaryTree&?operator=?( const ?BinaryTree&);??
- ??
- ???? void ?insert(? const ?elemType?&);??
- ???? bool ?empty()?{? return ?_root?==?0;}??
- ???? void ?remove( const ?elemType?&elem);??
- ???? void ?remove_root();??
- ??
- ???? void ?clear()?{? if (_root)?{?clear(_root);?_root?=?0;}}??
- ???? void ?preorder();??
- ???? void ?preorder(BTnode<elemType>?*node,?ostream?&os?=?cout);??
- ???? static ?ostream?&?display_val(?elemType?&node,ostream?&os?=?cout);??
- ???? void ?pre_recursion(BTnode<elemType>?*node);??
- ????BTnode<elemType>*?get_root()?{? return ?_root;}??
- private :??
- ????BTnode<elemType>?*_root;??
- ???? void ?clear(BTnode<elemType>?*node);??
- ???? void ?copy(BTnode<elemType>?*tar,?BTnode<elemType>?*src);??
- };??
- ??
- template < typename ?elemType>??
- inline ?BinaryTree<elemType>::??
- BinaryTree()?:?_root(0)?{}??
- ??
- template < typename ?elemType>??
- inline ?BinaryTree<elemType>::BinaryTree( const ?BinaryTree&?rhs)?{??
- ????copy(_root,rhs._root);??
- }??
- ??
- template < typename ?elemType>??
- void ?BinaryTree<elemType>::insert(? const ?elemType?&elem)?{??
- ???? if ?(!_root)??
- ????????_root?=? new ?BTnode<elemType>(elem);??
- ????_root->insert_value(elem);??
- }??
- ??
- template < typename ?elemType>??
- inline ?BinaryTree<elemType>::~BinaryTree()?{??
- ????clear();??
- }??
- ??
- template < typename ?elemType>??
- inline ?BinaryTree<elemType>&??
- BinaryTree<elemType>::operator=?( const ?BinaryTree?&rhs)?{??
- ???? if (?!? this ?=?&rhs)?{??
- ????????clear();??
- ????????copy(_root,rhs._root);??
- ????}??
- ???? return ?* this ;??
- }??
- ??
- template < typename ?elemType>??
- inline ? void ?BinaryTree<elemType>::remove(? const ?elemType?&elem)?{??
- ???? if (_root)?{??
- ???????? if (?_root->_val?==?elem)??
- ????????????remove_root();??
- ???????? else ??
- ????????????_root->remove_value(elem,?_root);??
- ????}??
- }??
- ??
- template < typename ?elemType>??
- void ?BinaryTree<elemType>::??
- remove_root()?{??
- ???? if ?(!_root)? return ;??
- ??
- ????BTnode<elemType>?*tmp?=?_root;??
- ??
- ???? if (?!_root->_rchild)?{??
- ????????_root?=?_root->_rchild;??
- ???????? if (tmp->_lchild)?{??
- ???????????? if (!_root->_lchild)??
- ???????????? //沒有任何子樹則直接接上 ??
- ????????????????_root->_lchild?=?tmp->_lchild;??
- ???????????? else ??
- ????????????????BTnode<elemType>::lchild_leaf(tmp->_lchild,_root->_lchild);??
- ????????}??
- ??
- ????}??
- ???? else ??
- ????????_root?=?_root->_lchild;??
- ???? delete ?tmp;??
- }??
- //清除所有節點 ??
- template < typename ?elemType>??
- void ?BinaryTree<elemType>::clear(BTnode<elemType>?*node)?{??
- ???? if (node)?{??
- ????????clear(node->_lchild);??
- ????????clear(node->_rchild);??
- ???????? delete ?node;??
- ????}??
- }??
- ??
- template < typename ?elemType>??
- void ?BinaryTree<elemType>::preorder()?{??
- ????pre_recursion(_root);??
- }??
- ??
- //遞歸的前序遍歷 ??
- template < typename ?elemType>??
- void ?BinaryTree<elemType>::preorder(BTnode<elemType>?*node,?ostream?&os)?{??
- ??
- ???? if (node)?{??
- ????????display_val(node->_val,os);??
- ????????preorder(node->_lchild,os);??
- ????????preorder(node->_rchild,os);??
- ????}??
- }??
- ??
- template < typename ?elemType>??
- ostream?&?BinaryTree<elemType>::display_val(elemType?&node?,?ostream?&os)?{??
- ????os?<<?node?<<? '?' ;??
- ???? return ?os;??
- }??
- ??
- //非遞歸實現前序遍歷 ??
- template < typename ?elemType>??
- void ?BinaryTree<elemType>::pre_recursion?(BTnode<elemType>?*node)?{??
- ????stack<BTnode<elemType>*>?s;??? //使用先進后出棧 ??
- ????s.push(node);??
- ???? while (!s.empty())?{??
- ????????BTnode<elemType>*?tmp?=?s.top();??
- ????????s.pop();??
- ????????BinaryTree<elemType>::display_val(tmp->_val,std::cout);??
- ???????? if (tmp->_rchild)??
- ????????????s.push(tmp->_rchild);???? //右節點先進棧?后出，后遍歷 ??
- ???????? if (tmp->_lchild)??
- ????????????s.push(tmp->_lchild);???? //左節點后進棧，先出，先遍歷 ??
- ????}??
- }??
?
測試：
?
- int ?main()??
- {??
- ????BinaryTree<string>?bt;??
- ????bt.insert( "abc" );??
- ????bt.insert( "agcb" );??
- ????bt.insert( "kfgd" );??
- ????bt.insert( "how?are?you" );??
- ????bt.preorder();??
- ???? //bt.remove("abc"); ??
- ???? //bt.preorder(); ??
- ????bt.remove( "kfgd" );??
- ????bt.preorder();??
- ???? return ?0;??
- }??
本章不僅讓我了解泛型編程，模板類是怎么一回事，template的語法。而且還讓我重溫了一次二叉排序樹 這個數據結構。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
