[数据结构与算法]c 二叉树模拟

头文件 tree.h

#ifndef _TREE_H_
#define _TREE_H_

#include <stdbool.h>

#define SLEN 20

typedef struct item
{
	char petname[SLEN];
	char petkind[SLEN];
} Item;

#define MAXITEMS 10

typedef struct trnode
{
	Item item;
	struct trnode* left;
	struct trnode* right;
} Trnode;

typedef struct tree
{
	Trnode* root;
	int size;
} Tree;

/**
* 操作： 把树初始化为空
* 前置条件： ptree指向一个树
* 后置条件： 树被初始化为空
*/
void InitializeTree(Tree* ptree);

/**
* 操作： 确定树是否为空
* 前置条件： ptree指向一个树
* 后置条件： 如果为空返回true，否则返回false
*/
bool TreeIsEmpty(const Tree* ptree);

/**
* 操作： 确定树是否已满
* 前置条件： ptree指向一个树
* 后置条件： 如果已满返回true，否则返回false
*/
bool TreeIsFull(const Tree* ptree);

/**
* 操作：返回树的项数
* 前置条件： ptree指向一个树
* 后置条件： 返回树的项数
*/
int TreeItemCount(const Tree* ptree);

/**
* 操作：在树中添加一个项
* 前置条件： ptree指向一个树， pi是待添加项的地址
* 后置条件： 添加成功返回true，否则返回false
*/
bool AddItem(const Item* pi, Tree* ptree);

/**
* 操作：在树中查找一个项
* 前置条件： ptree指向一个树， pi是待查找项
* 后置条件： 存在返回true，否则返回false
*/
bool InTree(const Item* pi, const Tree* ptree);

/**
* 操作：在树中删除一个项
* 前置条件： ptree指向一个树， pi是待删除项的地址
* 后置条件： 删除成功返回true，否则返回false
*/
bool DeleteItem(const Item* pi, Tree* ptree);

/**
* 操作：把函数应用于每一个项
* 前置条件： ptree指向一个树， pfunc是一个函数
* 后置条件： pfunc指向的这个函数为树中的每一项执行一次
*/
void Traverse(const Tree* ptree, void(*pfunc)(Item item));

/**
* 操作：删除树中的所有内容
* 前置条件： ptree指向一个树
* 后置条件： 清空树
*/
void DeleteAll(Tree* ptree);

#endif

实现文件 tree.c

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

typedef struct pair
{
	Trnode* parent;
	Trnode* child;
} Pair;

static Trnode* MakeNode(const Item* pi);
static bool ToLeft(const Item* i1, const Item* i2);
static bool ToRight(const Item* i1, const Item* i2);
static void AddNode(Trnode* newNode, Trnode* root);
static void InOrder(const Trnode* root, void(*pfunc)(Item item));
static Pair SeekItem(const Item* pi, const Tree* ptree);
static void DeleteNode(Trnode** ptr);
static void DeleteAllNodes(Trnode* ptr);

void InitializeTree(Tree* ptree)
{
	ptree->root = NULL;
	ptree->size = 0;
}

bool TreeIsEmpty(const Tree* ptree)
{
	if (ptree->root == NULL) {
		return true;
	} 
	return false;
}

bool TreeIsFull(const Tree* ptree)
{
	if (ptree->size == MAXITEMS) {
		return true;
	}
	return false;
}

int TreeItemCount(const Tree* ptree)
{
	return ptree->size;
}

bool AddItem(const Item* pi, Tree* ptree)
{
	Trnode* newNode;

	if (TreeIsFull(ptree)) {
		fprintf(stderr, "Tree is full\n");
		return false;
	}

	if (SeekItem(pi, ptree).child != NULL) {
		fprintf(stderr, "Attempted to add duplicate item\n");
		return false;
	}

	newNode = MakeNode(pi);
	if (newNode == NULL) {
		fprintf(stderr, "Could not create node\n");
		return false;
	}

	ptree->size++;

	if (ptree->root == NULL) {
		ptree->root = newNode;
	}
	else {
		AddNode(newNode, ptree->root);
	}

	return true;
}

