一个简单的多叉树C++实现

一个简单的多叉树实现：

1. 利用迭代器方便地构建树，
2. 可以递归输出，前序，后序。
3. 利用栈实现输出。
4. 销毁树只能后序遍历

类的定义：

1. #include <iostream>  
2. #include <string>  
3. #include <vector>  
4. #include <stack>  
5. #include <cassert>  
6. using namespace std;  
7. template<class T>  
8. class htree_node{  
9. public:  
10.     typedef htree_node<T> node_type;  
11.     htree_node()  
12.         :parent(0),format("  ")  
13.     {}  
14.     htree_node(const T& x)        
15.         :name(x), parent(0), format("  ")  
16.     {}  
17.     ~htree_node()  
18.     {}  
19.     T name;  
20.     //默认为两个空格  
21.     std::string format;  
22.     node_type *parent;  
23.     std::vector<node_type*> children;  
24. };  
25. template<class T, class Container = htree_node<T> >  
26. class htree{  
27. protected:  
28.     typedef Container tree_node;          
29. public:  
30.     htree()  
31.         :root(0)  
32.     { Init(); }  
33.     htree(tree_node *node)  
34.         :root(node)  
35.     { Init(); }  
36.     ~htree(){  
37.         destroy(root);  
38.     }  
39.     //pre_order_iterator  
40.     class iterator{  
41.     public:  
42.         iterator()  
43.             : _node(0)  
44.             , skip_current_children_(false)  
45.         {  
46.             skip_children();  
47.         }  
48.         iterator(tree_node *node)  
49.             : _node(node)  
50.             , skip_current_children_(false)  
51.         {  
52.             skip_children();  
53.         }  
54.         ~iterator()  
55.         {}  
56.         T& operator*() const  
57.         {  
58.             return _node->name;  
59.         }  
60.         T* operator->() const  
61.         {  
62.             return &(_node->name);  
63.         }  
64.         tree_node* get()  
65.         {  
66.             return _node;  
67.         }  
68.         //开始位置  
69.         iterator begin() const  
70.         {  
71.             return iterator(_node);  
72.         }  
73.         //结束位置  const????  
74.         iterator end() const  
75.         {  
76.             return iterator( _find_end(_node) );  
77.         }  
78.           
79.         tree_node *_node;  
80.     protected:  
81.         bool skip_current_children_;  
82.         void         skip_children()  
83.         {  
84.             skip_current_children_=true;  
85.         }  
86.         tree_node* _find_end(tree_node* current) const  
87.         {  
88.             int pos = current->children.size()-1;  
89.             if( pos<0 )  
90.                 return (current);  
91.                 //这里返回iterator会被析构掉，临时对象  
92.             //从最后一个孩子找起，  
93.             else  
94.                 _find_end(current->children[pos]);  
95.         }  
96.     };  
97. public:  
98.     //注意传position的引用  
99.     iterator insert(iterator& position, const T& x)       
100.     {  
101.         tree_node *tmp = new tree_node(x);  
102.         position._node->children.push_back(tmp);  
103.         tmp->parent = position._node;  
104.         return iterator(tmp);  
105.     }  
106.     //后序递归输出  
107.     void post_recurs_render(tree_node* some, unsigned recurs_level)  
108.     {  
109.         for (unsigned i = 0; i < some->children.size(); i++)  
110.             post_recurs_render(some->children[i], recurs_level+1);  
111.         for (int i = 0; i<recurs_level; i++)  
112.             cout << "  ";  
113.         cout << some->name << endl;  
114.     }  
115.     //先序递归输出  
116.     void pre_recurs_render(tree_node* some, unsigned recurs_level)  
117.     {  
118.         for (int i = 0; i<recurs_level; i++)  
119.             cout << "  ";  
120.         cout << some->name << endl;  
121.         for (unsigned i = 0; i < some->children.size(); i++)  
122.             pre_recurs_render(some->children[i], recurs_level+1);  
123.     }  
124.   
125.     //利用stack  
126.     //使用Transform格式化输出  
127.     void recurs_render(tree_node* some)  
128.     {  
129.         std::string temp;  
130.         temp = form_stack.top() + some->format;  
131.         form_stack.push(temp);  
132.           
133.         cout << temp;  
134.         cout << some->name;  
135.         cout << endl;  
136.         for (unsigned i = 0; i < some->children.size(); i++)  
137.             recurs_render(some->children[i]);  
138.         form_stack.pop();  
139.     }  
140.     tree_node *root;  
141. private:  
142.     void Init(){  
143.         form_stack.push(std::string(" "));  
144.     };  
145.     void destroy(tree_node *some)  
146.     {  
147.         #define SAFE_DELETE(p) {if(p){delete p; p=NULL;}}  
148.         //后序删除  
149.         for (unsigned i = 0; i < some->children.size(); i++)  
150.             destroy(some->children[i]);  
151.         SAFE_DELETE(some);  
152.     }  
153.     std::stack<std::string> form_stack;  
154. };  

