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

一步一步寫算法(之二叉樹廣度遍歷)

編輯:關於C語言

 

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

 

 

 

 

    在二叉樹的遍歷當中,有一種遍歷方法是不常見的,那就是廣度遍歷。和其他三種遍歷方法不同,二叉樹的廣度遍歷需要額外的數據結構來幫助一下?什麼數據結構呢?那就是隊列。因為隊列具有先進先出的特點,這個特點要求我們在遍歷新的一層數據之前,必須對上一次的數據全部遍歷結束。暫時還沒有掌握隊列知識的朋友可以看一看我的這一篇博客—隊列。

 

    a)下面是新添加的隊列數據結構,其中數據部分換成了樹節點指針的指針:

 

typedef struct _QUEUE 

    int head; 

    int tail; 

    int length; 

    TREE_NODE** pHead; 

}QUEUE; 

typedef struct _QUEUE

{

       int head;

       int tail;

       int length;

       TREE_NODE** pHead;

}QUEUE;    注:head表示開始,tail表示結束,length表示pHead的長度,pHead表示指針的起始地址

 

 

 

 

    b)創建隊列,因為涉及到length的長度問題,所以需要計算二叉樹中節點的總數

 

QUEUE* create_queue_for_tree(const TREE_NODE* pTreeNode) 

    QUEUE* pQueue; 

    int count; 

 

    if(NULL == pTreeNode) 

        return NULL; 

 

    count = count_all_node_number(pTreeNode); 

    pQueue = (QUEUE*)malloc(sizeof(QUEUE)); 

    assert(NULL != pQueue); 

    memset(pQueue, 0, sizeof(QUEUE)); 

 

    pQueue->pHead = (TREE_NODE**)malloc(sizeof(TREE_NODE*)* count); 

    assert(NULL != pQueue->pHead); 

    memset(pQueue->pHead, 0, sizeof(TREE_NODE*) * count); 

 

    pQueue->head = pQueue->tail = 0; 

    pQueue->length = count; 

    return pQueue; 

QUEUE* create_queue_for_tree(const TREE_NODE* pTreeNode)

{

       QUEUE* pQueue;

       int count;

 

       if(NULL == pTreeNode)

              return NULL;

 

       count = count_all_node_number(pTreeNode);

       pQueue = (QUEUE*)malloc(sizeof(QUEUE));

       assert(NULL != pQueue);

       memset(pQueue, 0, sizeof(QUEUE));

 

       pQueue->pHead = (TREE_NODE**)malloc(sizeof(TREE_NODE*)* count);

       assert(NULL != pQueue->pHead);

       memset(pQueue->pHead, 0, sizeof(TREE_NODE*) * count);

 

       pQueue->head = pQueue->tail = 0;

       pQueue->length = count;

       return pQueue;

}

 

 

 

 

    c)實現隊列的數據加入和數據彈出操作

void insert_node_into_queue(QUEUE* pQueue, TREE_NODE* pNode) 

    if(NULL == pQueue || NULL == pQueue->pHead ||NULL == pNode) 

        return; 

 

    pQueue->pHead[pQueue->tail ++] = pNode; 

    return; 

 

TREE_NODE* get_node_from_queue(QUEUE* pQueue) 

    if(NULL == pQueue || NULL == pQueue->pHead) 

        return NULL; 

 

    if(pQueue->head == pQueue->tail) 

        return NULL; 

 

    return pQueue->pHead[pQueue->head++]; 

void insert_node_into_queue(QUEUE* pQueue, TREE_NODE* pNode)

{

       if(NULL == pQueue || NULL == pQueue->pHead ||NULL == pNode)

              return;

 

       pQueue->pHead[pQueue->tail ++] = pNode;

       return;

}

 

TREE_NODE* get_node_from_queue(QUEUE* pQueue)

{

       if(NULL == pQueue || NULL == pQueue->pHead)

              return NULL;

 

       if(pQueue->head == pQueue->tail)

              return NULL;

 

       return pQueue->pHead[pQueue->head++];

}    注:這裡定義的隊列不是循環隊列,所以數據的壓入和彈出比較簡單,直接對head和tail處理即可

 

 

 

 

    d)遍歷節點,按層得到數據,最後再pQueue->pHead中得到的指針數據就是按層輸出的結果

 

QUEUE* traverse_node_by_layer(TREE_NODE* pNode) 

    QUEUE* pQueue; 

    if(NULL ==pNode) 

        return NULL; 

 

    pQueue = create_queue_for_tree(pNode); 

    assert(NULL != pQueue); 

 

    /* 首個節點加入隊列*/ 

    insert_node_into_queue(pQueue, pNode); 

    pNode = get_node_from_queue(pQueue); 

 

    while(pNode){ 

        if(pNode->left) 

            insert_node_into_queue(pQueue, pNode->left); 

 

        if(pNode->right) 

            insert_node_into_queue(pQueue, pNode->right); 

 

        pNode = get_node_from_queue(pQueue); 

    } 

 

    return pQueue; 

QUEUE* traverse_node_by_layer(TREE_NODE* pNode)

{

       QUEUE* pQueue;

       if(NULL ==pNode)

              return NULL;

 

       pQueue = create_queue_for_tree(pNode);

       assert(NULL != pQueue);

 

       /* 首個節點加入隊列*/

       insert_node_into_queue(pQueue, pNode);

       pNode = get_node_from_queue(pQueue);

 

       while(pNode){

              if(pNode->left)

                     insert_node_into_queue(pQueue, pNode->left);

 

              if(pNode->right)

                     insert_node_into_queue(pQueue, pNode->right);

 

              pNode = get_node_from_queue(pQueue);

       }

 

       return pQueue;

}

擴充部分:

 

    上面的辦法已經可以實現隊列的按層輸出,那麼如果想在節點結構中直接實現數據的按層訪問怎麼辦?其實兩步走就可以:1)在已有的TREE_NODE添加prev和next;(2)按照剛才得到的pQueue->pHead結果,依次對prev和next進行賦值即可。不知道朋友們明白了沒?

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