bool InTree(const Item* pi, const Tree* ptree)
{
	return (SeekItem(pi, ptree).child == NULL) ? false : true;
}

bool DeleteItem(const Item* pi, Tree* ptree)
{
	Pair look;

	look = SeekItem(pi, ptree);
	if (look.child == NULL) {
		return false;
	}

	if (look.parent == NULL) {
		DeleteNode(&ptree->root);
	}
	else if (look.parent->left == look.child) {
		DeleteNode(&look.parent->left);
	}
	else {
		DeleteNode(&look.parent->right);
	}
	ptree->size--;

	return true;
}

void Traverse(const Tree* ptree, void(*pfunc)(Item item)) 
{
	if (ptree != NULL) {
		InOrder(ptree->root, pfunc);
	}
}

void DeleteAll(Tree* ptree)
{
	if (ptree != NULL) {
		DeleteAllNodes(ptree->root);
	}
	ptree->root = NULL;
	ptree->size = 0;
}

static void InOrder(const Trnode* root, void(*pfunc)(Item item))
{
	if (root != NULL) {
		InOrder(root->left, pfunc);
		(*pfunc)(root->item);
		InOrder(root->right, pfunc);
	}
}

static void DeleteAllNodes(Trnode* ptr)
{
	Trnode* pright;

	if (ptr != NULL) {
		pright = ptr->right;
		DeleteAllNodes(ptr->left);
		free(ptr);
		DeleteAllNodes(pright);
	}
}

static void AddNode(Trnode* newNode, Trnode* root)
{
	if (ToLeft(&newNode->item, &root->item)) {
		if (root->left == NULL) {
			root->left = newNode;
		}
		else {
			AddNode(newNode, root->left);
		}
	} 
	else if (ToRight(&newNode->item, &root->item)) {
		if (root->right == NULL) {
			root->right = newNode;
		}
		else {
			AddNode(newNode, root->right);
		}
	}
	else {
		fprintf(stderr, "Location error in AddNode()\n");
		exit(1);
	}
}

static bool ToLeft(const Item* i1, const Item* i2)
{
	int comp1 = 0;

	if ((comp1 = strcmp(i1->petname, i2->petname)) < 0) {
		return true;
	}
	else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) < 0) {
		return true;
	}
	return false;
}

static bool ToRight(const Item* i1, const Item* i2)
{
	int comp1 = 0;

	if ((comp1 = strcmp(i1->petname, i2->petname)) > 0) {
		return true;
	}
	else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) > 0) {
		return true;
	}
	return false;
}

static Trnode* MakeNode(const Item* pi)
{
	Trnode* newNode;

	newNode = (Trnode*)malloc(sizeof(Trnode));
	if (newNode != NULL) {
		newNode->item = *pi;
		newNode->left = NULL;
		newNode->right = NULL;
	}

	return newNode;
}

static Pair SeekItem(const Item* pi, const Tree* ptree)
{
	Pair look;
	look.parent = NULL;
	look.child = ptree->root;

	if (look.child == NULL) {
		return look;
	}

	while (look.child != NULL) {
		if (ToLeft(pi, &(look.child->item))) {
			look.parent = look.child;
			look.child = look.child->left;
		}
		else if (ToRight(pi, &(look.child->item))) {
			look.parent = look.child;
			look.child = look.child->right;
		}
		else {
			break;
		}
	}

	return look;
}



static void DeleteNode(Trnode** ptr)
{
	Trnode* temp;
	if ((*ptr)->left == NULL) {
		temp = *ptr;
		*ptr = (*ptr)->right;
		free(temp);
	}
	else if ((*ptr)->right == NULL) {
		temp = *ptr;
		*ptr = (*ptr)->left;
		free(temp);
	}
	else {
		for (temp = (*ptr)->left; temp->right != NULL; temp = temp->right) {
			continue;
		}
		temp->right = (*ptr)->right;
		temp = *ptr;
		*ptr = (*ptr)->left;
		free(temp);
	}
}