下面是main函数里的测试代码：

1. int main()   
2. {   
3.     //for detecting the memory leaks  
4.     int tmpFlag = _CrtSetDbgFlag( _CRTDBG_REPORT_FLAG );   
5.     tmpFlag |= _CRTDBG_LEAK_CHECK_DF;   
6.     _CrtSetDbgFlag( tmpFlag );  
7.     typedef htree_node<string> node_type;  
8.     typedef htree<string> tree_type;  
9.     node_type *one = new node_type("one");  
10.       
11.     tree_type::iterator iter(one);  
12.     tree_type tr1(one);  
13.     tree_type::iterator two = tr1.insert(iter, "two");  
14.     tree_type::iterator three = tr1.insert(iter, "three");  
15.     tr1.insert(two, "apple");  
16.     tr1.insert(two, "banana");  
17.     tr1.insert(two, "peach");  
18.     tr1.insert(three, "china");  
19.     tr1.insert(three, "england");  
20.       
21.     //method 1：  
22.     tr1.recurs_render(tr1.root);  
23.     cout << "--------" << endl;  
24.       
25.     //method 2:   
26.     tr1.pre_recurs_render(tr1.root, 1);  
27.     cout << "--------" << endl;  
28.     //method 3:  
29.     tr1.post_recurs_render(tr1.root, 1);  
30.     cout << "--------" << endl;  
31.     // test iterator::end() function  
32.     cout << (* (iter.end()) ) << endl;  
33.     return 0;  
34. } 

最终输出结果：

1.    one  
2.      two  
3.        apple  
4.        banana  
5.        peach  
6.      three  
7.        china  
8.        england  
9. --------  
10.   one  
11.     two  
12.       apple  
13.       banana  
14.       peach  
15.     three  
16.       china  
17.       england  
18. --------  
19.       apple  
20.       banana  
21.       peach  
22.     two  
23.       china  
24.       england  
25.     three  
26.   one  
27. --------  
28. england 

---

C++树的实现

