C++基礎:遞歸遍歷存儲層次結構的鏈表

最近碰到要從一個存儲層次結構的鏈表中拿數據出來處理的問題。層次結構嵌套的層次是不明確的，所以要用遞歸來讀取。遞歸其實就是深度優(yōu)先搜索，也就是回溯法。遞歸是求解問題本省能夠劃分為形式、結構相同，但是問題規(guī)模逐漸變小的子問題的問題的利器。
    所以遞歸實現有兩個關鍵點：
    一就是問題劃分出來的子問題和原問題有相同的形式、結構，只要這樣才能利用同一個函數體，即所說的遞歸調用。
    二就是子問題的規(guī)模逐漸變小，這個在遞歸調用時就體現在參數上。所以遞歸函數肯定是有參數的，如果沒有參數，則一定是用了全局變量。當問題規(guī)模足夠小的時候，就是遞歸調用返回的時候。在網上看到GOOGLE的筆試題中就考過這個知識點。
    下面用STL的list通用容器模擬了這類問題。
    代碼如下：
    #include
    #include
    using namespace std;
    typedef struct tagNode {
    int data;
    list subList;
    } Node;
    void TraverseList(list L);
    int main()
    {
    list* pList = new list;
    Node* pnode1 = new Node;
    pnode1->data = 1;
    pList->insert(pList->begin(), pnode1);
    Node* pnode2 = new Node;
    pnode2->data = 2;
    pnode1->subList.insert(pnode1->subList.begin(), pnode2);
    Node* pnode3 = new Node;
    pnode3->data = 3;
    pnode2->subList.insert(pnode2->subList.begin(), pnode3);
    Node* pnode4 = new Node;
    pnode4->data = 4;
    pnode3->subList.insert(pnode3->subList.begin(), pnode4);
    Node* pnode5 = new Node;
    pnode5->data = 5;
    pnode4->subList.insert(pnode4->subList.begin(), pnode5);
    Node* pnode6 = new Node;
    pnode6->data = 6;
    list::iterator it = pList->end();
    pList->insert(it, pnode6);
    Node* pnode7 = new Node;
    pnode7->data = 7;
    it = pList->end();
    pList->insert(it, pnode7);
    TraverseList(*pList);
    return 0;
    }
    void TraverseList(list L)
    {
    if (!L.empty()) {
    list::iterator it = L.begin();
    Node* pNode = *it;
    do {
    if (pNode != NULL) {
    cout << pNode->data << endl;
    /*if (!pNode->subList.empty())*/
    TraverseList(pNode->subList);
    }
    } while (++it != L.end() && (pNode = *it) != NULL);
    }
    }