利用STL中的MAP和VECTOR实现的一个多节点树

//Download by http://www.NewXing.com #ifndef _TREE_H_ #define _TREE_H_ /* Copyright - All copy right is owned by Mr Jack Hui Author : Jack, Hui Ho Yin Email : jackhui@hotmail.com Last Update : 27-Aug-2000 */ #pragma warning(disable : 4786) //debug info - name too long #include <vector> #include <map> #include <string> #include <iostream> using namespace std; namespace Tiffany { //forward declarations template <class Key, class T> class TreeNode; template <class Key, class T> class Tree; template <class Key, class T> class Tree_iterator; // template <class Key, class T> class TreeNode { public: T m_data; //things stored in treenode Key m_key; //key to locate myself int m_level; //rootnode is of level 1 TreeNode<Key,T>* m_parent; //points to node of parent vector<TreeNode<Key,T> *> m_children; //holds pointers for children vector<TreeNode<Key,T> *>::iterator m_current; //holds iterator to current child processing Tree<Key, T>* m_LinkedTree; //whom i'm belonging to TreeNode(Tree<Key,T>* tr) : m_parent(NULL) { m_LinkedTree = tr; }; TreeNode(Tree<Key,T>* tr, const Key key, const T x) { m_key = key; m_data = x; m_LinkedTree = tr; }; //Delete all the children of this node including all the down levels void DeleteAllChildren() { vector<TreeNode<Key,T>*>::iterator pchild; map<Key, TreeNode<Key,T>*>::iterator itrmap; for(pchild=m_children.begin();pchild != m_children.end();) { (*pchild)->DeleteAllChildren(); itrmap = m_LinkedTree->m_nodemap.find((*pchild)->m_key); m_LinkedTree->m_nodemap.erase(itrmap); delete *pchild; m_children.erase(pchild); //after removing the node, iterater is advanced } }; //Return a reference to parent node in the tree TreeNode<Key,T>& GetParent () const { return *m_parent; }; //returns a reference to vector to the children const vector<TreeNode<Key,T>*>& GetChildren () const { return m_children; }; long ChildCount () const { return m_children.size(); }; //add a child node to this node void AddChild (TreeNode<Key,T>* child) { child->m_parent = this; child->m_level = this->m_level + 1; m_children.push_back(child); }; T GetData(void) const { return m_data; } }; //************ End of Tree Node declaration ***************************// // //************ Start of Tree declaration ***************************// // template <class Key, class T> class Tree { friend class TreeNode<Key, T>; protected: //provide a name of the TreeNode to direct access to it map<Key, TreeNode<Key,T>*> m_nodemap; //a map for fast accessing TreeNode TreeNode<Key,T>* m_pTreeroot; //a pointer to root node TreeNode<Key,T>* m_WalkPivot; //Sub-tree root for walking TreeNode<Key,T>* m_WalkCurrent; //point to current node of walking TreeNode<Key,T>* m_WalkParent; //point to parent node of current node public: typedef Tree_iterator<Key, T> iterator; typedef const iterator const_iterator; iterator begin() { iterator _tmp; _tmp.m_Node = m_nodemap.begin(); return _tmp; } iterator end() { iterator _tmp; _tmp.m_Node = m_nodemap.end(); return _tmp; } const_iterator begin() const { iterator _tmp; _tmp.m_Node = m_nodemap.begin(); return _tmp; } const_iterator end() const { const_iterator _tmp; _tmp.m_Node = m_nodemap.end(); return _tmp; } iterator find(const Key& key) { iterator _tmp; _tmp.m_Node = m_nodemap.find(key); return _tmp; } const_iterator find(const Key& key) const { const_iterator _tmp; _tmp.m_Node = m_nodemap.find(key); return _tmp; } Tree () : m_pTreeroot(NULL) { //instantiate an empty tree } Tree (const Key nm, const T x) { //instantiate a tree with the root node TreeNode<Key,T>* pNode; pNode = new TreeNode<Key,T>(this, nm, x); m_nodemap.insert(map<Key, TreeNode<Key,T>*>::value_type(nm, pNode)); m_pTreeroot = pNode; pNode->m_level = 1; } ~Tree() { if (m_pTreeroot) { m_pTreeroot->DeleteAllChildren(); delete m_pTreeroot; } } //returns tree root node, or NULL for empty tree TreeNode<Key,T>& GetRoot () const { return *m_pTreeroot; } iterator AddChild (iterator& parent, const Key nm, const T x) { TreeNode<Key,T>* pNew; pNew = new TreeNode<Key,T>(this, nm, x); parent.m_Node->second->AddChild(pNew); pair<map<Key, TreeNode<Key,T>*>::iterator, bool> pt = m_nodemap.insert(map<Key, TreeNode<Key,T>*>::value_type(nm, pNew)); iterator _tmp; _tmp.m_Node = pt.first; return _tmp; } iterator AddChild (const Key nm, const T x) { TreeNode<Key,T>* pNew; pNew = new TreeNode<Key,T>(this, nm, x); m_pTreeroot->AddChild(pNew); pair<map<Key, TreeNode<Key,T>*>::iterator, bool> pt = m_nodemap.insert(map<Key, TreeNode<Key,T>*>::value_type(nm, pNew)); iterator _tmp; _tmp.m_Node = pt.first; return _tmp; } void DeleteAllChildren(iterator & itr) { itr.m_Node->second->DeleteAllChildren(); } size_t size(void) { return m_nodemap.size(); } //Set the sub-tree walking root and traverse to the first node void SetPostOrderSubTreePivot(iterator& it) { m_WalkPivot = it.m_Node->second; m_WalkCurrent = m_WalkPivot; m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin(); while (m_WalkCurrent->m_children.size() != 0) { m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin(); m_WalkCurrent = *(m_WalkCurrent->m_children.begin()); } if (m_WalkCurrent != m_WalkPivot) { m_WalkParent = m_WalkCurrent->m_parent; } else { m_WalkParent = m_WalkCurrent; //for the case no child in pivot } } //Set the sub-tree walking root and traverse to the first node void SetPostOrderRootPivot() { m_WalkPivot = m_pTreeroot; m_WalkCurrent = m_WalkPivot; m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin(); while (m_WalkCurrent->m_children.size() != 0) { m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin(); m_WalkCurrent = *(m_WalkCurrent->m_children.begin()); } if (m_WalkCurrent != m_WalkPivot) { m_WalkParent = m_WalkCurrent->m_parent; } else { m_WalkParent = m_WalkCurrent; //for the case no child in pivot } } void SetWalkDownRootPivot() { m_WalkPivot = m_pTreeroot; m_WalkCurrent = m_WalkPivot; m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin(); } //it advances m_WalkCurrent in post-order, and returns true if a move is made //else it returns false bool SubTreePostOrderWalk() { if (m_WalkCurrent == m_WalkPivot) return false; //if not the parent's last child, advance one node in paraent's child //if the advanced child contains sub node, go in depth to the leftmost one if (++m_WalkParent->m_current != m_WalkParent->m_children.end()) { m_WalkCurrent = *(m_WalkParent->m_current); while (m_WalkCurrent->m_children.size() != 0) { //go down m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin(); m_WalkParent = m_WalkCurrent; m_WalkCurrent = *(m_WalkCurrent->m_current); } } else { //if it's the last child of parent, we go up m_WalkCurrent = m_WalkParent; m_WalkParent = m_WalkCurrent->m_parent; } m_WalkParent = m_WalkCurrent->m_parent; return true; } //It advance the tree in top-down style with parent first bool SubTreeWalkDown() { //if it has children, we go down to children if (m_WalkCurrent->m_current != m_WalkCurrent->m_children.end()) { m_WalkCurrent = *(m_WalkCurrent->m_current); m_WalkParent = m_WalkCurrent->m_parent; m_WalkParent->m_current++; //advance to next child for next iteration m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin(); //initialize to first child } else { //