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

作者: admin 分类: C++ 发布时间: 2019-12-02 13:37

一个简单的多叉树实现:

  1. 利用迭代器方便地构建树,

  2. 可以递归输出,前序,后序。

  3. 利用栈实现输出。

  4. 销毁树只能后序遍历

类的定义:

// Node.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#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;
};
int _tmain(int argc, _TCHAR* argv[])
{
//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;
getchar();
return 0;
}

2019-12-02_133401.png

转载:

版权声明:本文为CSDN博主「ryfdizuo」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。

原文链接:https://blog.csdn.net/ryfdizuo/article/details/3968596

如果觉得我的文章对您有用,请随意赞赏。您的支持将鼓励我继续创作!

发表评论

标签云