Essential C++ Chapter 6学习记录(6.1~6.5节的代码)
2022/1/18 1:04:06
本文主要是介绍Essential C++ Chapter 6学习记录(6.1~6.5节的代码),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include<iostream> using namespace std; template <typename elemType> class BinaryTree; template <typename elemType> class BTnode; template <typename valType> class BTnode{ friend class BinaryTree<valType>; public: BTnode(const valType &); void insert_value(const valType &); // void lchild_leaf(BTnode *leaf,BTnode *subtree); void remove_value(const valType &,BTnode *&); void preorder(BTnode *pt,ostream &os) const; void inorder(BTnode *pt,ostream &os) const; void postorder(BTnode *pt,ostream &os) const; static void lchild_leaf(BTnode *leaf,BTnode *subtree); private: valType _val; int _cnt; BTnode *_lchild; BTnode *_rchild; void display_val( BTnode *pt, ostream &os ) const; }; template<typename valType> inline BTnode<valType>:: BTnode(const valType &val) : _val(val) { _cnt = 1; _lchild = _rchild = 0; } template <typename valType> void inline BTnode<valType>:: insert_value(const valType &val) { if(val == _val) { _cnt++; return; } if(val < _val) { if(! _lchild) _lchild = new BTnode(val); else _lchild -> insert_value(val); } if(val > _val) { if(! _rchild) _rchild = new BTnode(val); else _rchild -> insert_value(val); } } template<typename valType> inline void BTnode<valType>:: remove_value(const valType &val,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;//改变pointer指向的对象 else BTnode<valType>::lchild_leaf(_lchild,prev->_lchild); } else prev = _lchild;// 改变pointer本身 delete this; } } template<typename valType> inline void BTnode<valType>:: lchild_leaf(BTnode *leaf,BTnode *subtree) { while(subtree->_lchild) subtree = subtree->_lchild; subtree->_lchild = leaf; } template <typename valType> inline void BTnode<valType>:: display_val( BTnode *pt, ostream &os ) const { os << pt->_val; if ( pt->_cnt > 1 ) os << "( " << pt->_cnt << " ) "; else os << ' '; } template<typename valType> void BTnode<valType>:: preorder(BTnode *pt,ostream &os) const { if(pt) { display_val(pt,os); if(pt->_lchild) preorder(pt->_lchild,os); if(pt->_rchild) preorder(pt->_rchild,os); } } template<typename valType> void BTnode<valType>:: inorder(BTnode *pt,ostream &os) const { if(pt) { if(pt->_lchild) inorder(pt->_lchild,os); display_val(pt,os); if(pt->_rchild) inorder(pt->_rchild,os); } } template<typename valType> void BTnode<valType>:: postorder(BTnode *pt,ostream &os) const { if(pt) { if(pt->_lchild) postorder(pt->_lchild,os); if(pt->_rchild) postorder(pt->_rchild,os); display_val(pt,os); } } template <typename elemType> class BinaryTree{ friend ostream& operator<< (ostream& os,const BinaryTree<elemType> &bt); public: BinaryTree(); BinaryTree(const BinaryTree &); ~BinaryTree(); BinaryTree& operator=(const BinaryTree&); void clear(){if(_root){clear(_root);_root = 0;}} void insert(const elemType &); void remove(const elemType &); bool empty(){ return _root == 0; } // 以上都一样 // void inorder( ostream &os = *_current_os ) const { _root->inorder( _root, os ); } // void postorder( ostream &os = *_current_os ) const { _root->postorder( _root, os ); } // void preorder( ostream &os = *_current_os ) const { _root->preorder( _root, os ); } void inorder() const { _root->inorder( _root, cout ); } void postorder() const { _root->postorder( _root, cout ); } void preorder() const { _root->preorder( _root, cout ); } // ostream& print( ostream &os = *_current_os, // void (BinaryTree<elemType>::*traversal)( ostream& ) const = // &BinaryTree<elemType>::inorder ) const; ostream& print( ostream &os); private: // BTnode必须以template parameter list加以限定 BTnode<elemType> *_root; // static ostream *_current_os; // 将src所指子树复制到tar所指子树 void copy(BTnode<elemType>* tar,BTnode<elemType>*src); void clear(BTnode<elemType>*); void remove_root(); }; // template <typename elemType> // ostream *BinaryTree<elemType>::_current_os = &cout; 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> 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>:: insert(const elemType &elem) { if(! _root) _root = new BTnode<elemType> (elem); else _root -> insert_value(elem); } 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> inline void BinaryTree<elemType>:: remove_root() { if(! _root) return; BTnode <elemType> *tmp = _root; if(_root->_rchild) { _root = _root -> _rchild; if(tmp -> _lchild) { BTnode<elemType> *lc = tmp -> _lchild; BTnode<elemType> *newlc = _root -> _lchild; if(!newlc) _root -> _lchild = lc; else BTnode<elemType>::lchild_leaf(lc,newlc); } } else _root = _root->_lchild; delete tmp; } template <typename elemType> void BinaryTree<elemType>:: clear(BTnode<elemType> *pt) { if(pt){ clear(pt->_lchild); clear(pt->_rchild); delete pt; } } // template <typename elemType> // ostream& // BinaryTree<elemType>:: // print( ostream &os, // void (BinaryTree::*traversal)( ostream& ) const ) const // { // (this->*traversal)( os ); // return os; // } template <typename elemType> ostream& BinaryTree<elemType>:: print( ostream &os) { this->inorder(); return os; } // template <typename elemType> // inline ostream& // operator<<( ostream &os, const BinaryTree<elemType> &bt ) // { // os << "Tree: " << endl; // bt.print( os, &BinaryTree<elemType>::inorder ); // return os; // } // friend ostream& operator<< (ostream& os,const BinaryTree<elemType> &bt); template<typename elemType> inline ostream& operator<< (ostream& os,BinaryTree<elemType> &bt) { os<<"Tree: "<<endl; bt.print(os); return os; } // 错误写法: // template <typename elemType> // inline BinaryTree<elemType>:: // BinaryTree& operator=(const BinaryTree &rhs) // { // if(this != &rhs){ // clear(); // copy(_root,rhs._root); // } // return *this; // } int main(){ BinaryTree<string> bt; bt.insert( "Piglet" ); bt.insert( "Eeyore" ); bt.insert( "Roo" ); bt.insert( "Tigger" ); bt.insert( "Chris" ); bt.insert( "Pooh" ); bt.insert( "Kanga" ); bt.preorder(); cout<<'\n'; bt.remove("Piglet"); bt.preorder(); cout<<'\n'; cout<<bt; return 0; }
这篇关于Essential C++ Chapter 6学习记录(6.1~6.5节的代码)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验