Trees for Storage and Search

Dr. Lawlor, CS 202, CS, UAF

Like linked lists, trees are a recursively defined data structure. Here's a linked list, with recursive traversal and construction functions:

class llnode {
public:
	int data;
	llnode *next;
	llnode(int v,llnode *n) {data=v; next=n;}
};
int total(llnode *cur,int sum)
{
	if (cur==0) { return sum; } // base case
	else { return total(cur->next,cur->data + sum); }
}
llnode *make_list(void) {
	int x;
	if (cin>>x) { return new llnode(x,make_list()); }
	else { return NULL; }
}
int foo(void) {
	llnode *cur=make_list();
	return total(cur,0);
}

(Try this in NetRun now!)

Here's a tree. It's like a linked list with *two* next pointers, called "child pointers". One child is the left subtree, and the other is the right subtree. One or both of the "child" pointers might be NULL. Because you've got two children, this is called a "binary tree"; if you've got four children (for example, "topleft", "topright", "bottomleft", and "bottomright"), it'd be a "4-ary tree". To traverse the tree, you just need to recurse down both the left and the right subtrees.

class treenode {
public:
	int data;
	treenode *left;
	treenode *right;
	treenode(int v,treenode *l,treenode *r) {data=v; left=l; right=r;}
};
int total(treenode *cur)
{
	if (cur==0) { return 0; } // base case
	else { return cur->data + total(cur->left) + total(cur->right); }
}
treenode *make_tree(void) {
	int x;
	if (cin>>x && x>=0) { 
		treenode *left=make_tree();
		treenode *right=make_tree();
		return new treenode(x,left,right); 
	}
	else { return NULL; }
}
int foo(void) {
	treenode *cur=make_tree();
	return total(cur);
}

(Try this in NetRun now!)

This program is a little weird, because you need to give the input data (cin>>x) in a very particular order--in a preorder traversal of the tree.

A more common way to build and look up trees is by ordering the children--for example, we can store values greater than ours in our right child; and values smaller than ours in the left child. This way of building the tree makes it much more efficient to look up values--rather than look at both children, we can compare the value to ours, and know exactly where to look. This is called a "binary search tree". Here's a more detailed explanation of how to build a binary search tree.

class treenode {
public:
	int data;
	treenode *left; // values < than data
	treenode *right; // values > than data
	treenode(int v,treenode *l,treenode *r) {data=v; left=l; right=r;}
};
// Return the treenode containing this value
treenode *lookup(treenode *cur,int value)
{
	if (cur==0) { return NULL; } // base case (not found)
	else { 
		if (value<cur->data) return lookup(cur->left,value);
		else if (value>cur->data) return lookup(cur->right,value);
		else /* value==cur->data */ return cur;
	}
}
void printtree(treenode *cur,int level)
{
	if (cur==0) return;
	printtree(cur->left,level+1);

	for (int i=0;i<level;i++) cout<<"  ";
	cout<<cur->data<<"\n";

	printtree(cur->right,level+1);
}
void add_to_tree(int x,treenode *&cur) {
	if (cur==0) cur=new treenode(x,0,0);
	else if (x<cur->data) add_to_tree(x,cur->left);
	else if (x>cur->data) add_to_tree(x,cur->right);
	else /* x==cur->data */ {
		std::cout<<"Error! Duplicate value "<<x<<" in tree!\n";
		exit(1);
	}
}
treenode *make_tree(void) {
	treenode *cur=0;
	int x;
	while (cin>>x) add_to_tree(x,cur);
	return cur;
}
int foo(void) {
	treenode *cur=make_tree();
	printtree(cur,0);
	treenode *v7=lookup(cur,7);
	treenode *v9=lookup(cur,9);
	std::cout<<"found 7 at "<<v7<<" and 9 at "<<v9<<"\n";
	return 0;
}

(Try this in NetRun now!)

You can even extract a range of values, which come out sorted for free.

class treenode {
public:
	int data;
	treenode *left;
	treenode *right;
	treenode(int v,treenode *l,treenode *r) {data=v; left=l; right=r;}
};
int total(treenode *cur)
{
	if (cur==0) { return 0; } // base case
	else { return cur->data+total(cur->left)+total(cur->right); }
}
treenode *make_tree(void) {
	int x;
	if (cin>>x && x>=0) { return new treenode(x,make_tree(),make_tree()); }
	else { return NULL; }
}
void print_tree(treenode *cur,int level) {
	if (cur==NULL) return;

	for (int i=0;i<level;i++) cout<<"  ";
	cout<<cur->data<<"\n";

	print_tree(cur->left,level+1);


	print_tree(cur->right,level+1);
}
treenode *find(treenode *cur,int value) {
	if (cur==NULL) return NULL; // base case: not found
	if (value<cur->data) return find(cur->left,value);
	if (value>cur->data) return find(cur->right,value);
	return cur;
}
void print_range(treenode *cur,int lo,int hi) {
	if (cur==NULL) {return;} // base case: not found
	if (lo<cur->data) print_range(cur->left,lo,hi);
	if (lo<=cur->data && cur->data<hi) cout<<" found at "<<cur->data<<"\n";
	if (hi>cur->data) print_range(cur->right,lo,hi);
}
int foo(void) {
	treenode *cur=make_tree();
	print_tree(cur,0);
	for (int value=0;value<10;value++) cout<<"Tree has "<<value<<" at "<<find(cur,value)<<"\n";
	print_range(cur,-10000000,1000000000);
	return total(cur);
}

(Try this in NetRun now!)

Trees come up again and again in computer science--searching is often much faster in a tree!