|
#ifndef _TREE_H_
#define _TREE_H_
/* Copyright - All copyright is owned by Mr Jack Hui
Author : Jack, Hui Ho Yin
Email : jackhui@hotmail.com, jackhui@hongkong.com
Update : 27-Aug-2000, 10-Aug-2002*/
#pragma warning(disable : 4786) //debug info - name too long
#include <vector>
#include
#include <string>
#include <iostream>
// Support TEMPLATE CLASS sorted_vector
#include <algorithm>
#include <utility>
#include <functional>
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 k,="" bool="" bnoduplicates="false,class" pr="std::less<K">, class A = std::allocator<k> >
class sorted_vector ;
//
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
sorted_vector<treenode<key,t> *> m_children; //holds pointers for children
sorted_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
}
};
//It erases a child from a Node without delete the node, and without remove
//linking from the tree, so it can still be accessed from the tree's find().
void EraseChild(Tree_iterator<key, t=""> &itr)
{
vector<treenode<key,t>*>::iterator pchild;
map<key, treenode<key,t="">*>::iterator itrmap;
TreeNode<key,t> *pNode = itr.m_Node->second;
itrmap = m_LinkedTree->m_nodemap.find(pNode->m_key);
//erase reference from the child vector
for(pchild=m_children.begin();pchild != m_children.end(); pchild++)
{
if( (*pchild)->m_key == pNode->m_key)
{
m_children.erase(pchild);
break;
}
}
}
//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 sorted_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.insert(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;
}
//--- add by mry 2004
iterator AddChild (const Key parent, const Key nm, const T x) {
iterator px,_tmp;
px = find(parent);
if ( px != end())
_tmp = AddChild (px, nm, x);
return _tmp;
}
TreeNode<key,t>& SetRoot (const Key nm, const T x) {
TreeNode<key,t>* pNode;
//Èç¹ûÒѾÓÐÁ˸ù½Úµã£¬É¾³ýËùÓÐ
if (m_pTreeroot) {
m_pTreeroot->DeleteAllChildren();
delete m_pTreeroot;
}
//È»ºó´´½¨¸ù½Úµã
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;
//·µ»Ø¸ù½Úµã
return GetRoot();
}
//end of add
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
}
}
//It sets root to be the pivot in Walk Down, first node is the first child
void SetWalkDownSubTreePivot(iterator& itr)
{
m_WalkPivot = itr.m_Node->second;
m_WalkCurrent = m_WalkPivot;
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
}
//It sets root to be the pivot in Walk Down, first node is the first child
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 {
//if it's the last child of parent, we go up to the level
//which we still need processing by recurively call ourself
if (m_WalkCurrent == m_WalkPivot)
return false; //no more child
m_WalkCurrent = m_WalkCurrent->m_parent;
m_WalkParent = m_WalkCurrent->m_parent;
SubTreeWalkDown();
}
return true;
}
void DelSubTree() {
}
//It moves a tree from source to destination. After moving a tree, tree walking will be invalid.
//However iterator will still be valid. Users has to Set the new root pivot again.
void MoveSubTree(iterator& dest_parent, iterator& src)
{
TreeNode<key,t>* pSrcNode;
TreeNode<key,t>* pDestNode;
TreeNode<key,t>* pSrcNodeParent;
pSrcNode = src.m_Node->second;
pSrcNodeParent = pSrcNode->m_parent;
//remove reference from original parent
pSrcNodeParent->EraseChild(src);
//add the src sub tree to destination parent node
pDestNode = dest_parent.m_Node->second;
pDestNode->AddChild(pSrcNode);
iterator itr;
itr = find(pSrcNode->m_key);
//setting up correct level
SetWalkDownSubTreePivot(itr);
while (SubTreeWalkDown())
{
m_WalkCurrent->m_level = m_WalkCurrent->m_parent->m_level + 1;
}
}
T SubTreeGetData(void) { return m_WalkCurrent->m_data; }
T SubTreeGetLevel(void) { return m_WalkCurrent->m_level; }
}; //class Tree
//************ End of Tree declaration ***************************//
//
//Actually, the interator is just a copy of the iterator to a std::map hold in
//the tree to provide simple navigation ability.
template <class key,="" class="" t="">
class Tree_iterator
{
typedef map<key, treenode<key,t="">*>::iterator _map_it;
public:
_map_it m_Node;
T operator*() const { return (m_Node->second)->GetData(); }
Tree_iterator& operator++() {
m_Node++;
return *this;
}
Tree_iterator operator++(int) {
Tree_iterator __tmp = *this;
m_Node++;
return __tmp;
}
Tree_iterator& operator--() {
m_Node--;
return *this;
}
bool operator==(const Tree_iterator& _y) const {
return m_Node == _y.m_Node;
}
bool operator!=(const Tree_iterator& _y) const {
return m_Node != _y.m_Node;
}
}; //class Tree_iterator
// TEMPLATE CLASS sorted_vector
template<class k,="" bool="" bnoduplicates="false,class" pr="std::less<K">, class A = std::allocator<k> >
class sorted_vector
{
public:
typedef sorted_vector<k,bnoduplicates,pr,a> Myt_;
typedef std::vector<k,a> Cont;
typedef Cont::allocator_type allocator_type;
typedef Cont::size_type size_type;
typedef Cont::difference_type difference_type;
typedef Cont::reference reference;
typedef Cont::const_reference const_reference;
typedef Cont::value_type value_type;
typedef K key_type;
typedef Cont::iterator iterator;
typedef Cont::const_iterator const_iterator;
typedef Pr key_compare;
typedef Pr value_compare;
typedef Cont::const_reverse_iterator
const_reverse_iterator;
typedef Cont::reverse_iterator reverse_iterator;
typedef std::pair<iterator, iterator=""> Pairii_;
typedef std::pair<const_iterator, const_iterator=""> Paircc_;
typedef std::pair<iterator, bool=""> Pairib_;
explicit sorted_vector(const Pr& pred = Pr(),const A& al = A())
:key_compare_(pred),vec_(al){}
#if (_MSC_VER >= 1300)
template<class it="">
sorted_vector(It first, It beyond,
const Pr& pred = Pr(),const A& al = A())
:key_compare_(pred),vec_(first,beyond,al)
{stable_sort();}
#else
sorted_vector(const_iterator first, const_iterator beyond,
const Pr& pred = Pr(),const A& al = A())
:key_compare_(pred),vec_(first,beyond,al)
{stable_sort();}
#endif
sorted_vector(const Myt_& x)
: vec_(x.vec_),key_compare_(x.key_compare_)
{}
~sorted_vector() {}
Myt_& operator=(const Myt_& x) {vec_.operator=(x.vec_);
key_compare_= x.key_compare_;
return *this;}
Myt_& operator=(const Cont& x){vec_.operator=(x);
sort();return *this;}
void reserve(size_type n) {vec_.reserve(n);}
iterator begin() {return vec_.begin(); }
const_iterator begin() const {return vec_.begin(); }
iterator end() {return vec_.end();}
const_iterator end() const {return vec_.end();}
reverse_iterator rbegin() {return vec_.rbegin();}
const_reverse_iterator rbegin() const
{return vec_.rbegin();}
reverse_iterator rend() {return vec_.rend();}
const_reverse_iterator rend() const
{return vec_.rend();}
size_type size() const {return vec_.size();}
size_type max_size() const {return vec_.max_size();}
bool empty() const {return vec_.empty();}
A get_allocator() const {return vec_.get_allocator();}
const_reference at(size_type p) const {return vec_.at(p);}
reference at(size_type p) {return vec_.at(p);}
const_reference operator[](size_type p) const
{return vec_.operator[](p);}
reference operator[](size_type p) {return vec_.operator[](p);}
reference front() {return vec_.front();}
const_reference front() const {return vec_.front();}
reference back() {return vec_.back();}
const_reference back() const {return vec_.back();}
void pop_back() {vec_.pop_back();}
void assign(const_iterator first, const_iterator beyond)
{vec_.assign(first,beyond);}
void assign(size_type n, const K& x = K())
{vec_.assign(n,x);}
/*insert members*/
Pairib_ insert(const value_type& x)
{
if(bNoDuplicates){
iterator p= lower_bound(x);
if(p==end()||key_compare_(x,*p)){
return Pairib_(InsertImpl_(p,x),true);
}else{
return Pairib_(p,false);
}
}else{
iterator p= upper_bound(x);
return Pairib_(InsertImpl_(p,x),true);
}
}
iterator insert(iterator it, const value_type& x)//it is the hint
{
if(it!=end() ){
if(bNoDuplicates){
if(key_compare_(*it,x)){
if((it+1)==end()||KeyCompare_Gt_(*(it+1),x)){//use hint
return InsertImpl_(it+1,x);
}else if(KeyCompare_Geq_(*(it+1),x)){
return end();
}
}
}else{
if( KeyCompare_Leq_(*it,x)
&&((it+1)==end()||KeyCompare_Geq_(*(it+1),x))){
return InsertImpl_(it+1,x);
}
}
}
return insert(x).first;
}
#if (_MSC_VER >= 1300)
template<class it="">
void insert(It first, It beyond)
{
size_type n= std::distance(first,beyond);
reserve(size()+n);
for( ;first!=beyond;++first){
insert(*first);
}
}
#else
void insert(const_iterator first, const_iterator beyond)
{
size_type n= std::distance(first,beyond);
reserve(size()+n);
for( ;first!=beyond;++first){
insert(*first);
}
}
#endif
iterator erase(iterator p) {return vec_.erase(p);}
iterator erase(iterator first, iterator beyond)
{return vec_.erase(first,beyond);}
size_type erase(const K& key)
{
Pairii_ begEnd= equal_range(key);
size_type n= std::distance(begEnd.first,begEnd.second);
erase(begEnd.first,begEnd.second);
return n;
}
void clear() {return vec_.clear();}
bool Eq_(const Myt_& x) const
{return (size() == x.size()
&& std::equal(begin(), end(), x.begin())); }
bool Lt_(const Myt_& x) const
{return (std::lexicographical_compare(begin(), end(),
x.begin(), x.end()));}
void swap(Myt_& x)
{vec_.swap(x.vec_);std::swap(key_compare_,x.key_compare_);}
friend void swap(Myt_& x, Myt_& Y_)
{x.swap(Y_); }
key_compare key_comp() const {return key_compare_; }
value_compare value_comp() const {return (key_comp()); }
iterator find(const K& k)
{ iterator p = lower_bound(k);
return (p==end()||key_compare_(k, *p))? end():p;
}
const_iterator find(const K& k) const
{const_iterator p = lower_bound(k);
return (p==end()||key_compare_(k,*p))?end():p;}
size_type count(const K& k) const
{Paircc_ Ans_ = equal_range(k);
size_type n = std::distance(Ans_.first, Ans_.second);
return (n); }
iterator lower_bound(const K& k)
{return std::lower_bound(begin(), end(), k, key_compare_); }
const_iterator lower_bound(const K& k) const
{return std::lower_bound(begin(), end(), k, key_compare_); }
iterator upper_bound(const K& k)
{return std::upper_bound(begin(), end(), k, key_compare_); }
const_iterator upper_bound(const K& k) const
{return std::upper_bound(begin(), end(), k, key_compare_); }
Pairii_ equal_range(const K& k)
{return std::equal_range(begin(), end(), k, key_compare_); }
Paircc_ equal_range(const K& k) const
{return std::equal_range(begin(), end(), k, key_compare_); }
/*functions for use with direct std::vector-access*/
Cont& get_container()
{return vec_;}
void sort()//restore sorted order after low level access
{ std::sort(vec_.begin(),vec_.end(),key_compare_);
if( bNoDuplicates ){
vec_.erase(Unique_(),vec_.end());
}
}
void stable_sort()//restore sorted order after low level access
{ std::stable_sort(vec_.begin(),vec_.end(),key_compare_);
if( bNoDuplicates ){
erase(Unique_(),end());
}
}
protected:
iterator Unique_()
{ iterator front_= vec_.begin(),out_= vec_.end(),end_=vec_.end();
bool bCopy_= false;
for(iterator prev_; (prev_=front_)!=end_ && ++front_!=end_; ){
if( key_compare_(*prev_,*front_)){
if(bCopy_){
*out_= *front_;
out_++;
}
}else{
if(!bCopy_){out_=front_;bCopy_=true;}
}
}
return out_;
}
iterator InsertImpl_(iterator p,const value_type& x)
{return vec_.insert(p,x);}
bool KeyCompare_Leq_(const K& ty0,const K& ty1)
{return !key_compare_(ty1,ty0);}
bool KeyCompare_Geq_(const K& ty0,const K& ty1)
{return !key_compare_(ty0,ty1);}
bool KeyCompare_Gt_(const K& ty0,const K& ty1)
{return key_compare_(ty1,ty0);}
key_compare key_compare_;
Cont vec_;
};//class sorted_vector
template<class k,bool="" bnoduplicates,class="" pr,="" class="" a=""> inline
bool operator==(const sorted_vector<k, bnoduplicates,pr,a="">& x,
const sorted_vector<k, bnoduplicates,pr,a="">& Y_)
{return x.Eq_(Y_); }
template<class k,bool="" bnoduplicates,class="" pr,="" class="" a=""> inline
bool operator!=(const sorted_vector<k, bnoduplicates,pr,a="">& x,
const sorted_vector<k, bnoduplicates,pr,a="">& Y_)
{return !(x == Y_); }
template<class k,bool="" bnoduplicates,class="" pr,="" class="" a=""> inline
bool operator<(const sorted_vector<k, bnoduplicates,pr,a="">& x,
const sorted_vector<k, bnoduplicates,pr,a="">& Y_)
{return x.Lt_(Y_);}
template<class k,bool="" bnoduplicates,class="" pr,class="" a=""> inline
bool operator>(const sorted_vector<k, bnoduplicates,pr,a="">& x,
const sorted_vector<k, bnoduplicates,pr,a="">& Y_)
{return Y_ < x; }
template<class k,bool="" bnoduplicates,class="" pr,="" class="" a=""> inline
bool operator<=(const sorted_vector<k, bnoduplicates,pr,a="">& x,
const sorted_vector<k, bnoduplicates,pr,a="">& Y_)
{return !(Y_ < x); }
template<class k,="" bool="" bnoduplicates,class="" pr,class="" a=""> inline
bool operator>=(const sorted_vector<k, bnoduplicates,pr,a="">& x,
const sorted_vector<k, bnoduplicates,pr,a="">& Y_)
{return (!(x < Y_)); }
}; //namespace Tiffany
#endif //_TREE_H_
|
|
|
|
|
{
//Post Order Walk Test
Tiffany::Tree<wstring, string=""> x(L"Node 1", "Root");
Tiffany::Tree<wstring, string="">::iterator px;
Tiffany::Tree<wstring, string="">::iterator px1;
Tiffany::Tree<wstring, string="">::iterator px2;
px = x.AddChild(L"Key1","A");
px1 = x.AddChild(px, L"Key2", "1");
x.AddChild(px1, L"Key3", "a");
px2 = x.AddChild(px1, L"Key4", "b");
x.AddChild(px2, L"Key5", "I");
x.AddChild(px2, L"Key6", "II");
x.AddChild(px1, L"Key7", "c");
px1 = x.AddChild(px, L"Key8", "2");
x.AddChild(px1, L"Key9", "d");
px = x.AddChild(L"Key10","B");
px1 = x.AddChild(px, L"Key11","3");
x.AddChild(px1, L"Key12", "e");
x.AddChild(px1, L"Key13", "f");
px = x.AddChild(L"Key14", "C");
px1 = x.AddChild(px, L"Key15", "4");
x.AddChild(px1, L"Key16", "g");
px = x.begin();
for ( px = x.begin( ) ; px != x.end( ) ; px++ )
{
cout << *px << endl;
}
//mry test
px = x.find(L"Key100");
if (px == x.end())
cout << "Not find to Key100" << endl;
else
{
cout << "The element of Tree m1 with a key of Key100 is: "
<< *px << endl;
px1 = x.AddChild(px, L"Key111","3");
}
px = x.AddChild(L"Key12",L"Key141", "soleman");
if (px == x.end())
cout << "Not find to Key100" << endl;
for ( px = x.begin( ) ; px != x.end( ) ; px++ )
{
cout << *px << endl;
}
//end mry test
x.SetPostOrderRootPivot();
// x.SetSubTreePivot(px);
cout << "Data is: " << x.SubTreeGetData().c_str() << endl;
for (int i=1; i<18; i++) {
x.SubTreePostOrderWalk();
cout << "Data is: " << x.SubTreeGetData().c_str() << endl;
}
// x.PostOrderWalk();
//move from subtree [b] to under [g]
px1 = x.find(L"Key4");
px2 = x.find(L"Key16");
x.MoveSubTree(px2, px1);
x.SetWalkDownRootPivot();
cout << "After moving tree" << endl;
cout << "Data is: " << x.SubTreeGetData().c_str() << endl;
for (int j=1; j<18; j++) {
x.SubTreeWalkDown();
cout << "Data is: " << x.SubTreeGetData().c_str() << endl;
}
}
|
|
|
|
|
Is it possible(and how) to convert this to managed C++ because I'd like to make a .NET assembly?
Best regards
|
|
|
|
|
I could try to convert this to C# but my knowledges of C++ don't go this far
|
|
|
|
|
sorry, it doesn't have a C# version. For C#, you can use two Hashtable tables to do the same things.
For creating a tree structure in C#. It's quite easy.
You can create the tree nodes which contains a collection of tree nodes.
Hiya, Everybody ^^
|
|
|
|
|
How can I move subtree [b] to [g]? (in your figure)
Could you tell me the way to do it?
|
|
|
|
|
Okay, I've added a new MoveSubTree function.
You can use it as:
px1 = x.find(L"Key4");
px2 = x.find(L"Key16");
x.MoveSubTree(px2, px1);
x.SetWalkDownRootPivot();
cout << "After moving tree" << endl;
cout << "Data is: " << x.SubTreeGetData().c_str() << endl;
for (int i=1; i<17; i++) {
x.SubTreeWalkDown();
cout << "Data is: " << x.SubTreeGetData().c_str() << endl;
The new CPP file is here.
#ifndef _TREE_H_
#define _TREE_H_
#pragma warning(disable : 4786) //debug info - name too long
#include <vector>
#include <map>
#include <string>
#include <iostream>
using namespace std;
namespace Tiffany {
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
{
friend class Tree<Key, T>;
protected:
T m_data;
Key m_key;
int m_level;
TreeNode<Key,T>* m_parent;
vector<TreeNode<Key,T> *> m_children;
vector<TreeNode<Key,T> *>::iterator m_current;
Tree<Key, T>* m_LinkedTree;
public:
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;
};
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);
}
};
void EraseChild(Tree_iterator<Key, T> &itr)
{
vector<TreeNode<Key,T>*>::iterator pchild;
map<Key, TreeNode<Key,T>*>::iterator itrmap;
TreeNode<Key,T> *pNode = itr.m_Node->second;
itrmap = m_LinkedTree->m_nodemap.find(pNode->m_key);
for(pchild=m_children.begin();pchild != m_children.end(); pchild++)
{
if( (*pchild)->m_key == pNode->m_key)
{
m_children.erase(pchild);
break;
}
}
}
TreeNode<Key,T>& GetParent () const {
return *m_parent;
};
const vector<TreeNode<Key,T>*>& GetChildren () const
{
return m_children;
};
long ChildCount () const
{
return m_children.size();
};
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; }
};
template <class Key, class T>
class Tree {
friend class TreeNode<Key, T>;
protected:
map<Key, TreeNode<Key,T>*> m_nodemap;
TreeNode<Key,T>* m_pTreeroot;
TreeNode<Key,T>* m_WalkPivot;
TreeNode<Key,T>* m_WalkCurrent;
TreeNode<Key,T>* m_WalkParent;
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) {
}
Tree (const Key nm, const T x) {
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;
}
}
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(); }
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;
}
}
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;
}
}
void SetWalkDownSubTreePivot(iterator& itr) {
m_WalkPivot = itr.m_Node->second;
m_WalkCurrent = m_WalkPivot;
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
}
void SetWalkDownRootPivot() {
m_WalkPivot = m_pTreeroot;
m_WalkCurrent = m_WalkPivot;
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
}
bool SubTreePostOrderWalk() {
if (m_WalkCurrent == m_WalkPivot)
return false;
if (++m_WalkParent->m_current != m_WalkParent->m_children.end()) {
m_WalkCurrent = *(m_WalkParent->m_current);
while (m_WalkCurrent->m_children.size() != 0) {
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
m_WalkParent = m_WalkCurrent;
m_WalkCurrent = *(m_WalkCurrent->m_current);
}
}
else {
m_WalkCurrent = m_WalkParent;
m_WalkParent = m_WalkCurrent->m_parent;
}
m_WalkParent = m_WalkCurrent->m_parent;
return true;
}
bool SubTreeWalkDown() {
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++;
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
}
else {
if (m_WalkCurrent == m_WalkPivot)
return false;
m_WalkCurrent = m_WalkCurrent->m_parent;
m_WalkParent = m_WalkCurrent->m_parent;
SubTreeWalkDown();
}
return true;
}
void DelSubTree() {
}
void MoveSubTree(iterator& dest_parent, iterator& src)
{
TreeNode<Key,T>* pSrcNode;
TreeNode<Key,T>* pDestNode;
TreeNode<Key,T>* pSrcNodeParent;
pSrcNode = src.m_Node->second;
pSrcNodeParent = pSrcNode->m_parent;
pSrcNodeParent->EraseChild(src);
pDestNode = dest_parent.m_Node->second;
pDestNode->AddChild(pSrcNode);
iterator itr;
itr = find(pSrcNode->m_key);
SetWalkDownSubTreePivot(itr);
while (SubTreeWalkDown())
{
m_WalkCurrent->m_level = m_WalkCurrent->m_parent->m_level + 1;
}
}
T SubTreeGetData(void) { return m_WalkCurrent->m_data; }
T SubTreeGetLevel(void) { return m_WalkCurrent->m_level; }
};
template <class Key, class T>
class Tree_iterator
{
typedef map<Key, TreeNode<Key,T>*>::iterator _map_it;
public:
_map_it m_Node;
T operator*() const { return (m_Node->second)->GetData(); }
Tree_iterator& operator++() {
m_Node++;
return *this;
}
Tree_iterator operator++(int) {
Tree_iterator __tmp = *this;
m_Node++;
return __tmp;
}
Tree_iterator& operator--() {
m_Node--;
return *this;
}
bool operator==(const Tree_iterator& _y) const {
return m_Node == _y.m_Node;
}
bool operator!=(const Tree_iterator& _y) const {
return m_Node != _y.m_Node;
}
};
};
#endif //_TREE_H_
|
|
|
|
|
the new code you posted does not compile, any chance you could post a working version of this code.
TIA
|
|
|
|
|
Here's an algorithm to generalize binary trees:
Simply add a linked list(the nodes of which are tree-nodes) as one of the members of each node. On each traversal of a treenode,traverse the nodes of it's associated linked list. It's not hard to see that each node of a treenode's associated linked list, is a subtree the parent of which is the tree node.
|
|
|
|
|
I used map to do it, so we can do quick find of an element by the key.
Jack
|
|
|
|
|