鸟语天空

抽象数据类型(ADT)——二叉查找树

作者：追风剑情 发布于：2020-4-24 13:21 分类：C

示例：储存宠物

tree.h

//#pragma once
/* tree.h -- 二叉查找数			  */
/*			 树中不允许有重复的项 */
#ifndef _TREE_H_
#define _TREE_H_
#include <stdbool.h>

/* 根据具体情况重新定义 Item */
#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);

/* 操作：		在树中添加一个项			*/
/* 前提条件：	pi是待添加项的地址			*/
/*				ptree指向一个已初始化的树	*/
/* 后置条件：	如果可以添加，该函数将在树中添加一个项  */
/*				并返回true；否则，返回false 			*/
bool AddItem(const Item * pi, Tree * ptree);

/* 操作：		在树中查找一个项			*/
/* 前提条件：	pi指向一个项				*/
/*				ptree指向一个已初始化的树	*/
/* 后置条件：	如果在树中找到一个项，该函数返回true  */
/*				否则，返回false 			*/
bool InTree(const Item * pi, const Tree * ptree);

/* 操作：		从树中删除一个项			*/
/* 前提条件：	pi是删除项的地址			*/
/*				ptree指向一个已初始化的树	*/
/* 后置条件：	如果从树中成功删除一个项，该函数返回true  */
/*				否则，返回false 			*/
bool DeleteItem(const Item * pi, Tree * ptree);

/* 操作：		把函数应用于树中的每一项	*/
/* 前提条件：	ptree指向一个树				*/
/*				pfun指向一个函数			*/
/*				该函数接受一个Item类型的参数，并无返回值 */
/* 后置条件：	pfun指向的这个函数为树中的每一项执行一次 */
void Traverse(const Tree * ptree, void(*pfun)(Item item));

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

#endif

tree.c

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

/* 局部数据类型 */
typedef struct pair {
	Trnode * parent;
	Trnode * child;
} Pair;

/* 局部函数 */

/* 处理动态内存分配和初始化节点 */
static Trnode * MakeNode(const Item * pi);
/* 添加新节点 */
static void AddNode(Trnode * new_node, Trnode * root);
/* 是否应该将新节点添加到左边 */
static bool ToLeft(const Item * i1, const Item *i2);
/* 是否应该将新节点添加到右边 */
static bool ToRight(const Item * i1, const Item *i2);
/* 定位pi节点应放在树中的位置 */
static Pair SeekItem(const Item * pi, const Tree * ptree);
/* 删除指定节点 */
static void DeleteNode(Trnode **ptr);
/* 遍历树 */
static void InOrder(const Trnode * root, void(*pfun)(Item item));
/* 删除所有节点 */
static void DeleteAllNodes(Trnode * root);

/* 函数定义 */

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

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

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

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

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

	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;
	}
	new_node = MakeNode(pi);
	if (new_node == NULL)
	{
		fprintf(stderr, "Couldn't create node\n");
		return false;
	}
	/* 成功创建了一个新节点 */
	ptree->size++;

	if (ptree->root == NULL)		/* 情况1：树为空 */
		ptree->root = new_node;
	else
		AddNode(new_node, 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(*pfun)(Item item))
{
	if (ptree != NULL)
		InOrder(ptree->root, pfun);
}

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

static Trnode * MakeNode(const Item * pi)
{
	Trnode * new_node;
	new_node = (Trnode *)malloc(sizeof(Trnode));
	if (new_node != NULL)
	{
		new_node->item = *pi;
		new_node->left = NULL;
		new_node->right = NULL;
	}
	return new_node;
}

static void AddNode(Trnode * new_node, Trnode * root)
{
	if (ToLeft(&new_node->item, &root->item))
	{
		if (root->left == NULL)
			root->left = new_node;
		else
			AddNode(new_node, root->left);
	}
	else if (ToRight(&new_node->item, &root->item))
	{
		if (root->right == NULL)
			root->right = new_node;
		else
			AddNode(new_node, root->right);
	}
	else /* 不允许有重复项 */
	{
		fprintf(stderr, "location error in AddNode()\n");
		exit(1);
	}
}

static bool ToLeft(const Item * i1, const Item *i2)
{
	int comp1;
	if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)
		return true;
	else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) < 0)
		return true;
	else
		return false;
}

static bool ToRight(const Item * i1, const Item *i2)
{
	int comp1;
	if ((comp1 = strcmp(i1->petname, i2->petname)) > 0)
		return true;
	else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) > 0)
		return true;
	else
		return false;
}

static Pair SeekItem(const Item * pi, const Tree * ptree)
{
	Pair look;
	look.parent = NULL;
	look.child = ptree->root;
	if (look.child == NULL)
		return look; //ptree是空树
	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
			/* 如果前两种情况都不满足，则必须是相等的情况 */
			/* look.child 目标项的节点*/
			break;
	}
	return look; /* 成功返回 */
}

/*  ptr 是指向目标节点的父节点指针成员的地址 */
/* *ptr 指向目标节点 */
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);
	}
}

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

static void DeleteAllNodes(Trnode * root)
{
	Trnode * pright;
	if (root != NULL)
	{
		pright = root->right;
		DeleteAllNodes(root->left);
		free(root);
		DeleteAllNodes(pright);
	}
}

main.c

#define _CRT_SECURE_NO_WARNINGS
//可以用#ifndef指令，防止多次包含一个文件
#include <stdio.h>
//提供malloc()、rand()、srand()原型
#include <stdlib.h>
#include <time.h>
//提供strcpy()原型
#include <string.h>
//提供CHAR_BIT的定义，CHAR_BIT表示每字节的位数
#include <limits.h>
//C99定义了bool、true、false
//如果编译器不支持bool,可以用枚举替代enum bool {false, true};
#include <stdbool.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 * str);
char* s_gets(char* st, int n);

int main(int argc, char* argv[])
{
	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");
		}
	}
	DeleteAll(&pets);
	puts("Bye.");

	system("pause");
	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, or 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!");
	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 droppet(Tree * pt)
{
	Item temp;

	if (TreeIsEmpty(pt)) 
	{
		puts("No entries!");
		return;
	}
	
	puts("Please enter name of pet you wish to delete:");
	s_gets(temp.petname, SLEN);
	puts("Please enter pet kind:");
	s_gets(temp.petkind, SLEN);
	uppercase(temp.petname);
	uppercase(temp.petkind);
	printf("%s the %s ", temp.petname, temp.petkind);
	if (DeleteItem(&temp, pt))
		printf("is dropped from the club.\n");
	else
		printf("is not a member.\n");
}

void showpets(const Tree * pt)
{
	if (TreeIsEmpty(pt))
		puts("No entries!");
	else
		Traverse(pt, printitem);
}

void findpet(const Tree * pt)
{
	Item temp;

	if (TreeIsEmpty(pt))
	{
		puts("No entries!");
		return;
	}

	puts("Please enter name of pet you wish to find:");
	s_gets(temp.petname, SLEN);
	puts("Please enter pet 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 printitem(Item item)
{
	printf("Pet: %-19s Kind: %-19s\n", item.petname, item.petkind);
}

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

// 自己实现读取函数
char* s_gets(char* st, int n)
{
	char* ret_val;
	int i = 0;
	ret_val = fgets(st, n, stdin);
	if (ret_val) //即，ret_val != NULL
	{
		while (st[i] != '\n' && st[i] != '\0')
			i++;
		if (st[i] == '\n')
			st[i] = '\0';
		else
			while (getchar() != '\n')
				continue;
	}
	return ret_val;
}

运行测试

标签: C语言