STL扩展之tree,注意数据结构为data,childlist

一个简单的多叉树实现：

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

类的定义：

#include
#include
#include
#include
#include

using namespace std;

template<class T>
class htree_node{
public:
    typedef htree_node node_type;

    htree_node()
        :parent(0),format("  ")
    {}
    htree_node(const T& x)
        :name(x), parent(0), format("  ")
    {}

    ~htree_node()
    {}

    T name;
    //默认为两个空格
    std::string format;

    node_type *parent;
    std::vector children;
};

template<class T, class Container = htree_node >
class htree{
protected:
    typedef Container tree_node;
public:
    htree()
        :root(0)
    { Init(); }
    htree(tree_node *node)
        :root(node)
    { Init(); }
    ~htree(){
        destroy(root);
    }

    //pre_order_iterator
    class iterator{
    public:
        iterator()
            : _node(0)
            , skip_current_children_(false)
        {
            skip_children();
        }
        iterator(tree_node *node)
            : _node(node)
            , skip_current_children_(false)
        {
            skip_children();
        }

        ~iterator()
        {}

        T& operator*() const
        {
            return _node->name;
        }
        T* operator->() const
        {
            return &(_node->name);
        }
        tree_node* get()
        {
            return _node;
        }

        //开始位置
        iterator begin() const
        {
            return iterator(_node);
        }
        //结束位置  const????
        iterator end() const
        {
            return iterator( _find_end(_node) );
        }

        tree_node *_node;
    protected:
        bool skip_current_children_;
        void         skip_children()
        {
            skip_current_children_=true;
        }
        tree_node* _find_end(tree_node* current) const
        {
            int pos = current->children.size()-1;
            if( pos<0 )
                return (current);
                //这里返回iterator会被析构掉，临时对象
            //从最后一个孩子找起，
            else
                _find_end(current->children[pos]);
        }
    };
public:
    //注意传position的引用
    iterator insert(iterator& position, const T& x)
    {
        tree_node *tmp = new tree_node(x);

        position._node->children.push_back(tmp);
        tmp->parent = position._node;

        return iterator(tmp);
    }

    //后序递归输出
    void post_recurs_render(tree_node* some, unsigned recurs_level)
    {
        for (unsigned i = 0; i < some->children.size(); i++)
            post_recurs_render(some->children[i], recurs_level+1);
        for (int i = 0; i
            cout << "  ";

        cout << some->name << endl;
    }
    //先序递归输出
    void pre_recurs_render(tree_node* some, unsigned recurs_level)
    {
        for (int i = 0; i
            cout << "  ";

        cout << some->name << endl;

        for (unsigned i = 0; i < some->children.size(); i++)
            pre_recurs_render(some->children[i], recurs_level+1);
    }


    //利用stack
    //使用Transform格式化输出
    void recurs_render(tree_node* some)
    {
        std::string temp;
        temp = form_stack.top() + some->format;
        form_stack.push(temp);

        cout << temp;
        cout << some->name;
        cout << endl;
        for (unsigned i = 0; i < some->children.size(); i++)
            recurs_render(some->children[i]);

        form_stack.pop();
    }
    tree_node *root;

private:
    void Init(){
        form_stack.push(std::string(" "));
    };

    void destroy(tree_node *some)
    {
        #define SAFE_DELETE(p) {if(p){delete p; p=NULL;}}
        //后序删除
        for (unsigned i = 0; i < some->children.size(); i++)
            destroy(some->children[i]);
        SAFE_DELETE(some);
    }

    std::stack form_stack;
};

#include <iostream> #include <string> #include <vector> #include <stack> #include <cassert> using namespace std; template<class T> class htree_node{ public: typedef htree_node<T> node_type; htree_node() :parent(0),format(" ") {} htree_node(const T& x) :name(x), parent(0), format(" ") {} ~htree_node() {} T name; //默认为两个空格 std::string format; node_type *parent; std::vector<node_type*> children; }; template<class T, class Container = htree_node<T> > class htree{ protected: typedef Container tree_node; public: htree() :root(0) { Init(); } htree(tree_node *node) :root(node) { Init(); } ~htree(){ destroy(root); } //pre_order_iterator class iterator{ public: iterator() : _node(0) , skip_current_children_(false) { skip_children(); } iterator(tree_node *node) : _node(node) , skip_current_children_(false) { skip_children(); } ~iterator() {} T& operator*() const { return _node->name; } T* operator->() const { return &(_node->name); } tree_node* get() { return _node; } //开始位置 iterator begin() const { return iterator(_node); } //结束位置 const???? iterator end() const { return iterator( _find_end(_node) ); } tree_node *_node; protected: bool skip_current_children_; void skip_children() { skip_current_children_=true; } tree_node* _find_end(tree_node* current) const { int pos = current->children.size()-1; if( pos<0 ) return (current); //这里返回iterator会被析构掉，临时对象 //从最后一个孩子找起， else _find_end(current->children[pos]); } }; public: //注意传position的引用 iterator insert(iterator& position, const T& x) { tree_node *tmp = new tree_node(x); position._node->children.push_back(tmp); tmp->parent = position._node; return iterator(tmp); } //后序递归输出 void post_recurs_render(tree_node* some, unsigned recurs_level) { for (unsigned i = 0; i < some->children.size(); i++) post_recurs_render(some->children[i], recurs_level+1); for (int i = 0; i<recurs_level; i++) cout << " "; cout << some->name << endl; } //先序递归输出 void pre_recurs_render(tree_node* some, unsigned recurs_level) { for (int i = 0; i<recurs_level; i++) cout << " "; cout << some->name << endl; for (unsigned i = 0; i < some->children.size(); i++) pre_recurs_render(some->children[i], recurs_level+1); } //利用stack //使用Transform格式化输出 void recurs_render(tree_node* some) { std::string temp; temp = form_stack.top() + some->format; form_stack.push(temp); cout << temp; cout << some->name; cout << endl; for (unsigned i = 0; i < some->children.size(); i++) recurs_render(some->children[i]); form_stack.pop(); } tree_node *root; private: void Init(){ form_stack.push(std::string(" ")); }; void destroy(tree_node *some) { #define SAFE_DELETE(p) {if(p){delete p; p=NULL;}} //后序删除 for (unsigned i = 0; i < some->children.size(); i++) destroy(some->children[i]); SAFE_DELETE(some); } std::stack<std::string> form_stack; }; 

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

int main()
{
    //for detecting the memory leaks
    int tmpFlag = _CrtSetDbgFlag( _CRTDBG_REPORT_FLAG );
    tmpFlag |= _CRTDBG_LEAK_CHECK_DF;
    _CrtSetDbgFlag( tmpFlag );

    typedef htree_node node_type;
    typedef htree tree_type;

    node_type *one = new node_type("one");

    tree_type::iterator iter(one);
    tree_type tr1(one);
    tree_type::iterator two = tr1.insert(iter, "two");
    tree_type::iterator three = tr1.insert(iter, "three");

    tr1.insert(two, "apple");
    tr1.insert(two, "banana");
    tr1.insert(two, "peach");

    tr1.insert(three, "china");
    tr1.insert(three, "england");

    //method 1：
    tr1.recurs_render(tr1.root);
    cout << "--------" << endl;

    //method 2:
    tr1.pre_recurs_render(tr1.root, 1);
    cout << "--------" << endl;

    //method 3:
    tr1.post_recurs_render(tr1.root, 1);
    cout << "--------" << endl;

    // test iterator::end() function
    cout << (* (iter.end()) ) << endl;

    return 0;
}

int main() { //for detecting the memory leaks int tmpFlag = _CrtSetDbgFlag( _CRTDBG_REPORT_FLAG ); tmpFlag |= _CRTDBG_LEAK_CHECK_DF; _CrtSetDbgFlag( tmpFlag ); typedef htree_node<string> node_type; typedef htree<string> tree_type; node_type *one = new node_type("one"); tree_type::iterator iter(one); tree_type tr1(one); tree_type::iterator two = tr1.insert(iter, "two"); tree_type::iterator three = tr1.insert(iter, "three"); tr1.insert(two, "apple"); tr1.insert(two, "banana"); tr1.insert(two, "peach"); tr1.insert(three, "china"); tr1.insert(three, "england"); //method 1： tr1.recurs_render(tr1.root); cout << "--------" << endl; //method 2: tr1.pre_recurs_render(tr1.root, 1); cout << "--------" << endl; //method 3: tr1.post_recurs_render(tr1.root, 1); cout << "--------" << endl; // test iterator::end() function cout << (* (iter.end()) ) << endl; return 0; }   

最终输出结果：

   one
     two
       apple
       banana
       peach
     three
       china
       england
--------
  one
    two
      apple
      banana
      peach
    three
      china
      england
--------
      apple
      banana
      peach
    two
      china
      england
    three
  one
--------
england