一 、目的：

成都創(chuàng)新互聯(lián)是網(wǎng)站建設(shè)技術(shù)企業(yè)，為成都企業(yè)提供專業(yè)的網(wǎng)站設(shè)計制作、成都網(wǎng)站設(shè)計，網(wǎng)站設(shè)計，網(wǎng)站制作，網(wǎng)站改版等技術(shù)服務(wù)。擁有10多年豐富建站經(jīng)驗(yàn)和眾多成功案例，為您定制適合企業(yè)的網(wǎng)站。10多年品質(zhì)，值得信賴！

1. 掌握指針變量、動態(tài)變量的含義；
2. 掌握二叉樹的結(jié)構(gòu)特征，以及各種存儲結(jié)構(gòu)的特點(diǎn)及適用范圍；
3. 掌握指針類型描述、訪問和處理二叉樹的運(yùn)算；

二 、環(huán)境：

operating system version：Win11

CPU instruction set:? x64

Integrated Development Environment：Viusal Studio 2022

三 、內(nèi)容：

已知以二叉樹表作為存儲結(jié)構(gòu)，寫出按層次順序遍歷二叉樹的算法。

算法思想：本算法采用一個隊(duì)列q，先將二叉樹根結(jié)點(diǎn)入隊(duì)列，然后退隊(duì)列，輸出該結(jié)點(diǎn)，若它有左子樹，便將左子樹根結(jié)點(diǎn)入隊(duì)列；若有右子樹，便將右子樹根結(jié)點(diǎn)入隊(duì)列，直到隊(duì)列空為止。因?yàn)殛?duì)列的特點(diǎn)是先進(jìn)先出，從而達(dá)到按層次順序遍歷二叉樹的目的。

四 、要求：

1. 實(shí)現(xiàn)二叉樹表的層次遍歷算法，并給出應(yīng)用。

五 、步驟：

1. 程序：

#include "stdio.h"  
#include "stdlib.h"  
#define INITQUEUE 20  
  
typedef struct BiTNode  
{  
    char data;    //定義結(jié)點(diǎn)數(shù)據(jù)  
    struct BiTNode* lchild;//定義結(jié)點(diǎn)左孩子指針  
    struct BiTNode* rchild;//定義結(jié)點(diǎn)右孩子指針  
}BiTNode, * BiTree;//定義二叉樹結(jié)點(diǎn)  
  
typedef struct Queue  
{  
    BiTNode* front;//定義隊(duì)列頭指針  
    BiTNode* tail;//定義隊(duì)列尾指針  
    int size;//定義隊(duì)列空間大小  
}Queue;  
  
int InitQueue(Queue& Q)  
{//InitQueue初始化隊(duì)列  
    Q.front = (BiTNode*)malloc(INITQUEUE * sizeof(BiTNode));  
    if (!Q.front)  
    {  
        return 0;  
    }  
    Q.tail = Q.front;  
    Q.size = INITQUEUE;  
    return 1;  
}  
  
bool IsEmpty(Queue Q)  
{//IsEmpty判斷隊(duì)列是否為空  
    if (Q.tail == Q.front)  
    {  
        return true;  
    }  
    else  
    {  
        return false;  
    }  
}  
  
int EnQueue(Queue& Q, BiTNode e)  
{//EnQueue將元素入隊(duì)列  
    if ((Q.tail - Q.front + INITQUEUE) % INITQUEUE == INITQUEUE - 1)  
    {  
        return 0;  
    }  
    *Q.tail = e;  
    Q.tail++;  
    return 1;  
}  
  
int DeQueue(Queue& Q, BiTNode& e)  
{//DeQueue將元素出隊(duì)列  
    if (Q.front == Q.tail)  
    {  
        return 0;  
    }  
    e = *Q.front;  
    Q.front++;  
    return 1;  
}  
  
void CreateBiTree(BiTree& T)  
{//構(gòu)造二叉樹  
    char ch;  
    scanf_s("%c", &ch);  
    if ('#' == ch)  
    {  
        T = NULL;  
    }  
    else  
    {  
        T = (BiTree)malloc(sizeof(BiTNode));  
        T->data = ch;  
        CreateBiTree(T->lchild);  
        CreateBiTree(T->rchild);  
    }  
}  
  
int levelTraverse(BiTree T)  
{//二叉樹層次遍歷  
    if (NULL == T)  
    {  
        return 0;  
    }  
    BiTNode e;  
    Queue Q;  
    int levelcount = 0; //樹的深度  
    int curlevel = 1;   //本層里剩余的未訪問的結(jié)點(diǎn)數(shù)  
    int nextlevel = 0;  //下一層還未訪問的結(jié)點(diǎn)數(shù)  
    InitQueue(Q);  
    EnQueue(Q, *T);  
    while (!IsEmpty(Q))//當(dāng)隊(duì)列不為空時循環(huán)  
    {  
        DeQueue(Q, e);//出隊(duì)列  
        printf("%c ", e.data);//打印該元素  
        curlevel--;  
        if (NULL != e.lchild)//若左子樹不為空  
        {  
            EnQueue(Q, *e.lchild);//將元素入隊(duì)列  
            nextlevel++;//下一層數(shù)自增  
        }  
        if (NULL != e.rchild)//若右子樹不為空  
        {  
            EnQueue(Q, *e.rchild);//將元素入隊(duì)列  
            nextlevel++;  
        }  
        if (0 == curlevel)  
        {  
            levelcount++;  
            printf("——Layer %d node traversal.\n", levelcount);  
            curlevel = nextlevel;  
            nextlevel = 0;  
        }  
    }  
    return 1;  
}  
  