///Tree.h 文件#pragma once#include <list>#include <algorithm>using namespace std;struct TreeNode; //定义一个结构体原形class Tree; //定义一个类原形class Iterator; //定义一个类原形typedef list<TreeNode*> List; //重命名一个节点链表TreeNode* clone(TreeNode*, List&, TreeNode*);//Clone复制函数struct TreeNode { int _data; //数据 TreeNode* _parent; //父节点 List _children; //子节点 TreeNode(int, TreeNode* ); //构造函数 void SetParent(TreeNode& ); //设置父节点 void InsertChildren(TreeNode& ); //插入子节点};class Tree{public: //下面是构造器和运算符重载 Tree(); //默认构造函数 Tree(const Tree&); //复制构造函数 Tree(const int); //带参数构造函数 Tree(const int,const list<Tree*>&); //带参数构造函数 ~Tree(); //析构函数 Tree& operator=(const Tree&); //=符号运算符重载 bool operator==(const Tree&); //==符号运算符重载 bool operator!=(const Tree&); //!=符号运算符重载 //下面是成员函数 void Clear(); //清空 bool IsEmpty()const; //判断是否为空 int Size()const; //计算节点数目 int Leaves(); //计算叶子数 int Root()const; //返回根元素 int Height(); //计算树的高度 //下面是静态成员函数 static bool IsRoot(Iterator); //判断是否是根 static bool isLeaf(Iterator); //判断是否是叶子 static Iterator Parent(Iterator); //返回其父节点 static int NumChildren(Iterator); //返回其子节点数目 //跌代器函数 Iterator begin(); //Tree Begin Iterator end(); //Tree End friend class Iterator; //Iterator SubClassprivate: list<TreeNode*> _nodes; //节点数组 list<TreeNode*>::iterator LIt; //一个节点迭代器 int height(TreeNode*); int level(TreeNode*,Iterator);};//This is TreeSub Class Iteratorclass Iterator{private: Tree* _tree; //Tree data list<TreeNode*>::iterator _lit; //List Iteratorpublic: Iterator(); //默认构造函数 Iterator(const Iterator&); //复制构造函数 Iterator(Tree*,TreeNode*); //构造函数 Iterator(Tree*,list<TreeNode*>::iterator); //构造函数 //运算符重载 void operator=(const Iterator&); //赋值运算符重载 bool operator==(const Iterator&); //关系运算符重载 bool operator!=(const Iterator&); //关系运算符重载 Iterator& operator++(); //前缀++运算符 Iterator operator++(int); //后缀++运算符 int operator*()const; //获得节点信息 bool operator!(); //赋值运算符重载 typedef list<TreeNode*>::iterator List; friend class Tree;};

