二叉樹(shù)統(tǒng)計(jì)單詞方法

第頁(yè)二叉樹(shù)統(tǒng)計(jì)單詞方法因?yàn)轭A(yù)先不知道出現(xiàn)的單詞列表，無(wú)法方便地排序并使用折半查找;也不能分別對(duì)輸入中的每個(gè)單詞都執(zhí)行一次線性查找，所以合計(jì)使用二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)來(lái)組織這些單詞，接下來(lái)中山美聯(lián)我告訴你具體的二叉樹(shù)統(tǒng)計(jì)單詞方法，大家一起來(lái)看看吧!

二叉樹(shù)統(tǒng)計(jì)單詞方法1：

/*

*MypracticeofKR6.5

*

*/

#include

#include

#include

#include

#defineMAXWORD100

/*abinarytreenode*/

typedefstructtnode_{

char*word;

intcount;

structtnode_*left;

structtnode_*right;

}tnode;

voidprint_tree(tnode*root);

tnode*add_tree(tnode*root,char*word);

voidfree_node(tnode*root);

char*copy_string(char*s){

char*p=(char*)malloc(strlen(s)+1);

if(p!=NULL){

strcpy(p,s);

}

returnp;

}

tnode*add_tree(tnode*p,char*word){

intresult;

if(p==NULL){

p=(tnode*)malloc(sizeof(tnode));

p-word=copy_string(word);//Attention!

p-count=1;

p-left=NULL;

p-right=NULL;

}

else{

result=strcmp(word,p-word);

if(result0){

p-left=add_tree(p-left,word);

}

elseif(result0){

p-right=add_tree(p-right,word);

}

else{

p-count++;

}

}

returnp;

}

voidprint_tree(tnode*p){

if(p){

print_tree(p-left);

printf(%st:%4dn,p-word,p-count);

print_tree(p-right);

}

}

voidfree_node(tnode*p){

if(p){

free_node(p-left);

free_node(p-right);

free(p-word);

free(p);

}

}

intgetword(char*word,intn){

intc;

char*w=word;

while(isspace(c=getchar())){

;

}

if(c!=EOF){

*w++=c;

}

if(!isalpha(c)){

*w=;

returnc;

}

while(n0){

c=getchar();

if(isalnum(c)){

*w++=c;

}

else{

break;

}

n--;

}

*w=;

returnw[0];

}

intmain(){

tnode*root=NULL;//指針一定要初始化為NULL

charword[MAXWORD];

while((getword(word,MAXWORD))!=EOF){

if(isalnum(word[0])){

root=add_tree(root,word);

}

}

print_tree(root);

free_node(root);

return0;

}

二叉樹(shù)統(tǒng)計(jì)單詞方法2：

如果使用二叉數(shù)來(lái)完成這個(gè)問(wèn)題，我們將會(huì)得到更好的時(shí)間復(fù)雜度O(lgn)，n為節(jié)點(diǎn)個(gè)數(shù)。也可以說(shuō)，所花費(fèi)的時(shí)間將會(huì)和樹(shù)的高度成正比。二叉數(shù)的所有操作的時(shí)間復(fù)雜度都是這么多，包括插入、刪除、建立、查找(來(lái)自：算法導(dǎo)論第三版第12章)。所以，關(guān)于一個(gè)單詞而言，如果已經(jīng)存放在了樹(shù)中，那么就是查找，將新單詞放入的就是插入。然而，實(shí)際上這兩個(gè)動(dòng)作應(yīng)該是結(jié)合起來(lái)的，因?yàn)樵谄湓撛诘奈恢谜也坏降臅r(shí)候，我們已經(jīng)得到新單詞該在的位置，所以直接插入即可。具體請(qǐng)看下面代碼的實(shí)現(xiàn)。

二叉數(shù)的數(shù)據(jù)結(jié)構(gòu)中基本的有三個(gè)：

自身數(shù)據(jù)

左孩子

右孩子