int main(int argc, char* argv[])  
{  
    BiTree T = NULL;  
    printf_s("Please enter the binary tree node:\n");  
    CreateBiTree(T);  
    printf_s("Binary tree created successfully.\n"); 
    printf_s("The hierarchical order traversal of this binary tree is:\n");  
    levelTraverse(T);  
    return 0;  
} 

2.程序結(jié)果：

程序運(yùn)行，在此次、中我使用了二叉樹如下

作為測試樣例，因此輸入ABC##D##EF##G##。其中定義符號“#”為空結(jié)點(diǎn)。、結(jié)果如下圖所示：

由輸出結(jié)果可知，按照層次遍歷的順序分別輸出了每一層的元素，可知算法正確實(shí)現(xiàn)了二叉樹的層次遍歷。

3.分析和改進(jìn)應(yīng)用：

分析：此次、的整體思路是：層次遍歷借助隊(duì)列實(shí)現(xiàn)，首先先定義二叉樹及隊(duì)列的初始3.化，按照常規(guī)的方式分別定義隊(duì)列的判斷空IsEmpty函數(shù)，入隊(duì)函數(shù)EnQueue與出隊(duì)函數(shù)DeQueue，在二叉樹的層次遍歷levelTraverse方法中，將二叉樹的根結(jié)點(diǎn)進(jìn)入隊(duì)列中，判斷隊(duì)列不為NULL。打印輸出該結(jié)點(diǎn)存儲的元素。判斷結(jié)點(diǎn)如果有孩子（左孩子、右孩子），就將孩子進(jìn)入隊(duì)列中。循環(huán)以上操作，直到 BT->lchild == NULL、BT->rchild=NULL。

改進(jìn)應(yīng)用：基于二叉樹的層次的層次遍歷，可以改進(jìn)一個有關(guān)于二叉樹層次遍歷的應(yīng)用，即利用層次遍歷求出二叉樹的寬度。二叉樹的寬度是指二叉樹各層結(jié)點(diǎn)個數(shù)的大值。因?yàn)槎鏄涞膶哟伪闅v借助于隊(duì)列實(shí)現(xiàn)，每次打印當(dāng)前結(jié)點(diǎn)后將其左子樹右子樹入隊(duì)，此時隊(duì)列中既包含當(dāng)前層的結(jié)點(diǎn)，也包含下一層的結(jié)點(diǎn)，若我們將當(dāng)前層的結(jié)點(diǎn)全部出隊(duì)，剩余的就是下一層的結(jié)點(diǎn)個數(shù)。所以，可以使用maxWidth來表示大寬度，若下一層的結(jié)點(diǎn)個數(shù)大于maxWidth，則更新maxWidth，最終隊(duì)列為空，得到的maxWidth即為二叉樹的寬度。實(shí)現(xiàn)的函數(shù)代碼如下：

int WidthCount ( BiTree root) {        
    Queue Q;        
    BiTree T;       
    if (!root)   
        return;  //若是空樹則直接返回            
    InitQueue(Q); // 初始化空隊(duì)列Q    
    int width = 0;  
    int num = 1;  
    int maxWidth = 0;  
    EnQueue(Q,root);       
    while (!IsEmpty(Q))   
    {           
        DeQueue(Q,T);           
        printf("%d ", T->Data); // 訪問取出隊(duì)列的結(jié)點(diǎn)            
        if ( T->lchild )     
            EnQueue(Q, T->lchild); width++;          
        if ( T->rchild )    
            EnQueue(Q, T->rchild); width++;    
        if(--num == 0){  
            num = witdh;  
            if(maxWidth< width){  
                maxWidth = width;  
            }  
            width = 0;  
        }  
    }   
    return maxWidth ;  
} 

六 、小結(jié)：

?此次是有關(guān)于二叉樹層次遍歷算法的實(shí)現(xiàn)，算法的思想比較清晰，即先定義一個循環(huán)隊(duì)列，使這個隊(duì)中的數(shù)據(jù)域存放二叉樹中的元素。先將二叉樹根結(jié)點(diǎn)入隊(duì)，然后出隊(duì)，訪問該結(jié)點(diǎn)，如果有左子樹，則將左子樹根結(jié)點(diǎn)入隊(duì)；如果存在右子樹，則將右子樹的根結(jié)點(diǎn)入隊(duì)。然后出隊(duì)，對出隊(duì)結(jié)點(diǎn)訪問，如此循環(huán)直到隊(duì)列為空。最終，出隊(duì)的順序就是層次遍歷的順序。關(guān)于層次遍歷的應(yīng)用，我是在層次遍歷中的特殊結(jié)構(gòu)，即打印結(jié)點(diǎn)后把它左右子樹入隊(duì)，該隊(duì)列中有當(dāng)前層的結(jié)點(diǎn)，也有下一層結(jié)點(diǎn)，因此可以將當(dāng)前層的結(jié)點(diǎn)全部出隊(duì)，剩下的為下一層的結(jié)點(diǎn)個數(shù)，然后只需要比較當(dāng)前最多的層結(jié)點(diǎn)和下一層結(jié)點(diǎn)數(shù)的大小即可。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

名稱欄目：二叉樹的編程與實(shí)現(xiàn)（C語言）-創(chuàng)新互聯(lián)
鏈接地址：http://www.chinadenli.net/article4/ijdoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)網(wǎng)站制作、面包屑導(dǎo)航、App開發(fā)、商城網(wǎng)站、做網(wǎng)站、手機(jī)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)