C語言實現二叉樹

C語言實現二叉樹

二叉樹的重要性就不用多說啦；   我以前也學習過，但是一直沒有總結；   網上找到的例子，要麼是理論一大堆，然後是偽代碼實現；   要麼是復雜的代碼，沒有什麼解釋；   最終，還是靠FQ找到一些好的文章，參考地址我會在See Also部分給大家貼出來       Problem   假設我們要生成的二叉樹如下圖；           Solution   顯然，我們需要在節點保存的數據只有一個整數；   struct binary_tree {     int data    ;   // Data area     //TODO }; 所以在結構體裡面，我們的代碼應該類似上面的寫法；   通過觀察我們還發現，每一個節點都指向左右兩邊（除了最後的葉子節點外）；   因此，我們需要讓它有兩個指針域；   可能你會想到類似如下的寫法；   struct binary_tree {     int data    ;   // Data area     void * left;     void * right; };  上面的定義格式似乎是正確的，但是類型好像並不是我們想要的；   例如：當left指向左邊的子節點時，子節點應該也是一個包涵數據域的節點；   因此我們需要再定義一個與它本身相同的結構體；   struct binary_tree {     int data    ;   // Data area     struct binary_tree * left;     struct binary_tree * right; }; 所以，我們會這樣去定義它；   顯然，這是一個遞歸定義；   如果我們要實例化一個節點，我們可以:   struct binary_tree * tree; 顯然我們需要定義一個實例寫那麼長的類型名字，實在讓人難受；   因此，我們可以這樣；   typedef struct binary_tree node; node * tree; 好啦！到此為止我們的數據域就定義好啦！你現在的代碼應該是下面的樣子啦；    

struct binary_tree {
    int data    ;   // Data area
    binary_tree * left;
    binary_tree * right;
};  

typedef struct binary_tree node;

 

    接下來我們需要把數據插入到對應的位置上；   我們希望樹左邊分支的的數據總是比樹右邊分支的要小；    

void insert(node ** tree, int val) {
    node * temp = NULL;
    if(!(*tree)) {
        //TODO
        return ;
    }
    
    if (val < (*tree)->data) {
        //TODO
    }else if (val > (*tree)->data) {
        //TODO
    }
}

 

    因此我們代碼會像上面這樣寫；   第一個if語句判斷這個樹節點是否存在；   若是不存在，我們應該生成一個節點，然後添加到樹上來；   第二個if-else呢，則是判斷這個給定要存入的數據是大於當前節點的呢還是小於；   小於呢，存在左分支。大於存在右分支；    

    if(!(*tree)) {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return ;
    }
    
 

 

  分析上面代碼片段，我們發現temp的作用是臨時變量正如其名；   malloc分配內存，然後初始化節點左右指針域為空，以及數據域為val；   最後*tree=temp 把節點安裝到樹上；   並且返回上一級；   對於已經存在的樹節點，我們需要往左右兩分子擴展；   因此我們的代碼會是這樣的；    if (val < (*tree)->data) {         insert(&(*tree)->left,val);   }else if (val > (*tree)->data) {         insert(&(*tree)->right,val);   } 從代碼中可以看出，只對小於和大於兩個方向的數據進行操作；   你也許會考慮到萬一等於呢。   注意，在這裡應該是數據的唯一性有要求的，它類似於數學裡的集合，不會有重復的；   它的這種特性對我們往後要寫得單詞統計程序非常有幫助；   那麼這個函數的所有代碼如下：    

void insert(node ** tree, int val) {
    node * temp = NULL;
    if(!(*tree)) {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return ;
    }
    
    if (val < (*tree)->data) {
        insert(&(*tree)->left,val);
    }else if (val > (*tree)->data) {
        insert(&(*tree)->right,val);
    }
}

 

    節點創建好了，注意我們用malloc創建；   因此，我們是在堆中分配的內存，因此我們需要手動釋放；   那顯然需要用到free函數與之對應；   所以我們釋放節點的函數應該是這樣的；   void deltree(node * tree) {     if(tree) {         free(tree);     } }   這樣似乎也沒有問題啦！但是仔細觀察我們發現；   直接釋放啦free就只是釋放啦根節點；   就好比，我們去拔花生；我們只是簡單的用剪刀把上面的葉子剪斷啦；   沒有想過把花生沿著根一直挖下去是不可能把所有花生弄出來的；   因此，我們需要這樣做；    

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

 

    這樣我們找到左邊的根啦，又繼續往左邊找；   找不到啦，就往右邊找；   再找不到啦，就執行到free釋放節點然後返回上一級；   好啦！樹也有函數建啦，也有辦法“砍”啦！   接下來是怎麼展示我們的樹啦；   樹的遍歷有三種；   前，中，後；   void print_preorder(node * tree) {     if(tree) {         //TODO       } }   首先我們需要判斷tree是否空；   要是空的，我們就沒有必要看裡面還有什麼數據啦；    

void print_preorder(node * tree) {
    if(tree) {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }
}

void print_inorder(node * tree) {
    if(tree) {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

void print_postorder(node * tree) {
    if(tree) {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\n",tree->data);
    }
}

 

x   同樣的我們把中序和後序寫出來；    

void print_preorder(node * tree) {
    if(tree) {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }
}

void print_inorder(node * tree) {
    if(tree) {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

void print_postorder(node * tree) {
    if(tree) {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\n",tree->data);
    }
}

 

    好啦！該有的函數都有啦；   我們該寫測試函數啦；            

int main(void)
{
    node * root;
    node * tmp;
    //int i;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root,9);
    insert(&root,4);
    insert(&root,15);
    insert(&root,6);
    insert(&root,12);
    insert(&root,17);
    insert(&root,2);

    printf("Pre Order Display\n");
    print_preorder(root);

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

    printf("Post Order Display\n");
    print_postorder(root);


    /* Deleting all nodes of tree */
    deltree(root);
}

 

  運行結果如下：    

二叉樹的重要性就不用多說啦；

我以前也學習過，但是一直沒有總結；

網上找到的例子，要麼是理論一大堆，然後是偽代碼實現；

要麼是復雜的代碼，沒有什麼解釋；

最終，還是靠FQ找到一些好的文章，參考地址我會在See Also部分給大家貼出來

 

Problem

假設我們要生成的二叉樹如下圖；



 

Solution

顯然，我們需要在節點保存的數據只有一個整數；

struct binary_tree {
    int data    ;   // Data area
    //TODO
};
所以在結構體裡面，我們的代碼應該類似上面的寫法；

通過觀察我們還發現，每一個節點都指向左右兩邊（除了最後的葉子節點外）；

因此，我們需要讓它有兩個指針域；

可能你會想到類似如下的寫法；

struct binary_tree {
    int data    ;   // Data area
    void * left;
    void * right;
}; 
上面的定義格式似乎是正確的，但是類型好像並不是我們想要的；

例如：當left指向左邊的子節點時，子節點應該也是一個包涵數據域的節點；

因此我們需要再定義一個與它本身相同的結構體；

struct binary_tree {
    int data    ;   // Data area
    struct binary_tree * left;
    struct binary_tree * right;
};
所以，我們會這樣去定義它；

顯然，這是一個遞歸定義；

如果我們要實例化一個節點，我們可以:

struct binary_tree * tree;
顯然我們需要定義一個實例寫那麼長的類型名字，實在讓人難受；

因此，我們可以這樣；

typedef struct binary_tree node;
node * tree;
好啦！到此為止我們的數據域就定義好啦！你現在的代碼應該是下面的樣子啦；

復制代碼
struct binary_tree {
    int data    ;   // Data area
    binary_tree * left;
    binary_tree * right;
};  

typedef struct binary_tree node;
復制代碼
接下來我們需要把數據插入到對應的位置上；

我們希望樹左邊分支的的數據總是比樹右邊分支的要小；

至於為什麼我們暫時不解釋；

復制代碼
void insert(node ** tree, int val) {
    node * temp = NULL;
    if(!(*tree)) {
        //TODO
        return ;
    }
    
    if (val < (*tree)->data) {
        //TODO
    }else if (val > (*tree)->data) {
        //TODO
    }
}
復制代碼
因此我們代碼會像上面這樣寫；

第一個if語句判斷這個樹節點是否存在；

若是不存在，我們應該生成一個節點，然後添加到樹上來；

第二個if-else呢，則是判斷這個給定要存入的數據是大於當前節點的呢還是小於；

小於呢，存在左分支。大於存在右分支；

復制代碼
    if(!(*tree)) {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return ;
    }
    
復制代碼
分析上面代碼片段，我們發現temp的作用是臨時變量正如其名；

malloc分配內存，然後初始化節點左右指針域為空，以及數據域為val；

最後*tree=temp 把節點安裝到樹上；

並且返回上一級；

對於已經存在的樹節點，我們需要往左右兩分子擴展；

因此我們的代碼會是這樣的；

 if (val < (*tree)->data) {
        insert(&(*tree)->left,val);
  }else if (val > (*tree)->data) {
        insert(&(*tree)->right,val);
  }
從代碼中可以看出，只對小於和大於兩個方向的數據進行操作；

你也許會考慮到萬一等於呢。

注意，在這裡應該是數據的唯一性有要求的，它類似於數學裡的集合，不會有重復的；

它的這種特性對我們往後要寫得單詞統計程序非常有幫助；

那麼這個函數的所有代碼如下：

復制代碼
void insert(node ** tree, int val) {
    node * temp = NULL;
    if(!(*tree)) {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return ;
    }
    
    if (val < (*tree)->data) {
        insert(&(*tree)->left,val);
    }else if (val > (*tree)->data) {
        insert(&(*tree)->right,val);
    }
}
復制代碼
節點創建好了，注意我們用malloc創建；

因此，我們是在堆中分配的內存，因此我們需要手動釋放；

那顯然需要用到free函數與之對應；

所以我們釋放節點的函數應該是這樣的；

void deltree(node * tree) {
    if(tree) {
        free(tree);
    }
}  
這樣似乎也沒有問題啦！但是仔細觀察我們發現；

直接釋放啦free就只是釋放啦根節點；

就好比，我們去拔花生；我們只是簡單的用剪刀把上面的葉子剪斷啦；

沒有想過把花生沿著根一直挖下去是不可能把所有花生弄出來的；

因此，我們需要這樣做；

復制代碼
void deltree(node * tree) {
    if(tree) {
        deltree(tree->left);
        deltree(tree->right);
        free(tree);
    }
}
復制代碼
這樣我們找到左邊的根啦，又繼續往左邊找；

找不到啦，就往右邊找；

再找不到啦，就執行到free釋放節點然後返回上一級；

好啦！樹也有函數建啦，也有辦法“砍”啦！

接下來是怎麼展示我們的樹啦；

樹的遍歷有三種；

前，中，後；

void print_preorder(node * tree) {
    if(tree) {
        //TODO

    }
}  
首先我們需要判斷tree是否空；

要是空的，我們就沒有必要看裡面還有什麼數據啦；

復制代碼
void print_preorder(node * tree) {
    if(tree) {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }
}
復制代碼
同樣的我們把中序和後序寫出來；

復制代碼
void print_preorder(node * tree) {
    if(tree) {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }
}

void print_inorder(node * tree) {
    if(tree) {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

void print_postorder(node * tree) {
    if(tree) {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\n",tree->data);
    }
}
復制代碼
好啦！該有的函數都有啦；

我們該寫測試函數啦；

 

 

復制代碼
int main(void)
{
    node * root;
    node * tmp;
    //int i;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root,9);
    insert(&root,4);
    insert(&root,15);
    insert(&root,6);
    insert(&root,12);
    insert(&root,17);
    insert(&root,2);

    printf("Pre Order Display\n");
    print_preorder(root);

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

    printf("Post Order Display\n");
    print_postorder(root);


    /* Deleting all nodes of tree */
    deltree(root);
}
復制代碼
運行結果如下：

復制代碼
Pre Order Display
9
4
2
6
15
12
17
In Order Display
2
4
6
9
12
15
17
Post Order Display
2
6
4
12
17
15
9
復制代碼
 

Discussion

 然後這個例子似乎太簡單了！它沒有對樹進行查詢的函數；

也沒有樹的高度進行測量；

但是，它的簡潔是為了更加容易理解；

可是呢！太簡潔了，以至於我們都不知道為什麼要把數據弄成樹形結構；

為什麼，難道線性結構的數據還不能解決我們身邊的問題嗎？

這個問題，不知道大家有沒有問過自己。反正我以前經常問自己；

那麼，為了讓大家理解存在樹形結構的數據的必要性；

我們，設想要統計C語言的關鍵字在代碼中出現的頻率；

我們會怎麼做呢？？（這個問題我會在另一篇文章講解）

 

x       Discussion    然後這個例子似乎太簡單了！它沒有對樹進行查詢的函數；   也沒有樹的高度進行測量；   但是，它的簡潔是為了更加容易理解；   可是呢！太簡潔了，以至於我們都不知道為什麼要把數據弄成樹形結構；   為什麼，難道線性結構的數據還不能解決我們身邊的問題嗎？   這個問題，不知道大家有沒有問過自己。反正我以前經常問自己；   那麼，為了讓大家理解存在樹形結構的數據的必要性；   我們，設想要統計C語言的關鍵字在代碼中出現的頻率；   我們會怎麼做呢？？（這個問題我會在另一篇文章講解）