Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!hellgate.utah.edu!helios.ee.lbl.gov!ux1.lbl.gov!beard
From: beard@ux1.lbl.gov (Patrick C Beard)
Newsgroups: comp.lang.c++
Subject: Re: Tree Needed
Message-ID: <4845@helios.ee.lbl.gov>
X-Local-Date: 14 Feb 90 01:01:59 PST
Date: 14 Feb 90 09:01:59 GMT
References: <2866@cunixc.cc.columbia.edu>
Sender: usenet@helios.ee.lbl.gov
Reply-To: beard@ux1.lbl.gov (Patrick C Beard)
Organization: Lawrence Berkeley Laboratory, Berkeley
Lines: 169

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