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

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

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

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

程序設計如下：

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

struct BinaryTreeNode//二叉樹結點數據結構
{
    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;//每當一個結點不為NULL的時候，就將其放入容器中且加上其值
        (*pv).push_back(root->_val);

        _Count(root->_Lnode, pv, count, num);
        _Count(root->_Rnode, pv, count, num);
        if(count == num)//當找到一個路徑的時候就將其打印出來
        {
            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;//用一個計數器計算和
    _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;
}

運行程序：

《完》

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

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

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

廣告

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