///Tree.cpp 文件#include "stdafx.h"#include "Tree.h"//***** 下面是对于TreeNode结构体的定义实现*****///TreeNode::TreeNode(int type = 0, TreeNode* Parent = 0) { _data = type; _parent = Parent;}void TreeNode::SetParent(TreeNode& node) { _parent = &node;}void TreeNode::InsertChildren(TreeNode& node) { TreeNode* p = &node; _children.push_back(p);}//***** 下面是对于Tree类的定义实现*****///Tree::Tree() {}Tree::Tree(const int type) { _nodes.push_back(new TreeNode(type));}Tree::Tree(const Tree& t) { if (t._nodes.empty())return; clone(t._nodes.front(), _nodes, 0);}Tree::Tree(const int type, const list<Tree*>& lit) { TreeNode* root = new TreeNode(type);//建立根节点 _nodes.push_back(root);//放入树中 list<Tree*>::const_iterator it; for (it = lit.begin(); it != lit.end(); it++) { if (!((*it)->_nodes.empty())) {//如果当前节点元素不为空 Tree* tp = new Tree(**it); TreeNode* p = tp->_nodes.front(); root->_children.push_back(p); //设置根的子节点 p->_parent = root; //设置节点的父节点为根 list<TreeNode*>::iterator lit1 = tp->_nodes.begin(); list<TreeNode*>::iterator lit2 = tp->_nodes.end(); list<TreeNode*>::iterator lit3 = _nodes.end(); _nodes.insert(lit3, lit1, lit2); } }}Tree::~Tree() { for (list<TreeNode*>::iterator it = _nodes.begin(); it != _nodes.end(); it++) { delete* it; }}Tree& Tree::operator =(const Tree & t) { Clear(); Tree* p = new Tree(t); _nodes = p->_nodes; return *this;}bool Tree::operator ==(const Tree& t) { if (_nodes.size() != t._nodes.size()) { return false; } list<TreeNode*>::iterator it = _nodes.begin(); list<TreeNode*>::const_iterator _it = t._nodes.begin(); while (it != _nodes.end() && _it != t._nodes.end()) { if ((*it)->_data != (*_it)->_data) { return false; } it++; _it++; } return true;}bool Tree::operator !=(const Tree& t) { if (_nodes.size() != _nodes.size()) { return true; } else { list<TreeNode*>::iterator it = _nodes.begin(); list<TreeNode*>::const_iterator _it = t._nodes.begin(); while (it != _nodes.end() && _it != t._nodes.end()) { if ((*it)->_data != (*_it)->_data) { return true; } it++; _it++; } return false; }}void Tree::Clear() { for (list<TreeNode*>::iterator it = _nodes.begin(); it != _nodes.end(); it++) { delete* it; } _nodes.clear();}bool Tree::IsEmpty()const { return _nodes.empty();}int Tree::Size()const { return (int)_nodes.size();}int Tree::Leaves() { int i = 0; list<TreeNode*>::iterator it = _nodes.begin(); while (it != _nodes.end()) { if ((*it)->_children.size() == 0) { i++; } it++; } return i;}int Tree::Height() { if (_nodes.size() != 0) { TreeNode* TNode = _nodes.front(); return height(TNode); } else { return -1; //判断为空树 }}int Tree::height(TreeNode* node) { if (!node) { return -1; } else { list<TreeNode*> plist = node->_children; if (plist.size() == 0) { return 0; } int hA = 0; for (list<TreeNode*>::iterator it = plist.begin(); it != plist.end(); it++) { int hB = height(*it); if (hB>hA) { hA = hB; } } return hA + 1; }}Iterator Tree::begin() { return Iterator(this, _nodes.begin());}Iterator Tree::end() { return Iterator(this, _nodes.end());}int Tree::Root()const { return (*_nodes.begin())->_data;}bool Tree::IsRoot(Iterator it) { TreeNode p = *it; if (p._parent == 0) { return true; } return false;}bool Tree::isLeaf(Iterator it) { TreeNode p = *it; if (p._children.size() == 0) { return true; } return false;}Iterator Tree::Parent(Iterator it) { TreeNode p = *it; Tree* t = it._tree; Iterator Ite(t, p._parent); return Ite;}int Tree::NumChildren(Iterator it) { TreeNode p = *it; return (int)p._children.size();}//***** 下面是对于Tree::Iterator类的定义实现*****///Iterator::Iterator() {}Iterator::Iterator(const Iterator& it) { _tree = it._tree; _lit = it._lit;}Iterator::Iterator(Tree* t, TreeNode* n) { _tree = t; list<TreeNode*>& nodes = _tree->_nodes; _lit = find(nodes.begin(), nodes.end(), n);//<algorithm> Members}Iterator::Iterator(Tree * t, list<TreeNode*>::iterator lt) { _tree = t; _lit = lt;}void Iterator::operator =(const Iterator& it) { _tree = it._tree; _lit = it._lit;}bool Iterator::operator ==(const Iterator & it) { return _tree == it._tree && _lit == it._lit;}bool Iterator::operator !=(const Iterator & it) { return _tree != it._tree || _lit != it._lit;}Iterator& Iterator::operator ++() { ++_lit; return *this;}Iterator Iterator::operator ++(int) { Iterator it(*this); ++_lit; return it;}int Iterator::operator *() const { return ((*_lit)->_data);}bool Iterator::operator !() { return _lit == _tree->_nodes.end();}//Clone函数TreeNode* clone(TreeNode* node, List& nodes, TreeNode* nodep) { TreeNode* cp = new TreeNode(node->_data, nodep); nodes.push_back(cp); List& l = node->_children; List& cl = cp->_children; for (list<TreeNode*>::iterator lt = l.begin(); lt != l.end(); lt++) { cl.push_back(clone(*lt, nodes, cp)); } return cp;}