home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power-Programmierung
/
CD1.mdf
/
magazine
/
progjour
/
1991
/
04
/
bstree.c
< prev
next >
Wrap
C/C++ Source or Header
|
1991-06-03
|
3KB
|
98 lines
/* bstree.c */
/* This is a simple implementation of a Binary Search Tree. A tree is a
special case of the more general structure, the directed graph. A complete
implementation would require more features, including memory management,
error handling, and some utility functions. For example, if one were
to use a binary search tree in an embedded system application, it would
be necessary to include a "free list" handling function. This algorithm
does not include a capability to keep the nodes of the tree balanced.
Consequently, a realistic implementation would also include some balancing
algorithm such as the AVL method. Using the fundamental ideas of the
binary search tree, try to implement an "expression tree" */
#include <stdio.h>
struct NODE
{
int data;
struct NODE *left;
struct NODE *right;
} ;
#define TREESIZE 100
#define NUL 0
void filltree(struct NODE *tree);
void insert (struct NODE *tree, struct NODE *newnode);
void inorder(struct NODE *tree);
void postorder(struct NODE *tree);
int getnumber();
void main()
{
struct NODE numbers[TREESIZE];
filltree(numbers); /* insert items into tree */
inorder(numbers); /* display tree using inorder traversal */
postorder(numbers); /* display tree using postorder traversal */
}
void filltree (struct NODE *tree)
{
int index = 0;
int num;
while ((num=getnumber()) != -1) {
tree[index].data = num;
tree[index].left = tree[index].right = NUL;
if (index > 0) insert (tree, &tree[index]);
index++;
}
}
int getnumber()
{
int num;
printf("\n Enter Positive Integer (-1 to end): ");
scanf("%d", &num);
return(num);
}
void insert (struct NODE *tree, struct NODE *newnode)
{
if (newnode->data < tree->data) {
if (tree->left == NUL)
tree->left = newnode;
else
insert (tree->left, newnode);
}
else {
if (tree->right == NUL)
tree->right = newnode;
else
insert (tree->right, newnode);
}
}
void inorder (struct NODE *tree)
{
/* notice the placement of printf */
if (tree->left != NUL)
inorder (tree->left); /* call left child again */
printf ("%d\n", tree->data); /* visit the node */
if (tree->right != NUL)
inorder (tree->right); /* call right child again */
}
void postorder (struct NODE *tree)
{
/* notice the placement of printf */
if (tree->left != NUL) /* call left child again */
postorder (tree->left);
if (tree->right != NUL)
postorder (tree->right); /* call right child again */
printf ("%d\n", tree->data); /* visit the node */
}