Εκτέλεση βασικών λειτουργιών δομής δυαδικού δέντρου

Χρήσιμοι σύνδεσμοι:
www.wikipedia.org/wiki/Tree_traversal
www.wikipedia.org/wiki/Binary_tree

#include<stdio.h>
#include<stdlib.h>

struct tree
{
	int info;
	struct tree *left;
	struct tree *right;
};

typedef struct tree TREE;

TREE *insert(TREE *, int);
void inorder(TREE *);
void postorder(TREE *);
void preorder(TREE *);
TREE *delete(TREE *, int);
TREE *search(TREE *);

int main(void)
{
	TREE *root;
	int choice, item, item_no;
	root = NULL;

	int option = 1;

	while (option)
	{
		printf("\n BINARY TREE OPERATION\n\n");
		printf(" --------------------- Menu -----------------------\n\n");
		printf(" Command	Help\n\n");
		printf(" 1. INSERT	(Insert node in Tree)\n");
		printf(" 2. DELETE	(Delete node from Tree)\n");
		printf(" 3. INORDER	(Inorder traversal of tree)\n");
		printf(" 4. POSTORDER	(Postorder traversal of tree)\n");
		printf(" 5. PREORDER	(Preorder traversal of tree)\n");
		printf(" 6. REPLACE	(Search and replace node in Tree)\n");
		printf(" 7. EXIT		\n\n");
		printf(" --------------------------------------------------\n\n");
		printf(" Please enter a choice from the menu: ");
		scanf("%d", &choice);

		switch (choice)
		{
		case 1:
				printf("\n Enter new element: ");
				scanf("%d", &item);
				root = insert(root, item);
				printf("\n root is %d", root->info);
				printf("\n Inorder traversal of binary tree is : ");
				inorder(root);
				break;
		case 2:
				printf("\n Enter the element to be deleted : ");
				scanf(" %d", &item_no);
				root = delete(root, item_no);
				inorder(root);
				break;
		case 3:
				printf("\n Inorder traversal of binary tree is : ");
				inorder(root);
				break;
		case 4:
				printf("\n Postorder traversal of binary tree is : ");
				postorder(root);
				break;
		case 5:
				printf("\n Preorder traversal of binary tree is : ");
				preorder(root);
				break;
		case 6:
				root = search(root);
				break;
		case 7:	
				return;
		} /* end of switch */

		fflush(stdin);

		printf("\n\n ________________________________________\n");
		printf("\n Do you want to continue(Type 0 or 1)?: ");
		scanf("%d", &option);
		
		system("cls"); /* replace "cls" with "clear" in linux*/
	}

	return(0);
}

/* Insert node in Binary Tree */
TREE *insert(TREE *root, int x)
{
	if (!root)
	{
		root = (TREE*)malloc(sizeof(TREE));
		root->info = x;
		root->left = NULL;
		root->right = NULL;
		return(root);
	}
	if (root->info > x)
		root->left = insert(root->left, x);
	else
	{
		if (root->info < x)
			root->right = insert(root->right, x);
	}
	return(root);
}

/* Delete node from Binary Tree */
TREE *delete(TREE *ptr, int x)
{
	TREE *p1, *p2;
	if (!ptr)
	{
		printf("\n Node not found ");
		return(ptr);
	}
	else
	{
		if (ptr->info < x)
		{
			ptr->right = delete(ptr->right, x);
		}
		else if (ptr->info >x)
		{
			ptr->left = delete(ptr->left, x);
			return ptr;
		}
		else
		{
			if (ptr->info == x)
			{
				if (ptr->left == ptr->right) /* for example, a leaf node */
				{
					free(ptr);
					return(NULL);
				}
				else if (ptr->left == NULL)  /* a right subtree */
				{
					p1 = ptr->right;
					free(ptr);
					return p1;
				}
				else if (ptr->right == NULL)   /* a left subtree */
				{
					p1 = ptr->left;
					free(ptr);
					return p1;
				}
				else
				{
					p1 = ptr->right;
					p2 = ptr->right;
					while (p1->left != NULL)
						p1 = p1->left;
					p1->left = ptr->left;
					free(ptr);
					return p2;
				}
			}
		}
	}
	return(ptr);
}

/* Inorder traversal of Binary Tree */
void inorder(TREE *root)
{
	if (root != NULL)
	{
		inorder(root->left);
		printf(" %d", root->info);
		inorder(root->right);
	}
	return;
}

/* Postorder traversal of Binary Tree */
void postorder(TREE *root)
{
	if (root != NULL)
	{
		postorder(root->left);
		postorder(root->right);
		printf(" %d", root->info);
	}
	return;
}

/* Preorder traversal of Binary Tree */
void preorder(TREE *root)
{
	if (root != NULL)
	{
		printf(" %d", root->info);
		preorder(root->left);
		preorder(root->right);
	}
	return;
}

/* Search and replace node in Binary Tree */
TREE *search(TREE *root)
{
	int no, i, ino;
	TREE *ptr;
	ptr = root;
	printf("\n Enter the element to be searched :");
	scanf(" %d", &no);
	fflush(stdin);
	while (ptr)
	{
		if (no>ptr->info)
			ptr = ptr->right;
		else if (no<ptr->info)
			ptr = ptr->left;
		else
			break;
	}
	if (ptr)
	{
		printf("\n Element %d is found and is = %d", no, ptr->info);
		printf("\n Do you want to replace it (press 1 for yes) ?: ");
		scanf(" %d", &i);
		if (i == 1)
		{
			printf("\n Enter the new element :");
			scanf(" %d", &ino);
			ptr->info = ino;
		}
		else
			printf("\n\t Not any changes made to the binary tree");
	}
	else
		printf("\n Element %d does not exist!", no);
	return(root);
}
ċ
binary-tree-operations-exe.zip
(180k)
Dimitrios Rousis,
9 Μαρ 2014, 8:45 π.μ.
ċ
tree.c
(5k)
Dimitrios Rousis,
8 Μαρ 2014, 10:06 π.μ.