#include#include #include #include #define MAXWORD 100 struct tree_node *addtree(struct tree_node * , char *); void treeprint(struct tree_node *); int getword(char * ,int ); //定義二叉樹結構 struct tree_node{ char *word ; //指向單詞的指針 int *count ; //統計單詞出現的次數 struct tree_node * left ; //指向左子樹的指針 自引用結構體 struct tree_node * right; //指向右子樹指針 }; int main(){ struct tree_node * root; char word[MAXWORD]; root = NULL; while (getword(word,MAXWORD) != EOF) if(isalpha(word[0])) root = addtree(root,word); treeprint(root); return 0; } //為新節點分配空間 struct tree_node *tree_alloc(void); //復制新單詞 char *strdup(char *); struct tree_node * addtree(struct tree_node * p ,char *w) { int cond; if (p == NULL){ //a new word has arrved ; p = tree_alloc(); //make a new node ; p->word = strdup(w); p->count = 1; p->next = p->right = NULL; }else if ((cond = strcmp(w, p->word)) == 0) p->count++; //在二叉樹中存在的單詞 else if(cond < 0 ) //新的單詞比樹中的節點小 放入左邊 p->left = addtree(p->left, w); else p->right = addtree(p->right ,w); return p; } //treeprint 函數按順序打印樹 ==>先打印左子樹,然後打印本身,最後後打印右子樹 void treeprint(struct tree_node * p) { if ( p != NULL){ treeprint(p->left); printf("%8d %s\n",p->count ,p->word); treeprint(p->right); } } // 分配新節點所需的空間 // struct tree_node * tree_alloc(void) { return (struct tree_node*) malloc(sizeof(struct tree_node)); } //strdup 函數通過調用malloc函數把傳入的字符串復制到一個安全的位置 char * strdup(char *s) { char * p; p = (char * ) malloc(strlen(s)+1); //多分配一個字節的空間用來存放'\0',strlen函數返回的長度不包含'\0'在內. if(p != NULL) //可能分配空間會失敗,所以先判斷一下 strcpy(p ,s); return p; }
