輸入一個二叉樹和一個整數(shù)，打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑。從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑。

創(chuàng)新互聯(lián)是一家專注于成都網(wǎng)站制作、成都網(wǎng)站設(shè)計、外貿(mào)營銷網(wǎng)站建設(shè)與策劃設(shè)計,彭山網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)十余年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:彭山等地區(qū)。彭山做網(wǎng)站價格咨詢:028-86922220

  如上圖的二叉樹，當(dāng)輸入根結(jié)點和一個數(shù)值12的時候，就有兩條路徑“1->2->4->5”和“1->3->8”，如果存在，就輸出上述路徑，如果沒有任何一條路徑滿足就不輸出路徑并提示；

  首先，路徑一定是從根結(jié)點開始到某個葉子結(jié)點結(jié)束，這才是一條路徑，因此，應(yīng)該最先訪問的就是根結(jié)點，而在二叉樹的先中后序遍歷中只有先序遍歷是最先訪根結(jié)點的，所以可以用如下方法：用先序遍歷方法遍歷二叉樹，每當(dāng)經(jīng)過一個結(jié)點的時候就將其值進(jìn)行保存相加，如果中途發(fā)現(xiàn)或者到達(dá)葉子結(jié)點之后，當(dāng)前路徑相加得到的值并不滿足要求的值，則往回退并將值減去，或者當(dāng)前路徑已經(jīng)滿足，則需要再去換一條路徑訪問看是否還有其他路徑滿足條件，而能夠提供往回退的方法就只有遞歸了，直至遍歷完畢二叉樹；

程序設(shè)計如下：

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

struct BinaryTreeNode//二叉樹結(jié)點數(shù)據(jù)結(jié)構(gòu)
{
    int _val;
    BinaryTreeNode *_Lnode;
    BinaryTreeNode *_Rnode;

    BinaryTreeNode(int val)
        :_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;
    }
}

void PrevOrder(BinaryTreeNode *root)//前序遍歷打印出二叉樹
{
    if(root != NULL)
    {
        cout<<root->_val<<" ";
        PrevOrder(root->_Lnode);
        PrevOrder(root->_Rnode);
    }
}

void _Count(BinaryTreeNode* root, vector<int> *pv, int& count, int num)
{
    if(root != NULL)
    {
        count += root->_val;//每當(dāng)一個結(jié)點不為NULL的時候，就將其放入容器中且加上其值
        (*pv).push_back(root->_val);

        _Count(root->_Lnode, pv, count, num);
        _Count(root->_Rnode, pv, count, num);
        if(count == num)//當(dāng)找到一個路徑的時候就將其打印出來
        {
            cout<<"A Path Is : ";
            for(size_t i = 0; i < (*pv).size(); ++i)
                cout<<(*pv)[i]<<"->";
            cout<<"NULL"<<endl;
        }

        count -= (*pv).back();//退回上一步
        (*pv).pop_back();
    }
}

void PrintPathOfNumInBT(BinaryTreeNode *root, int num)//打印路徑
{
    assert(root);

    vector<int> v;//用一個容器來存放路徑
    int count = 0;//用一個計數(shù)器計算和
    _Count(root, &v, count, num);
}

int main()
{
    int arr[] = {1,2,6,'#','#',4,5,'#','#','#',3,7,'#','#',8,'#','#'};
    int num = 12;

    BinaryTreeNode *root = CreateBinaryTree(arr, sizeof(arr)/sizeof(arr[0]));
    cout<<"PrevOrder:";
    PrevOrder(root);
    cout<<endl;

    PrintPathOfNumInBT(root, num);

    DestoryBinaryTree(root);
    return 0;
}

運行程序：

《完》

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

文章名稱：二叉樹中和為某一值的路徑——25-創(chuàng)新互聯(lián)
標(biāo)題鏈接：http://vcdvsql.cn/article20/jggjo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)網(wǎng)站制作、網(wǎng)站導(dǎo)航、響應(yīng)式網(wǎng)站、品牌網(wǎng)站制作、外貿(mào)建站、虛擬主機

廣告

聲明：本網(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)