测试 main.c

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "tree.h"

char menu(void);
void addPet(Tree* pt);
void dropPet(Tree* pt);
void showPets(const Tree* pt);
void findPet(const Tree* pt);
void printItem(Item item);
void uppercase(char* ch);
char* s_gets(char* st, int n);

int main(void)
{
	Tree pets;
	char choice;

	InitializeTree(&pets);

	while ((choice = menu()) != 'q') {
		switch (choice)
		{
		case 'a':
			addPet(&pets);
			break;
		case 'l':
			showPets(&pets);
			break;
		case 'f':
			findPet(&pets);
			break;
		case 'n':
			printf("%d pets in club\n", TreeItemCount(&pets));
			break;
		case 'd':
			dropPet(&pets);
			break;
		default:
			puts("Switching error\n");
			break;
		}
	}

	DeleteAll(&pets);
	puts("Done!\n");

	return 0;
}

char menu(void)
{
	int ch;

	puts("Nerfville Pet Club Membership Program");
	puts("Enter the letter corresponding to your choice: ");
	puts("a) add a pet           l) show list of pets");
	puts("n) number of pets      f) find pets");
	puts("d) delete a pet        q) quit");

	while ((ch = getchar()) != EOF) {
		while (getchar() != '\n') {
			continue;
		}
		ch = tolower(ch);
		if (strchr("alrfndq", ch) == NULL) {
			puts("Please enter an a, l, f, n, d, q:");
		}
		else {
			break;
		}
	}

	if (ch == EOF) {
		ch = 'q';
	}

	return ch;
}

void addPet(Tree* pt)
{
	Item temp;

	if (TreeIsFull(pt)) {
		puts("No room in the club!\n");
	}
	else {
		puts("Please enter name of pet:");
		s_gets(temp.petname, SLEN);
		puts("Please enter pet kind:");
		s_gets(temp.petkind, SLEN);

		uppercase(temp.petname);
		uppercase(temp.petkind);
		AddItem(&temp, pt);
	}
}

void showPets(const Tree* pt)
{
	if (TreeIsEmpty(pt)) {
		puts("No entries\n");
	}
	else {
		Traverse(pt, printItem);
	}
}

void printItem(Item item)
{
	printf("Pet: %-19s Kind: %-19s\n", item.petkind, item.petkind);
}

void findPet(const Tree* pt)
{
	Item temp;
	if (TreeIsEmpty(pt)) {
		puts("No entries\n");
		return;
	}

	puts("Please enter name of pet you wish to find: ");
	s_gets(temp.petname, SLEN);
	puts("Please enter kind: ");
	s_gets(temp.petkind, SLEN);

	uppercase(temp.petname);
	uppercase(temp.petkind);
	printf("%s the %s ", temp.petname, temp.petkind);
	if (InTree(&temp, pt)) {
		printf("is a member\n");
	}
	else {
		printf("is not a member\n");
	}
}

void dropPet(Tree* pt)
{
	Item temp;
	if (TreeIsEmpty(pt)) {
		puts("No entries\n");
		return;
	}

	puts("Please enter name of pet you wish to find: ");
	s_gets(temp.petname, SLEN);
	puts("Please enter kind: ");
	s_gets(temp.petkind, SLEN);

	uppercase(temp.petname);
	uppercase(temp.petkind);
	printf("%s the %s ", temp.petname, temp.petkind);

	if (DeleteItem(&temp, pt)) {
		puts("is dropped from the club\n");
	}
	else {
		puts("is not a member\n");
	}
}

void uppercase(char* str)
{
	while (*str) {
		*str = toupper(*str);
		str++;
	}
}

char* s_gets(char* st, int n)
{
	char* ret_val;
	char* find;

	ret_val = fgets(st, n, stdin);
	if (ret_val) {
		find = strchr(st, '\n');
		if (find) {
			*find = '\0';
		}
		else {
			while (getchar() != '\n') {
				continue;
			}
		}
	}
	return ret_val;
}

来自《c primer plus》