ARCH_TREE q, s;
? ? if((*p)->right == NULL) {
? ? ? ? q = *p;
? ? ? ? *p = (*p)->left;
? ? ? ? free(q);
? ? } else if((*p)->left == NULL) {
? ? ? ? q = *p;
? ? ? ? *p = (*p)->right;
? ? ? ? free(q);
? ? } else {
? ? ? ? q = *p;
? ? ? ? s = (*p)->left;
? ? ? ? while(s->right != NULL) {
? ? ? ? ? ? q = s;
? ? ? ? ? ? s = s->right;
? ? ? ? }
? ? ? ? (*p)->element = s->element;
? ? ? ? if(q != p) {
? ? ? ? ? ? q->right = s->left;
? ? ? ? } else {
? ? ? ? ? ? q ->left = s->left;
? ? ? ? }
? ? }
? ? free(s);
}
void deleteBST(SEARCH_TREE *T, element_type key)
{
? ? if(!(*T)) {
? ? ? ? return;
? ? } else if ((*T)->element == key) {
? ? ? ? free(*T);
? ? } else if((*T)->element > key) {
? ? ? ? deleteBST((*)T->left, key);
? ? } else {
? ? ? ? deleteBST((*)T->right, key);
? ? }
}
poj2418 Hardwood Species
?
#include
#include
#include
?
struct node {
? ? char name[31];
? ? struct node *lchild, *rchild;
? ? int count;
}tree;
struct node *root;
int n = 0;
void mid_cal(struct node *root)
{
? ? if(root != NULL) {
? ? ? ? mid_cal(root->lchild);
? ? ? ? printf("%s %.4lf\n", root->name, ((double)(root->count) / (double)n) * 100.0);
? ? ? ? mid_cal(root->rchild);
? ? }
}
?
void insertBST(struct node** root, char *s)
{
? ? if(*root == NULL) {
? ? ? ? struct node *p = (struct node*)malloc(sizeof(tree));
? ? ? ? strcpy(p->name, s);
? ? ? ? p->lchild = p->rchild = NULL;
? ? ? ? p->count = 1;
? ? ? ? *root = p;
? ? } else {
? ? ? ? if(strcmp(s, (*root)->name) == 0) {
? ? ? ? ? ? ((*root)->count)++;
? ? ? ? ? ? return;
? ? ? ? } else if(strcmp(s, (*root)->name) < 0) {
? ? ? ? ? ? insertBST(&((*root)->lchild), s);
? ? ? ? } else {
? ? ? ? ? ? insertBST(&((*root)->rchild), s);
? ? ? ? }
? ? }
}
?
int main()
{
? ? char s[31];
? ? while(gets(s)) {
? ? ? ? insertBST(&root, s);
? ? ? ? n++;
? ? }
? ? mid_cal(root);
? ? return 0;