程序員數(shù)據(jù)結構筆記（五）

回溯法:
    回溯跟遞歸都是程序員考試里常出現(xiàn)的問題,大家必須掌握!
    回溯法的有關概念:
    1) 解答樹:葉子結點可能是解,對結點進行后序遍歷.
    2) 搜索與回溯
    五個數(shù)中任選三個的解答樹(解肯定有三層,至葉子結點):
    　　　　　　　　　　ROOT 虛根
    　　　/　　　　　　/　　　 |　　\　　\
    　　 1　　　　　 2　　　　 3　　4　　 5
    　/ 　|　 |　 \　　/ | \ 　　 /\　　|
     2　　3　 4　　5　3　4　5　　4　5　 5
    /|\ 　/\　|　 /\　|　|
     3 4 5 4　5 5　4　5 5　5
    回溯算法實現(xiàn)中的技巧:棧
    要搞清回溯算法，先舉一個(中序遍歷二叉樹的非遞歸算法)來說明棧在非遞歸中所起的作用。
     A 過程：push()->push()->push()->push()棧內結果:ABDE(E為葉子,結束進棧)
    / \　　　pop()　　　ABD(E無右孩子,出棧)
    　 B　 C　　 pop()　　　AB(D無右孩子,出棧)
    　/\　　　　 pop()　　　A(B有右孩子,右孩子進棧)
     D　F 　　　　.　　　　　 .
    /　/\　　　　 . 　　　　　.
     E　G　H　　　　. 　　　　　.
    /　　　　　　　 .　　　　　 .
     I　　　　　　　 最后結果： EDBGFIHAC
    簡單算法:
    　…
    if(r!=NULL) //樹不空
    { while(r!=NULL)
    　{ push(s,r);
    r=r->lch;　　　//一直向左孩子前進
    　}
    　while(!empty(s)) // 棧非空,出棧
    　{ p=pop(s);
    printf(p->data);
    p=p->rch;　　　//向右孩子前進
    while(p!=NULL)
    { push(s,p);
    　p=p->lch; //右孩子進棧
    }
    　}
    }　//這就是傳說中的回溯,嘻嘻……沒嚇著你吧
    5選3問題算法:
    思想: 進棧:搜索
    出棧:回溯
    邊建樹(進棧)邊遍歷(出棧)
    基本流程:
    太復雜了,再說我不太喜歡用WORD畫圖（有損形象），以后再整理!
    程序: n=5;r=3
    ……
    init(s)　　//初始化棧
    push(s,1)　//根進棧
    while(s.top    　push(s,s.data[s.top]+1); //孩子入棧
    while(!empty(s))
    { if(s.top=r-1)
    　判斷該"解"是否為解.
    　x=pop(s); //保留x,判斷是否為值n,如果是n,則出棧
    　while(x==n)
    　x=pop(s);
    　push(s,x+1);
    　while(s.top    　push(s,s.data[s.top]+1);
    }
    背包問題: TW=20 , w[5]={6,10,7,5,8}
    解的條件:1) 該解答樹的葉子結點