C語言實現二叉樹

Problem   我需要統計的單詞是在程序直接硬編碼的；   這樣做得原因是省略了文件輸入輸出所帶來的困惑；   我的每篇文章，一般只說一個主題；   這樣也方便我日後復習；       Solution   首先，我們需要定義一個結構體，如下代碼所示：    

const int LONGEST_WORD = 32;    // The longest word size

struct binary_tree {
    char str[LONGEST_WORD];
    int count;
    struct binary_tree * left;
    struct binary_tree * right;
};

typedef struct binary_tree node;

 

注意到，我們假設最長的單詞定義為一個常量，在這裡我覺得目前32這個長度應該可以啦；   如果要統計的文章是化學論文，建議你再加大數字，因為化學式通常都很長；   然後是，我們的結構體；這應該很容易理解的；   由於C語言沒有提供我想要的BOOL類型，因此自己動手寫啦下面的代碼；   這個定義非常有用，通常它比define更加值得推薦；   enum BOOL {     NO,     YES };     typedef enum BOOL BOOL; 接下來，我們需要知道單詞之間是如何比較大小的；   因此，需要一個函數叫做cmp；   代碼實現如下：    

BOOL cmp(char * s, char * t)
{
    int i;
    for (i = 0; s[i] == t[i]; i++)
        if ( s[i] == '\0' )
            return NO;
    return (s[i] - t[i]) < 0 ? NO:YES;
}

 

  同時遍歷兩個字符串，然後對返回值進行一個處理；   這樣只會返回兩種情況NO/YES，不然的話會返回三種值(-1，0，正數);   那樣的話，不利於我們往後的工作；   接下來呢，就是如果返回YES我們該（如何） （做什麼）；   如果返回NO我們又該（如何）（做什麼）；   因此，我們需要一個insert函數，把數據的兩種不同分別插入左右子樹；    

void insert(node ** tree, char * val) {
    node * temp = NULL;
    if(!(*tree)) {
        temp = (node*)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->str = val;    //issue code ...
        temp->count = 1;
        *tree = temp;
        return ;
    }

    if(cmp(val, (*tree)->str)) {
        insert(&(*tree)->left,val);
    }else if (cmp(val,(*tree)->str)) {
        insert(&(*tree)->right,val);
    }else{
        (*tree)->count++;
    }
} 
 

 

  這段代碼和前面提到的(C語言實現二叉樹)裡面的代碼幾乎一樣的，哪裡有詳細介紹；   這裡主要講解一下注釋有issue code的那行，如果這行不修改，程序將會蹦潰；   但是，我會故意不馬上修改它，繼續往下寫；   我們需要一個函數，銷毀節點：    

void deltree(node * tree) {
    if(tree) {
        deltree(tree->left);
        deltree(tree->right);
        free(tree);
    }
}   

 

為了查看我們的結果，我們需要一種遍歷方式；   這裡我們就選擇中序吧！    

void print_inorder(node * tree) {
    if(tree) {
        print_inorder(tree->left);
        printf("[%s\t\t\t]count:[%d]\n",tree->str,tree->count);
        print_inorder(tree->right);
    }
} 

 

    我們把頭文件stdio.h/stdlib.h引入後；   把主int main(int argc, char ** arg{    

    node * root;
    node * tmp;
    //int i;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root,"hello");
    insert(&root,"hey");
    insert(&root,"hello");
    insert(&root,"ok");
    insert(&root,"hey");
    insert(&root,"hey");
    insert(&root,"hey")；

    printf("In Order Display\n");
    print_inorder(root);/* Deleting all nodes of tree */

    deltree(root);
}

 

    gcc編譯運行得到如下結果：       果然，我們的issue code有問題，原因是字符串不能像其他的，例如int類型一樣直接用‘=’號賦值；   所以我們需要一個cpy函數：   void mystrcpy(char *s, char *t) {     while ((*s++ = *t++) != '\0')         ; } 所有代碼如下：    

#include <stdio.h>
#include <stdlib.h>


const int LONGEST_WORD = 32;    // The longest word size

struct binary_tree {
    char str[LONGEST_WORD];
    int count;
    struct binary_tree * left;
    struct binary_tree * right;
};

typedef struct binary_tree node;

enum BOOL {
    NO, 
    YES 
};

typedef enum BOOL BOOL;

BOOL cmp(char * s, char * t)
{
    int i;
    for (i = 0; s[i] == t[i]; i++)
        if ( s[i] == '\0' )
            return NO; 
    return (s[i] - t[i]) < 0 ? NO:YES;
}
void mystrcpy(char *s, char *t) 
{
    while ((*s++ = *t++) != '\0')
        ;   
}

void insert(node ** tree, char * val) {
    node * temp = NULL;
    if(!(*tree)) {
        temp = (node*)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        //temp->str = val;  //issue code ...
        mystrcpy(temp->str,val);
        temp->count = 1;
        *tree = temp;
        return ;
    }

    if(cmp(val, (*tree)->str)) {
        insert(&(*tree)->left,val);
    }else if (cmp(val,(*tree)->str)) {
        insert(&(*tree)->right,val);
    }else{
        (*tree)->count++;
    }
}

void deltree(node * tree) {
    if(tree) {
        deltree(tree->left);
        deltree(tree->right);
        free(tree);
    }
}

void print_inorder(node * tree) {
    if(tree) {
        print_inorder(tree->left);
        printf("[%s\t\t\t]count:[%d]\n",tree->str,tree->count);
        print_inorder(tree->right);
    }
}




int main(int argc, char ** argv)
{
    node * root;
    node * tmp;
    //int i;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root,"hello");
    insert(&root,"hey");
    insert(&root,"hello");
    insert(&root,"ok");
    insert(&root,"hey");
    insert(&root,"hey");
    insert(&root,"hey");


    printf("In Order Display\n");
    print_inorder(root);


    /* Deleting all nodes of tree */

    deltree(root);
}
 

 

  最後運行結果如下：       Discussion   那麼這個程序已經完成啦！   還有很多可以優化的，也可以增加更多的功能；   例如，查找特定字符出現的次數；   或者特定字符所出現的行數，等等都可以；   我們會在日後慢慢完善；