ta-mmh@cunixb.cc.columbia.edu (Margaret Helmuth) (02/11/90)
Does anyone know where I can get a C++ n-ary tree?
beard@ux1.lbl.gov (Patrick C Beard) (02/14/90)
In article <2866@cunixc.cc.columbia.edu> ta-mmh@cunixb.cc.columbia.edu (Margaret Helmuth) writes: # #Does anyone know where I can get a C++ n-ary tree? Well, here's one I wrote a little while back... It needs to learn how to balance itself, but it worked for me. /* Tree.h A general n-ary tree class. by Patrick Beard. */ #ifndef __TREE_CLASS__ #define __TREE_CLASS__ #include <stream.h> #ifndef nil #define nil (0) #endif class Tree { public: Tree(char *data=nil); // constructor creates a fresh one. ~Tree(); // destructor kills it. Tree* AppendChild(Tree* child); // add a child to end of list. Tree* PrependChild(Tree* child);// add a child to beginning of list. Tree* Remove(); // removes child from its parent. // access functions. Tree* Parent() { return parent; } Tree* Sibling() { return sibling; } Tree* operator[](int index); // get index'th child. (zero based). void Print(int tabs=0); // print out whole tree. // data access/storage functions. char* Retrieve() { return data; } void Store(char* storedData) { data = storedData; } Tree* Find(char* storedData); // find this string private: char* data; // data this node contains. Tree* parent; // our parent. Tree* children; // list of children. Tree* lastChild; // so appending is fast. Tree* sibling; // if we're in a list. }; #endif /* Tree.cp Implementation of n-ary tree class. by Patrick Beard. */ #include "Tree.h" Tree::Tree(char *nodeData) { data = nodeData; parent = nil; children = nil; sibling = nil; lastChild = nil; } Tree::~Tree() { // we have to remove reference to ourself from our parent. only clean way. if(parent) Remove(); // also better delete all children? for(Tree *child = children; child != nil; child = child->sibling) { delete child; } } Tree* Tree::AppendChild(Tree* child) { // set up pointers, etc. // add child to list of children. if(!children) { children = lastChild = child; } else { lastChild->sibling = child; lastChild = child; } // update who this child's parent is. child->parent = this; return child; } Tree* Tree::PrependChild(Tree* child) { child->sibling = children; children = child; child->parent = this; return child; } Tree* Tree::Remove() { // remove references to us from siblings and parent. Tree *child, *prev = nil; for(child = parent->children; child != nil; child = child->sibling) { if(child == this) break; prev = child; // remember for linked list. } if(child) { if(prev) prev->sibling = child->sibling; else children = child->sibling; if(child == lastChild) lastChild = prev; child->sibling = nil; child->parent = nil; } return child; } Tree* Tree::operator[](int index) { Tree *child = children; while(child != nil && index--) child = child->sibling; return child; } Tree* Tree::Find(char* storedData) { if(strcmp(storedData, data)==0) return this; if(children) { for(Tree *child = children; child != nil; child = child->sibling) { if(child->Find(storedData)) return child; } } return nil; } void Tree::Print(int tabs) { for(register int i=0; i<tabs; i++) cout << "\t"; cout << data << "\n"; for(Tree *child = children; child != nil; child = child->sibling) { child->Print(tabs+1); } } ------------------------------------------------------------------------------- - Patrick Beard, Macintosh Programmer (beard@lbl.gov) - - Berkeley Systems, Inc. ".......<dead air>.......Good day!" - Paul Harvey - -------------------------------------------------------------------------------