Add your own alternative version
Stats
96.2K views 1.6K downloads 34 bookmarked
Posted
28 May 2002

Comments and Discussions



How to remove node by it iterator?
example:
test.cpp
class test_tree
{
~test_tree();
tree
but test_tree destructor crashes.
I think, that node deletes not correctly.
Anton.





How to delete a leafnode? for 'f'.





I've been looking at a similar problem myself recently (under Design Patterns, Composites and Visitors). I like the way you keep track of all nodes in the tree so that you can do fast iterations ignoring the structure of the tree. I just think it is a bit of a shame that you 2 treewalking methods do not also use STLlike iterators. I have tried to move a step closer to this with my article and I implement a treewalking STL iterator and a shallow STL iterator that iterates over the nodes at one level. However, I didn't implement different walk strategies for the deep iterator, nor did I implement a fast iterator. One quite neat thing in my system though was that the tree is also the node and vice versa. To iterate over a subtree you simply call begin from a different node.
My solution to the different walk strategies was to provide mixins to a separate visitor class hierarchy. This used the shallow iterators to walk the tree in different orders  but I don't think that solution is necessarily ideal. I think the perfect STL Compliant Composite Tree is out there somewhere  I'm just not sure that either of us have it yet!
Nice work anyway.
Dave_H





Thanks ... Actually, the one I posted here is not the final version, but nearly the same. I'm lazy to update this article.
It's failing to compiling in VS.net 2003, and I'll fix it and post it here again.
Jack Hui





Jack,
I suspect your compilation problem in VS.Net 2003 is to do with a breaking change between .Net 2002 and .Net 2003. In order to make the compiler standards compliant, MS had to make this particular change. Basically, any templatised type that uses the scope resolution operator has to be prefixed with the keyword typename . In the version on the site this means 2 lines have to be amended:
typename vector
typedef typename map
I'm pretty sure that the reason for this is to mean that the compiler does not have to precompile sections of the template prior to it actually being used.
Dave H





I am interested in solutions for this as well.
Have you seen
www.damtp.cam.ac.uk/user/kp229/tree/tree.hh ?





I've just spent a little while browsing that solution. It looks quite good, but I think there are a few weaknesses:
1) It's a container, not a composite, the same as Jack Hui's solution. The only problem with this is if the classes being put into the tree need to know about their location. This is often the case with many trees such as expression trees or similar. It doesn't mean the container isn't valid, but it does provide a different perspective. Have a look at my article at Composites and Visitors.
2) It is protected under the GPL, which because of its viral nature pretty much precludes it from being used in any of my commercial work. I do wish that people would put library code under the LGPL, because on a large number of occasions, I have had to ignore a library because it is GPL'd.
Dave





\tree.h(338): error C2146: syntax error : missing ';' before identifier '_map_it'
\tree.h(338): error C2146: syntax error : missing ';' before identifier '_map_it'
tree.h(338): error C2146: syntax error : missing ';' before identifier '_map_it'
tree.h(338): error C2146: syntax error : missing ';' before identifier '_map_it'
tree.h(36): error C2146: syntax error : missing ';' before identifier 'm_current'
tree.h(36): error C2146: syntax error : missing ';' before identifier 'm_current'
tree.h(36): error C2146: syntax error : missing ';' before identifier 'm_current'
tree.h(36): error C2146: syntax error : missing ';' before identifier 'm_current'
tree.h(341): error C2146: syntax error : missing ';' before identifier 'm_Node'
tree.h(341): error C2146: syntax error : missing ';' before identifier 'm_Node'
tree.h(341): error C2146: syntax error : missing ';' before identifier 'm_Node'
tree.h(341): error C2146: syntax error : missing ';' before identifier 'm_Node'
tree.h(338): error C2501: 'Tiffany::Tree_iterator





Hi,
The typename keyword is required if a dependent name is to be treated as a type. This is a breaking change in the Visual C++ .NET 2003 compiler, made in order to conform to the ISO C++ standard.
In the class "TreeNode", define a new type for iterator to current child. Remember to include "typename":
template <class Key, class T> class TreeNode { typedef typename vector<TreeNode<Key,T> *>::iterator _point_it;
...
_point_it m_current; //holds iterator to current child processing
...
In the class "Tree_iterator", simply add "typename" in "_map_it" type definition:
template <class Key, class T> class Tree_iterator { typedef typename map<Key, TreeNode<Key,T>*>::iterator _map_it;
...





I'm working on an unrelated project but happened to get this article in a google search. I just wanted to say thanks to the poster above for that valuable information. I have been banging my head for 6 hours to get some old VC6 code to compile in Visual Studio 8. You saved me a sleepless night. Thanks!
(Who would've thought that Microsoft would actually write an ISO compliant compiler! There is a lot of broken code out there thanks to their crappy implementations in the past)





#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 : 27Aug2000, 10Aug2002*/
#pragma warning(disable : 4786) //debug info  name too long
#include





{
//Post Order Walk Test
Tiffany::Tree





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 treenodes) 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







General News Suggestion Question Bug Answer Joke Praise Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

