数据结构学习

avl.h:

#ifndef _AVL_H
#define _AVL_H
typedef struct node *Position;
typedef Position AVLtree;

typedef struct node
{
	int height;
	AVLtree left;
	AVLtree right;
	int data;
}node;

int Height(Position p); //return the height of a node
Position SingleRotateWithRight(Position k2); //left rotate when in RR operation
Position SingleRotateWithLeft(Position k2); // LL
Position DoubleRotateWithLeft(Position k3); // LR
Position DoubleRotateWithRight(Position k3); // RL
Position Rotate(Position k);
AVLtree insert(AVLtree root, int data); //Insert operation
Position search(AVLtree root, int data);
AVLtree delete(AVLtree root, int data);
void inorder_print(AVLtree root);
void dispose(AVLtree root); //free the tree
#endif

avl.c:

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#include "avl.h"
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char const *argv[])
{
	AVLtree root = NULL;
	char choice;
	printf("Welcome to the AVL tree program\n");
	while (1) {
		printf("Please make a choice\n");
		printf("----------------------\n");
		printf("i. insert an element\n");
		printf("p. print the tree\n");
		printf("d. delete an element from the tree\n");
		printf("f. find an element \n");
		printf("q. quit the program\n");
		printf("----------------------\n");

		/*get rid of '\n' in buffer*/
		if ((choice = getchar()) == '\n')
			choice = getchar();

		int number;
		Position p;
		switch (choice) {
			case 'i':
				printf("Which number to insert?\n");
				scanf("%d", &number);
				root = insert(root, number);
				break;
			case 'p':
				printf("The tree is \n");
				printf("######################\n");
				inorder_print(root);
				printf("######################\n");
				break;
			case 'd':
				printf("Which number to delete?\n");
				scanf("%d", &number);
				root = delete(root, number);
				break;
			case 'f':
				printf("Which number to find?\n");
				scanf("%d", &number);
				if (p = search(root, number)) {
					printf("%d is found\n", number);
				}
				else
					printf("Not found\n");
				break;
			case 'q':
				printf("Byebye!\n");
				dispose(root);
				goto QUIT;
			default:
				printf("Wrong choice! Please try again\n");
				break;
		}
	}
	QUIT: return 0;
}

int Height(Position p) {
	if (p == NULL)
		return -1;
	else
		return p->height;
}

Position SingleRotateWithRight(Position k2) {
	Position k1 = k2->right;
	k2->right = k1->left;
	k1->left = k2;

	k1->height = MAX(Height(k1->left), Height(k1->right)) + 1;
	k2->height = MAX(Height(k2->left), Height(k2->right)) + 1;
	return k1;
}

Position SingleRotateWithLeft(Position k2) {
	Position k1 = k2->left;
	k2->left = k1->right;
	k1->right = k2;

	k2->height = MAX(Height(k2->left), Height(k2->right)) + 1;
	k1->height = MAX(Height(k1->left), Height(k1->right)) + 1;
	return k1;
}

Position DoubleRotateWithLeft(Position k3) {
	k3->left = SingleRotateWithRight(k3->left);
	return SingleRotateWithLeft(k3);
}

Position DoubleRotateWithRight(Position k3) {
	k3->right = SingleRotateWithLeft(k3->right);

	return SingleRotateWithRight(k3);
}

Position Rotate(Position k) {
	if (Height(k->left) - Height(k->right) == 2) {
		if (Height(k->left->left) >= Height(k->left->right)) {
			k = SingleRotateWithLeft(k);
		}
		else {
			k = DoubleRotateWithLeft(k);
		}
	}

	if (Height(k->right) - Height(k->left) == 2) {
		if (Height(k->right->right) >= Height(k->right->left)) {
			k = SingleRotateWithRight(k);
		}
		else {
			k = DoubleRotateWithRight(k);
		}
	}

	return k;
}

AVLtree insert(AVLtree root, int data) {
	if (root == NULL) {
		/*if the tree is empty then create a node*/
		root = (node*)malloc(sizeof(node));
		root->left = root->right = NULL;
		root->data = data;
		root->height = 0;
	}

	else if (data < root->data) {
		root->left = insert(root->left, data);
		if (Height(root->left) - Height(root->right) == 2) {
			if (data < root->left->data) {
				root = SingleRotateWithLeft(root);
			}
			else {
				root = DoubleRotateWithLeft(root);
			}
		}
	}
	else if (data > root->data) {
		root->right = insert(root->right, data);
		if (Height(root->right) - Height(root->left) == 2) {
			if (data > root->right->data) {
				root = SingleRotateWithRight(root);
			}
			else {
				root = DoubleRotateWithRight(root);
			}
		}
	}
	else {
		/*data already exsits*/
		fprintf(stderr, "%d exsits\n", data);
	}

	root->height = MAX(Height(root->left), Height(root->right)) + 1;

	return root;
}

Position search(AVLtree root, int data) {
	if (root == NULL) {
		return root;
	}

	if (root->data == data)
		return root;
	else if (root->data < data) {
		return search(root->right, data);
	}
	else {
		return search(root->left, data);
	}
}

AVLtree delete(AVLtree root, int data) {
	if (root == NULL) {
		fprintf(stderr, "Not found\n");
		return NULL;
	}

	else if (data == root->data) {
		if (root->right == NULL) {
			/*if right child is NULL then delete it*/
			Position temp = root;
			root = root->left;
			free(temp);
			printf("%d is deleted\n", data);
		}
		else {
			Position temp = root->right;
			while (temp->left) {
				temp = temp->left;
			}

			root->data = temp->data;
			root->right = delete(root->right, temp->data);
			root->height = MAX(Height(root->left), Height(root->right)) + 1;
			printf("%d is deleted\n", data);
		}

		return root;
	}

	else if (data < root->data) {
		root->left = delete(root->left, data);
	}
	else {
		root->right = delete(root->right, data);
	}

	if (root->left) {
		root->left = Rotate(root->left);
	}
	if (root->right) {
		root->right = Rotate(root->right);
	}

	root = Rotate(root);
	root->height = MAX(Height(root->left), Height(root->right)) + 1;

	return root;
}

void inorder_print(AVLtree root) {
	if (root != NULL) {
		inorder_print(root->left);
		printf("%d\n", root->data);
		inorder_print(root->right);
	}
}

void dispose(AVLtree root)
{
    if( root != NULL )
    {
        dispose( root->left );
        dispose( root->right );
        free( root );
    }
}