我們?cè)擃}中，自身數(shù)據(jù)就是單詞，而且還必須要多一個(gè)統(tǒng)計(jì)單詞次數(shù)的數(shù)值。

code如下：

[cpp]viewplaincopy

structtnode{

char*word;

intcount;

structtnode*left;

structtnode*right;

};

面對(duì)過(guò)程的流程以及代碼

作為一般講c語(yǔ)言的書(shū)，很顯然是會(huì)用面向過(guò)程的思維方式來(lái)完成的，由下面的main函數(shù)可以具體的流程：

[cpp]viewplaincopy

intmain()

{

structtnode*root;

charword[MAXWORD];

root=NULL;

while(getword(word,MAXWORD)!=EOF)//讀入一個(gè)單詞

if(isalpha(word[0]))

root=addtree(root,word);//將單詞加入到樹(shù)中

treeprint(root);//打印樹(shù)

return0;

}

main函數(shù)中的addtree(root,word)包涵了更多的流程，我們來(lái)看看addtree函數(shù)：

[cpp]viewplaincopy

structtnode*addtree(structtnode*p,char*w)

{

//推斷是否是新節(jié)點(diǎn)

if(p==NULL){

/*anewwordhasarrived*/

p=talloc();

/*makeanewnode*/

p-word=strdup1(w);//復(fù)制w的過(guò)程，如單純的賦值，就會(huì)使p-word和w指向了一處。

p-count=1;

p-left=p-right=NULL;

returnp;

}

//不是新節(jié)點(diǎn)

intcond;

cond=strcmp(w,p-word);

if(cond==0){

p-count++;/*repeatedword*/

}elseif(cond0){//就到左子樹(shù)去找

p-left=addtree(p-left,w);

}else{//就到右子樹(shù)去找

p-right=addtree(p-right,w);

}

returnp;

}

通過(guò)上述代碼，我相信不僅對(duì)本題的流程有了基本的熟悉，并且也對(duì)二叉樹(shù)的查找和插入有了一定的了解。實(shí)際上，而二叉數(shù)建立的過(guò)程就是查找和插入的過(guò)程。

其中的兩個(gè)函數(shù)的代碼：

[cpp]viewplaincopy

/*talloc:makeatnode*/

/**

*為新節(jié)點(diǎn)分配內(nèi)存

*/

structtnode*talloc(void)

{

return(structtnode*)malloc(sizeof(structtnode));

}

/**

*完成對(duì)單詞的復(fù)制，避免不同指針指向同一個(gè)單詞，對(duì)單詞產(chǎn)生干擾

*/

char*strdup1(char*s)

{

char*p;

/*makeaduplicateofs*/

p=(char*)malloc(strlen(s)+1);/*+1for*/

if(p!=NULL)

strcpy(p,s);

returnp;

}

讀入單詞

[cpp]viewplaincopy

/*getword:getnextwordorcharacterfrominput*/

/**

*沒(méi)有調(diào)用高級(jí)的庫(kù)函數(shù)使得這段代碼略顯復(fù)雜

*但是這些基本的方式能夠讓我更深入的體會(huì)了一些編程的高級(jí)技巧

*/

intgetword(char*word,intlim)

{

intc,getch(void);

voidungetch(int);

char*w=word;

while(isspace(c=getch()))

;

if(c!=EOF)

*w++=c;

if(!isalpha(c)){

*w=;

returnc;

}

for(;--lim0;w++){

if(!isalnum(*w=getch())){

ungetch(*w);//讀的后一個(gè)要放回去，因?yàn)楹笠粋€(gè)不是我們要要的，但是我們又已經(jīng)讀了

break;

}

}

*w=;

returnword[0];

}

#defineBUFSIZE100

charbuf[BUFSIZE];

intbufp=0;

/*bufferforungetch*/

/*nextfreepositioninbuf*/

intgetch(void)/*geta(possiblypushed-back)character*/

{

return(bufp0)?buf[--bufp]:getchar();

}

voidungetch(intc)

/*pushcharacterbackoninput*/

