偶看新闻有70万元如何理财:想用C++写一个多叉树的结构
来源：百度文库 编辑：偶看新闻 时间：2024/05/10 19:36:56
要抛弃原来C的思想，用C++标准的东西写一颗树
主要找到以下两个不同的代码实现： 先研究第一个
一个简单的多叉树实现：
利用迭代器方便地构建树，
可以递归输出，前序，后序。
利用栈实现输出。
销毁树只能后序遍历
类的定义：
view plaincopy to clipboardprint?
#include
#include
#include
#include
#include
using namespace std;
template
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 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; icout << " ";
cout << some->name << endl;
}
//先序递归输出
void pre_recurs_render(tree_node* some, unsigned recurs_level)
{
for (int i = 0; icout << " ";
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;
};
下面是main函数里的测试代码：
view plaincopy to clipboardprint?
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;
}
最终输出结果：
view plaincopy to clipboardprint?
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
C++树的实现
STL里面没有提供容器树的模板实现，自已写一个：
Tree.h
view plaincopy to clipboardprint?
//tree.h 头文件
#include
主要找到以下两个不同的代码实现： 先研究第一个
一个简单的多叉树实现：
利用迭代器方便地构建树，
可以递归输出，前序，后序。
利用栈实现输出。
销毁树只能后序遍历
类的定义：
view plaincopy to clipboardprint?
#include
#include
#include
#include
#include
using namespace std;
template
class htree_node{
public:
typedef htree_node
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
};
template
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 << some->name << endl;
}
//先序递归输出
void pre_recurs_render(tree_node* some, unsigned recurs_level)
{
for (int i = 0; i
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
};
下面是main函数里的测试代码：
view plaincopy to clipboardprint?
int main()
{
//for detecting the memory leaks
int tmpFlag = _CrtSetDbgFlag( _CRTDBG_REPORT_FLAG );
tmpFlag |= _CRTDBG_LEAK_CHECK_DF;
_CrtSetDbgFlag( tmpFlag );
typedef htree_node
typedef htree
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;
}
最终输出结果：
view plaincopy to clipboardprint?
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
C++树的实现
STL里面没有提供容器树的模板实现，自已写一个：
Tree.h
view plaincopy to clipboardprint?
//tree.h 头文件
#include
#include
using namespace std;
struct TreeNode; //定义一个结构体原型
classTree; //定义一个类原型
classIterator; //定义一个类原型
typedef list
TreeNode* clone(TreeNode*,List&,TreeNode*);//Clone复制函数
struct TreeNode{
int_data; //数据
TreeNode* _parent; //父节点
List_children; //子节点
TreeNode(int,TreeNode*); //构造函数
void SetParent(TreeNode&); //设置父节点
void InsertChildren(TreeNode&); //插入子节点
};
classTree{
public:
//下面是构造器和运算符重载
Tree(); //默认构造函数
Tree(constTree&); //复制构造函数
Tree(constint); //带参数构造函数
Tree(constint,constlist
~Tree(); //析构函数
Tree& operator=(constTree&); //=符号运算符重载
bool operator==(constTree&); //==符号运算符重载
bool operator!=(constTree&); //!=符号运算符重载
//下面是成员函数
void Clear(); //清空
boolIsEmpty()const; //判断是否为空
intSize()const; //计算节点数目
intLeaves(); //计算叶子数
intRoot()const; //返回根元素
intHeight(); //计算树的高度
//下面是静态成员函数
static boolIsRoot(Iterator); //判断是否是根
static boolisLeaf(Iterator); //判断是否是叶子
static IteratorParent(Iterator); //返回其父节点
static intNumChildren(Iterator); //返回其子节点数目
//跌代器函数
Iteratorbegin(); //Tree Begin
Iteratorend(); //Tree End
friend classIterator; //Iterator SubClass
private:
list
list
intheight(TreeNode*);
intlevel(TreeNode*,Iterator);
};
//This is TreeSub Class Iterator
classIterator{
private:
Tree* _tree; //Tree data
list
public:
Iterator(); //默认构造函数
Iterator(constIterator&); //复制构造函数
Iterator(Tree*,TreeNode*); //构造函数
Iterator(Tree*,list
//运算符重载
void operator=(constIterator&); //赋值运算符重载
bool operator==(constIterator&); //关系运算符重载
bool operator!=(constIterator&); //关系运算符重载
Iterator& operator++(); //前缀++运算符
Iterator operator++(int); //后缀++运算符
int operator*()const; //获得节点信息
bool operator!(); //赋值运算符重载
typedef list
friend classTree;
};
Tree.cpp
view plaincopy to clipboardprint?
//tree.cpp 实现文件
#include "Tree.h"
//***** 下面是对于TreeNode结构体的定义实现*****///
TreeNode::TreeNode(inttype= 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(constinttype){
_nodes.push_back(new TreeNode(type));
}
Tree::Tree(constTree& t){
if(t._nodes.empty())return;
clone(t._nodes.front(),_nodes,0);
}
Tree::Tree(constinttype,constlist
TreeNode* root = new TreeNode(type);//建立根节点
_nodes.push_back(root);//放入树中
list
for(it = lit.begin();it!=lit.end();it++){
if(!((*it)->_nodes.empty())){//如果当前节点元素不为空
Tree* tp = newTree(**it);
TreeNode* p = tp->_nodes.front();
root->_children.push_back(p); //设置根的子节点
p->_parent = root; //设置节点的父节点为根
list
list
list
_nodes.insert(lit3,lit1,lit2);
}
}
}
Tree::~Tree(){
for(list
delete* it;
}
}
Tree& Tree::operator =(constTree & t){
Clear();
Tree* p = newTree(t);
_nodes = p->_nodes;
return *this;
}
boolTree::operator ==(constTree& t){
if(_nodes.size()!=t._nodes.size()){
return false;
}
list
list
while(it!=_nodes.end()&&_it!=t._nodes.end()){
if((*it)->_data!=(*_it)->_data){
return false;
}
it++;
_it++;
}
return true;
}
boolTree::operator !=(constTree& t){
if(_nodes.size()!=_nodes.size()){
return true;
}
else{
list
list
while(it!=_nodes.end()&&_it!=t._nodes.end()){
if((*it)->_data!=(*_it)->_data){
return true;
}
it++;
_it++;
}
return false;
}
}
void Tree::Clear(){
for(list
delete* it;
}
_nodes.clear();
}
boolTree::IsEmpty()const{
return _nodes.empty();
}
intTree::Size()const{
return (int)_nodes.size();
}
intTree::Leaves(){
inti = 0;
list
while(it!=_nodes.end()){
if((*it)->_children.size()==0){
i++;
}
it++;
}
return i;
}
intTree::Height(){
if(_nodes.size()!=0){
TreeNode* TNode = _nodes.front();
return height(TNode);
}
else{
return -1; //判断为空树
}
}
intTree::height(TreeNode* node){
if(!node){
return -1;
}
else{
list
if(plist.size()==0){
return 0;
}
inthA = 0;
for(list
inthB = height(*it);
if(hB>hA){
hA = hB;
}
}
return hA+1;
}
}
IteratorTree::begin(){
return Iterator(this,_nodes.begin());
}
IteratorTree::end(){
return Iterator(this,_nodes.end());
}
intTree::Root()const{
return (*_nodes.begin())->_data;
}
boolTree::IsRoot(Iteratorit){
TreeNode p = *it;
if(p._parent == 0){
return true;
}
return false;
}
boolTree::isLeaf(Iteratorit){
TreeNode p = *it;
if(p._children.size() == 0){
return true;
}
return false;
}
IteratorTree::Parent(Iteratorit){
TreeNode p = *it;
Tree* t = it._tree;
IteratorIte(t,p._parent);
return Ite;
}
intTree::NumChildren(Iteratorit){
TreeNode p = *it;
return (int)p._children.size();
}
//***** 下面是对于Tree::Iterator类的定义实现*****///
Iterator::Iterator(){
}
Iterator::Iterator(constIterator& it){
_tree = it._tree;
_lit = it._lit;
}
Iterator::Iterator(Tree* t, TreeNode* n){
_tree = t;
list
_lit = find(nodes.begin(),nodes.end(),n);//
}
Iterator::Iterator(Tree * t, list
_tree = t;
_lit = lt;
}
void Iterator::operator =(constIterator& it){
_tree = it._tree;
_lit = it._lit;
}
boolIterator::operator ==(constIterator & it){
return _tree == it._tree && _lit == it._lit;
}
boolIterator::operator !=(constIterator & it){
return _tree != it._tree || _lit != it._lit;
}
Iterator& Iterator::operator ++(){
++_lit;
return *this;
}
IteratorIterator::operator ++(int){
Iteratorit(*this);
++_lit;
return it;
}
intIterator::operator *() const{
return ((*_lit)->_data);
}
boolIterator::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
cl.push_back(clone(*lt,nodes,cp));
}
return cp;
}
一个C语言选择结构的问题?
[c]一个关于循环结构的问题
C结构一个问题
一个c结构程序问题
C结构一个问题11111111111111324
一个关于C语言结构体的问题
推荐一个用vb写cs结构程序的教程
阐述C程序的三个结构?顺序,选择,循环结构??
要用C设计一个信息管理系统主要有哪几大的结构啊？
求助！用javascript写一个包含2层子节点的的树形结构！
书上写的c语言的结构太罗嗦了，谁能帮我简述一下即概括一下．
仿照句式，以“只有”开头，写一个结构与之相似的复句
C语言-结构问题，会的请进
[c]和循环结构有关的问题
[c]关于循环结构的问题2
按要求写“ABB”结构的词语。
组织结构的英文怎么写?
脲酶的化学结构是怎么写
帮忙写一个C程序
用C写一个目录和文件的数据结构
怎样用c写一个算21点的程序
C语言中，结构体中的元素可不可以是另外一个结构体阿？
什么是组织结构？一个服装公司的组织结构是什么？
写一个完整的程序使用循环结构计算1+3+5+…+99的和并输出运算结果。（