二叉樹的編程與實現(xiàn)（C語言）-創(chuàng)新互聯(lián)

一、目的：

成都創(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è)的網(wǎng)站。10多年品質(zhì)，值得信賴！

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

二、環(huán)境：

operating system version：Win11

CPU instruction set:? x64

Integrated Development Environment：Viusal Studio 2022

三、內(nèi)容：

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

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

四、要求：

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

五、步驟：

1. 程序：

#include "stdio.h"  
#include "stdlib.h"  
#define INITQUEUE 20  
  
typedef struct BiTNode  
{  
    char data;    //定義結(jié)點數(shù)據(jù)  
    struct BiTNode* lchild;//定義結(jié)點左孩子指針  
    struct BiTNode* rchild;//定義結(jié)點右孩子指針  
}BiTNode, * BiTree;//定義二叉樹結(jié)點  
  
typedef struct Queue  
{  
    BiTNode* front;//定義隊列頭指針  
    BiTNode* tail;//定義隊列尾指針  
    int size;//定義隊列空間大小  
}Queue;  
  
int InitQueue(Queue& Q)  
{//InitQueue初始化隊列  
    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判斷隊列是否為空  
    if (Q.tail == Q.front)  
    {  
        return true;  
    }  
    else  
    {  
        return false;  
    }  
}  
  
int EnQueue(Queue& Q, BiTNode e)  
{//EnQueue將元素入隊列  
    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將元素出隊列  
    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é)點數(shù)  
    int nextlevel = 0;  //下一層還未訪問的結(jié)點數(shù)  
    InitQueue(Q);  
    EnQueue(Q, *T);  
    while (!IsEmpty(Q))//當隊列不為空時循環(huán)  
    {  
        DeQueue(Q, e);//出隊列  
        printf("%c ", e.data);//打印該元素  
        curlevel--;  
        if (NULL != e.lchild)//若左子樹不為空  
        {  
            EnQueue(Q, *e.lchild);//將元素入隊列  
            nextlevel++;//下一層數(shù)自增  
        }  
        if (NULL != e.rchild)//若右子樹不為空  
        {  
            EnQueue(Q, *e.rchild);//將元素入隊列  
            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é)果：

程序運行，在此次、中我使用了二叉樹如下

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

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

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

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

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

int WidthCount ( BiTree root) {        
    Queue Q;        
    BiTree T;       
    if (!root)   
        return;  //若是空樹則直接返回            
    InitQueue(Q); // 初始化空隊列Q    
    int width = 0;  
    int num = 1;  
    int maxWidth = 0;  
    EnQueue(Q,root);       
    while (!IsEmpty(Q))   
    {           
        DeQueue(Q,T);           
        printf("%d ", T->Data); // 訪問取出隊列的結(jié)點            
        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)于二叉樹層次遍歷算法的實現(xiàn)，算法的思想比較清晰，即先定義一個循環(huán)隊列，使這個隊中的數(shù)據(jù)域存放二叉樹中的元素。先將二叉樹根結(jié)點入隊，然后出隊，訪問該結(jié)點，如果有左子樹，則將左子樹根結(jié)點入隊；如果存在右子樹，則將右子樹的根結(jié)點入隊。然后出隊，對出隊結(jié)點訪問，如此循環(huán)直到隊列為空。最終，出隊的順序就是層次遍歷的順序。關(guān)于層次遍歷的應(yīng)用，我是在層次遍歷中的特殊結(jié)構(gòu)，即打印結(jié)點后把它左右子樹入隊，該隊列中有當前層的結(jié)點，也有下一層結(jié)點，因此可以將當前層的結(jié)點全部出隊，剩下的為下一層的結(jié)點個數(shù)，然后只需要比較當前最多的層結(jié)點和下一層結(jié)點數(shù)的大小即可。

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

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

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

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

猜你還喜歡下面的內(nèi)容