{

if(bufp=BUFSIZE)

printf(ungetch:toomanycharactersn);

else

buf[bufp++]=c;

}

打印結(jié)果

都快忘了

先序遍歷：先根，再左，后右

中序遍歷：先左，再根，后右

后序遍歷：先左，再右，后中

[cpp]viewplaincopy

/*treeprint:in-orderprintoftreep*/

/**

*遞歸打印，采納了中序遍歷。

*/

voidtreeprint(structtnode*p)

{

if(p!=NULL){

treeprint(p-left);

printf(%4d%sn,p-count,p-word);

treeprint(p-right);

}

}

打印實(shí)例

就拿我們編寫(xiě)的代碼作一個(gè)測(cè)試，結(jié)果如下，不能給中文做這樣測(cè)試，因?yàn)橹形睦锩娴淖侄紱](méi)有空格

[cpp]viewplaincopy

zy@zy:~/Documents/eclipseWorkSpace/test/src$./a.out

1EOF

3MAXWORD

1NULL

2addtree

4char

1count

1ctype

1define

2getword

4h

1if

4include

4int

1isalpha

1left

1main

1return

1right

5root

1stdio

1stdlib

1string

7struct

7tnode

2treeprint

1void

1while

5word

zy@zy:~/Documents/eclipseWorkSpace/test/src$

源代碼

[cpp]viewplaincopy

#include

#include

#include

#include

#defineMAXWORD100

structtnode*addtree(structtnode*,char*);

voidtreeprint(structtnode*);

intgetword(char*,int);

structtnode{

char*word;

intcount;

structtnode*left;

structtnode*right;

};

intmain()

{

structtnode*root;

charword[MAXWORD];

root=NULL;

while(getword(word,MAXWORD)!=EOF)//讀入一個(gè)單詞

if(isalpha(word[0]))

root=addtree(root,word);//將單詞加入到樹(shù)中

treeprint(root);//打印樹(shù)

return0;

}

structtnode*talloc(void);

char*strdup1(char*s);

structtnode*addtree(structtnode*p,char*w)

{

//推斷是否是新節(jié)點(diǎn)

if(p==NULL){

/*anewwordhasarrived*/

p=talloc();

/*makeanewnode*/

p-word=strdup1(w);//復(fù)制w的過(guò)程，如單純的賦值，就會(huì)使p-word和w指向了一處。

p-count=1;

p-left=p-right=NULL;

returnp;

}

//不是新節(jié)點(diǎn)

intcond;

cond=strcmp(w,p-word);

if(cond==0){

p-count++;/*repeatedword*/

}elseif(cond0){//就到左子樹(shù)去找

p-left=addtree(p-left,w);

}else{//就到右子樹(shù)去找

p-right=addtree(p-right,w);

}

returnp;

}

/*treeprint:in-orderprintoftreep*/

/**

*遞歸打印，采納了中序遍歷。

*/

voidtreeprint(structtnode*p)

{

if(p!=NULL){

treeprint(p-left);

printf(%4d%sn,p-count,p-word);

treeprint(p-right);

}

}

/*talloc:makeatnode*/

/**

*為新節(jié)點(diǎn)分配內(nèi)存

*/

structtnode*talloc(void)

{

return(structtnode*)malloc(sizeof(structtnode));

}

/**

*完成對(duì)單詞的復(fù)制，避免不同指針指向同一個(gè)單詞，對(duì)單詞產(chǎn)生干擾

*/

char*strdup1(char*s)

{

char*p;

/*makeaduplicateofs*/

p=(char*)malloc(strlen(s)+1);/*+1for*/

if(p!=NULL)

strcpy(p,s);

returnp;

}

/*getword:getnextwordorcharacterfrominput*/

/**

*沒(méi)有調(diào)用高級(jí)的庫(kù)函數(shù)使得這段代碼略顯復(fù)雜

*但是這些基本的方式能夠讓我更深入的體會(huì)了一些編程的高級(jí)技巧

*/

intgetword(char*word,intlim)