程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 一步一步寫算法(之排序二叉樹的保存和加載)

一步一步寫算法(之排序二叉樹的保存和加載)

編輯:關於C

 

【 聲明:版權所有,歡迎轉載,請勿用於商業用途。  聯系信箱:feixiaoxing @163.com】

 

 

    排序二叉樹是我們開發中經常使用到的一種數據結構,它具有較好的插入、刪除、查找特性。但是由於二叉樹的指針較多,所以相比較其他的數據結構而言,二叉樹來得比較麻煩些。但是也不是沒有辦法,下面介紹一下我個人常用的方法。

    我們知道,如果一個二叉樹是一個滿樹的話,那麼二叉樹的節點應該是按照1、2、3、4依次排開的。但是現實情況是這樣的,由於排序二叉樹自身的特性,某個分支節點常常可能左半邊有分支,右半邊沒有分支;或者是右半邊有分支,左半邊沒有分支。那麼在數據中節點的順序很可能是不連貫的了。

    但是,對於某一個節點來說,它的左分支節點、右分支節點和父節點之間還是存在著某種聯系的。比如說,如果父節點的順序是n,那麼它的左節點只能是n*2,右邊節點只能是2*n+1。那麼,我們能不能利用父節點和子節點之間的關系來進行數據的保存呢?答案當然是肯定的。

 

    首先,我們需要對數據結構重新定義一下,其中number記錄序列號:

 

 

typedef struct _TREE_NODE 

    int data; 

    int number; 

    struct _TREE_NODE* left_child; 

    struct _TREE_NODE* right_child;  

}TREE_NODE; 

typedef struct _TREE_NODE

{

       int data;

       int number;

       struct _TREE_NODE* left_child;

       struct _TREE_NODE* right_child;

}TREE_NODE;    那麼原來添加數據的函數也要做出修改?

STATUS _insert_node_into_tree(TREE_NODE* pTreeNode, int data) 

    TREE_NODE* pNode; 

 

    while(1){ 

        if(data < pTreeNode->data){ 

            if(NULL == pTreeNode->left_child){ 

                pNode = create_tree_node(data); 

                assert(NULL != pNode); 

                pNode->number = pTreeNode->number << 1; 

                pTreeNode->left_child = pNode; 

                break; 

            }else 

                pTreeNode = pTreeNode->left_child; 

        }else{ 

            if(NULL == pTreeNode->right_child){ 

                pNode = create_tree_node(data); 

                assert(NULL != pNode); 

                pNode->number = pTreeNode->number << 1 + 1; 

                pTreeNode->right_child = pNode; 

                break; 

            }else 

                pTreeNode = pTreeNode->right_child; 

        } 

    } 

 

    return TRUE; 

 

STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data) 

    if(NULL == ppTreeNode) 

        return FALSE; 

     

    if(NULL == *ppTreeNode){ 

        *ppTreeNode = (TREE_NODE*)create_tree_node(data); 

        assert(NULL != *ppTreeNode); 

        (*ppTreeNode)->number = 1; 

        return TRUE; 

    } 

     

    return _insert_node_into_tree(*ppTreeNode, data); 

STATUS _insert_node_into_tree(TREE_NODE* pTreeNode, int data)

{

       TREE_NODE* pNode;

 

       while(1){

              if(data < pTreeNode->data){

                     if(NULL == pTreeNode->left_child){

                            pNode = create_tree_node(data);

                            assert(NULL != pNode);

                            pNode->number = pTreeNode->number << 1;

                            pTreeNode->left_child = pNode;

                            break;

                     }else

                            pTreeNode = pTreeNode->left_child;

              }else{

                     if(NULL == pTreeNode->right_child){

                            pNode = create_tree_node(data);

                            assert(NULL != pNode);

                            pNode->number = pTreeNode->number << 1 + 1;

                            pTreeNode->right_child = pNode;

                            break;

                     }else

                            pTreeNode = pTreeNode->right_child;

              }

       }

 

       return TRUE;

}

 

STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)

{

       if(NULL == ppTreeNode)

              return FALSE;

      

       if(NULL == *ppTreeNode){

              *ppTreeNode = (TREE_NODE*)create_tree_node(data);

              assert(NULL != *ppTreeNode);

              (*ppTreeNode)->number = 1;

              return TRUE;

       }

      

       return _insert_node_into_tree(*ppTreeNode, data);

}    那麼,此時保存的時候放在硬盤裡面的數據應該有哪些呢?我們在遍歷每一個節點的時候,只需要把對應的數據和序列號依次放到硬盤即可。

 

 

typedef struct _DATA 

    int data; 

    int number; 

}DATA; 

typedef struct _DATA

{

       int data;

       int number;

}DATA;  

 

    保存的數據總要再次啟用吧?怎麼加載呢?很簡單,四個步驟:

        1)根據記錄的節點總數分配n*sizeof(TREE_NODE)空間;

        2)依次從硬盤中取出DATA數據,把它們復制給TREE_NODE,暫時left_side和right_side指針為空;

        3)對於對於每一個節點n,尋找它的父節點n>>1,填充left_side或者是right_side,並且根據(n%2)是否為1判斷當前節點是左節點還是右節點;

        4)獲取n=1的節點,那麼這個節點就是我們需要尋找的根節點,至此數據就加載完畢。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved