5.1 二分查找树算法
《算法导论》中，二分查找树的伪代码如下：
ITERATIVE-TREE-SEARCH(x,k)
1 while x ≠ NIL and k ≠ key[x]
2 do if k < key[x]
3 thenx ← left[x]
4 elsex ← right[x]
5 return x
TREE-INSERT(T,z)
1 y ← NIL
2 x ← root[T]
3 while x ≠ NIL
4 do y ← x
5 ifkey[z] < key[x]
6 thenx ← left[x]
7 elsex ← right[x]
8 p[z] ← y
9 if y = NIL
10 thenroot[T] ← z
11 else if key[z] < key[y]
12 thenleft[y] ← z
13 elseright[y] ← z
5.1.1 实例
PKU JudgeOnline, 2418, Hardwood Species.
5.1.2 问题描述
输入一串树木的名字，统计树木在所有树木中所占的百分比。
5.1.3 输入
RedAlder
Ash
Aspen
Basswood
Ash
Beech
YellowBirch
Ash
Cherry
Cottonwood
Ash
Cypress
RedElm
Gum
Hackberry
WhiteOak
Hickory
Pecan
HardMaple
WhiteOak
SoftMaple
RedOak
RedOak
WhiteOak
Poplan
Sassafras
Sycamore
BlackWalnut
Willow
5.1.4 输出
Ash13.7931
Aspen3.4483
Basswood3.4483
Beech3.4483
BlackWalnut 3.4483
Cherry3.4483
Cottonwood3.4483
Cypress3.4483
Gum3.4483
Hackberry3.4483
HardMaple 3.4483
Hickory3.4483
Pecan3.4483
Poplan3.4483
RedAlder 3.4483
RedElm 3.4483
RedOak 6.8966
Sassafras3.4483
SoftMaple 3.4483
Sycamore3.4483
WhiteOak 10.3448
Willow3.4483
YellowBirch 3.4483
5.1.5 程序
#define MAX_WORD_LENGTH 31 #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <string.h> #include <iostream.h> //定义BST结点 typedef struct BSTNode { charkey[MAX_WORD_LENGTH]; int value; BSTNode *lchild; BSTNode *rchild; }BSTNode,*BSTree; BSTreet=NULL; int sum = 0; //向BST插入结点 void insert_tree(char * key) { //x指示查找过程中下降的路径，y始终指向x的父结点 BSTree y=NULL; BSTree x=t; //x下降 while(x) { y = x; if(strcmp(x->key,key) == 0){ x->value++; return; }else if(strcmp(x->key, key) >0){ x = x->lchild; }else{ x = x->rchild; } } BSTreenew_node = (BSTree)malloc(sizeof(BSTNode)); new_node->lchild = NULL; new_node->rchild = NULL; strcpy(new_node->key, key); new_node->value = 1; //如果树为空 if(t==NULL) t=new_node; else { //设置父结点的孩子结点 if(strcmp(y->key,key) >= 0) y->lchild = new_node; else y->rchild=new_node; } } void inorder_tree_walk(BSTree x) { if(x !=NULL) { inorder_tree_walk(x->lchild); printf("%s", x->key); // printf("%d\n", x->value); printf("%.4f\n",(x->value * 100.0) / sum); inorder_tree_walk(x->rchild); } } int main() { chartemp[31]; while(gets(temp))/*&& temp[0] != '#')*/ { insert_tree(temp); // cout << temp << endl; sum++; } inorder_tree_walk(t); return 1; } 5.2 实例PKU JudgeOnline, 2503, Babelfish.
PKU JudgeOnline, 2418, Hardwood Species.
PKU JudgeOnline, 1002, Exponentiation.
本文章欢迎转载，请保留原始博客链接http://blog.csdn.net/fsdev/article