程序员数据结构笔记（五）

回溯法:
　　回溯跟递归都是程序员考试里常出现的问题,大家必须掌握!
　　回溯法的有关概念:
　　1) 解答树:叶子结点可能是解,对结点进行后序遍历.
　　2) 搜索与回溯
　　五个数中任选三个的解答树(解肯定有三层,至叶子结点):
　　　　　　　　　　　　　　　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

　　回溯算法实现中的技巧:栈
　　要搞清回溯算法，先举一个(中序遍历二叉树的非递归算法)来说明栈在非递归中所起的作用。
　　　　　 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) 该解答树的叶子结点