C語言實現二叉樹創建和查找

#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;
}