從上往下打印二叉樹——23-創(chuàng)新互聯(lián)

從上往下打印出二叉樹的每個結點，同一層的結點按照從左到右的順序打印。例如如下二叉樹打印出的結果為1、2、3、4、5、6、7、8、9。

十年的銅川網站建設經驗，針對設計、前端、開發(fā)、售后、文案、推廣等六對一服務，響應快，48小時及時工作處理。營銷型網站建設的優(yōu)勢是能夠根據用戶設備顯示端的尺寸不同，自動調整銅川建站的顯示方式，使網站能夠適用不同顯示終端，在瀏覽器中調整網站的寬度，無論在任何一種瀏覽器上瀏覽網站，都能展現(xiàn)優(yōu)雅布局與設計，從而大程度地提升瀏覽體驗。成都創(chuàng)新互聯(lián)從事“銅川網站設計”,“銅川網站推廣”以來，每個客戶項目都認真落實執(zhí)行。

從上往下打印二叉樹——23

上面所說的也就是二叉樹的層序遍歷，對于層序遍歷來說，首先訪問的肯定是根節(jié)點，然后是其左右結點，之后就是左子樹的左右結點和右子樹的左右結點，依次往下，如果使用像前中后序遍歷那樣按照左右結點去遞歸打印的話肯定是不行的，因為并不能一直先訪問某個左結點或者右結點，而是應該左右交叉訪問；

上面的二叉樹中，打印的順序是1、2、3、4、5、6、7、8、9，可以想到按照隊列的方式依次將其放入其中，而先進先出，得到的也就是打印的順序，至于如何存放，可以先將根結點放入其中，拿到隊首結點，如果隊首結點的左右結點不為NULL，就依次放入隊列中，然后將隊首元素pop出，再循環(huán)取隊首元素進行判斷放入......直至遍歷完二叉樹且隊列為空為止；

程序設計如下：

#include <iostream>
#include <assert.h>
#include <queue>
using namespace std;

struct BinaryTreeNode//二叉樹結點結構體
{
    int _val;
    BinaryTreeNode *_Lnode;
    BinaryTreeNode *_Rnode;

    BinaryTreeNode(int val)//構造函數(shù)
        :_val(val)
         ,_Lnode(NULL)
         ,_Rnode(NULL)
    {}
};

BinaryTreeNode* _Create(int *arr, size_t& index, size_t size)//前序方式創(chuàng)建二叉樹
{
    if((index < size) && (arr[index] != '#'))
    {
        BinaryTreeNode *root = new BinaryTreeNode(arr[index]);
        root->_Lnode = _Create(arr, ++index, size);
        root->_Rnode = _Create(arr, ++index, size);
        return root;
    }
    else
        return NULL;
}

BinaryTreeNode* CreateBinaryTree(int *arr, size_t size)
{
    assert(arr && size);

    size_t index = 0;
    return _Create(arr, index, size);
}

void DestoryBinaryTree(BinaryTreeNode* root)//銷毀二叉樹
{
    if(root != NULL)
    {
        DestoryBinaryTree(root->_Lnode);
        DestoryBinaryTree(root->_Rnode);
        delete root;
        root = NULL;
    }
}

void LevelOrderBinaryTree(BinaryTreeNode *root)//層序遍歷二叉樹
{
    assert(root);
    queue<BinaryTreeNode*> q;

    q.push(root);
    while(!q.empty())
    {
        if(q.front()->_Lnode != NULL)
            q.push(q.front()->_Lnode);
        if(q.front()->_Rnode != NULL)
            q.push(q.front()->_Rnode);

        cout<<q.front()->_val<<" ";
        q.pop();
    }
    cout<<endl;
}

void PrevOrder(BinaryTreeNode* root)//前序遍歷二叉樹，為了觀察二叉樹是否創(chuàng)建好
{
    if(root != NULL)
    {
        cout<<root->_val<<" ";
        PrevOrder(root->_Lnode);
        PrevOrder(root->_Rnode);
    }
}

int main()
{
    int arr[] = {1,2,4,'#','#',5,8,'#','#','#',3,6,'#','#',7,'#',9,'#','#'};
    BinaryTreeNode *root = CreateBinaryTree(arr, sizeof(arr)/sizeof(arr[0]));
    cout<<"PrevOrder: ";
    PrevOrder(root);
    cout<<endl;

    cout<<"LevelOrder: ";
    LevelOrderBinaryTree(root);
    DestoryBinaryTree(root);
    return 0;
}

運行程序：

從上往下打印二叉樹——23

《完》

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

本文標題：從上往下打印二叉樹——23-創(chuàng)新互聯(lián)
當前網址：http://www.jbt999.com/article10/dspsdo.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供App設計、Google、App開發(fā)、網站排名、企業(yè)網站制作、虛擬主機

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

猜你還喜歡下面的內容