新建 文本文档 (2).txt

这是一个用java做的二叉树的遍历的实例！

　　　　　　　结果: 102　210　214　321　333　600　665　699　874(排序成功)

　　最近在看一位程序员的笔记,也挺不错的啊.这应当是他的网站.他总说他的网站人气不够,现在顺便就帮他宣传一下啦！http://zhgpa.vicp.net/bbs，大家有时间多去去哦，呵呵!谢谢大伙支持！另外,还向大家推荐一个网站：http://kaowang.com/，挺不错的一个考试网站。学到不少东东啊！


八大类算法 

　　程序员考试下午试题最后一道一般是八大类算法里头的.大家尤其要注意的是递归，因为近几年都考了，而且有的还考两题。可以说如果我们不掌握递归就没有掌握C，况且递归是C里的难点。为了控制合格率，程序员考试不会让我们轻松过关的，为了中国软件业，我想也应该这样啊。
　　　　/数据结构(离散)
　　迭代
　　　　\数值计算(连续)
　　枚举 策略好坏很重要
　　递推
　　递归
　　回溯
　　分治
　　贪婪
　　动态规划
　　其中：递推、递归、分治、动态规划四种算法思想基本相似。都是把大问题变成小问题，但技术上有差别。



第四天 时间:9/26/2003 

枚举:
　　背包问题:
　　枚举策略：1)可能的方案：2N
　　　　　　　2)对每一方案进行判断.

　　枚举法一般流程：
　　　　while(还有其他可能方案)
　　　　{ 按某种顺序可难方案;
　　　　　检验方案;
　　　　　if(方案为解)
　　　　　　保存方案;
　　　　　}
　　　　}
　　枚举策略:
　　例：把所有排列枚举出来 P6=6!.
　　　Min:123456
　　　Max:654321
　　　a1a2a3a4a5a6=>?(下一排列)=>?
　　　比如:312654的下和种情况=>314256

递归
　　递归算法通常具有这样的特征：为求解规模为N的问题，设法将它分解成一些规模较小的问题，然后从这些较小问题的解能方便地构造出题目所需的解。而这些规模较小的问题也采用同样的方法分解成规模更小的问题，通过规模更小的问题构造出规模校小的问题的解，如此不断的反复分解和综合，总能分解到最简单的能直接得到解的情况。
　　因此,在解递归算法的题目时,要注意以下几点:
　　1) 找到递归调用的结束条件或继续递归调用条件.
　　2) 想方设法将处理对象的规模缩小或元素减少.
　　3) 由于递归调用可理解为并列同名函数的多次调用,而函数调用的原则是一层一层调用,一层一层返回.因此,还要注意理解调用返回后的下一个语句的作用.在一些简单的递归算法中,往往不需要考虑递调用返回后的语句处理.而在一些复杂的递归算法中,则需要考虑递归调用返回后的语句处理和进一步的递归调用.
　　4) 在读递归程序或编写递归程序时,必须要牢记递归函数的作用,这样便于理解整个函数的功能和知道哪儿需要写上递归调用语句.当然,在解递归算法的题目时,也需要分清递归函数中的内部变量和外部变量.
　　表现形式:
　　●定义是递归的(二叉树,二叉排序树)
　　●存储结构是递归的(二叉树,链表,数组)
　　●由前两种形式得出的算法是递归的
　　一般流程: function(variable list(规模为N))
　　　{ if(规模小,解已知) return 解;
　　　　else {
　　　　　把问题分成若干个部分;
　　　　　某些部分可直接得到解;
　　　　　而另一部分(规模为N-1)的解递归得到;
　　　　}
　　}
　　例1：求一个链表里的最大元素.
　　大家有没想过这个问题用递归来做呢?
　　非递归方法大家应该都会哦?
　　　　Max(nodetype *h) {
　　　　　nodetype *p;
　　　　　nodetype *q; //存放含最大值的结点
　　　　　Int max=0;
　　　　　P=h;
　　　　　While(p!=NULL){
　　　　　　if (max<p->data) {
　　　　　　　max=p->data;
　　　　　　　q=p;
　　　　　　}
　　　　　　p=p->next;
　　　　　}
　　　　　return q;
　　　　}
　　下面真经来了,嘻嘻嘻~~~
　　　　*max(nodetype *h) {
　　　　　nodetype *temp;
　　　　　temp=max(h->next);
　　　　　if(h->data>temp->data)
　　　　　　return h;
　　　　　else
　　　　　　return temp;
　　　　}
　　大家有空想想下面这个算法：求链表所有数据的平均值(我也没试过)，不许偷懒，用递归试试哦!
　　递归程序员考试题目类型：1)就是链表的某些操作(比如上面的求平均值)
　　　　　　　　　　　　　　2)二叉树(遍历等)

　　例2.判断数组元素是否递增
　　　　　int jidge(int a[],int n) {
　　　　　　if(n==1) return 1;
　　　　　　else
　　　　　　　if(a[0]>a[1]) return 0;
　　　　　　　else return jidge(a+1,n-1);
　　　　　}

　　例3.求二叉树的高度(根据二叉树的递归性质:(左子树)根(右子树))
　　　　　int depth(nodetype *root) {
　　　　　　if(root==NULL) 
　　　　　　　return 0;
　　　　　　else {
　　　　　　　h1=depth(root->lch);
　　　　　　　h2=depth(root->rch);
　　　　　　　return max(h1,h2)+1;
　　　　　　}
　　　　　 }
　　自己想想求二叉树结点个数(与上例类似)

　　例4.已知中序遍历和后序遍历,求二叉树.
　　　设一二叉树的:
　　　中序 S:E D F B A G J H C I
　　　　　　^start1 ^j ^end1
　　　后序 T:E F D B J H G I C A
　　　　　　^start2 ^end2
　　　　node *create(char *s,char *t, int start1,int start2,int end1,int end2) 
　　　　{ if (start1>end1) return NULL; //回归条件
　　　　　root=(node *)malloc(sizeof(node));
　　　　　root->data=t[end2];
　　　　　找到S中T[end2]的位置为 j
　　　　　root->lch=create(S,T,s1,j-1,start1,j+start2-start1-1);
　　　　　root->rch=create(S,T,j+1,end1,j+start2-start1,end2-1);
　　　　　return root;
　　　　}

　　例5.组合问题
　　　n 个数: (1,2,3,4,…n)求从中取r个数的所有组合.
　　　设n=5,r=3;
　　　递归思想：先固定一位 5 (从另四个数当中选二个)
　　　　　　　　　　　　　 5,4 (从另三个数当中选一个)
　　　　　　　　　　　　　 5,4,3 (从另二个数当中选零个)
　　　即：n-2个数中取r-2个数的所有组合
　　　　　…
　　程序:
　　　void combire(int n,int r) {
　　　　for(k=n;k>=n+r-1;k--) {
　　　　　a[r]=k;
　　　　　if(r==0) 打印a数组(表示找到一个解);
　　　　　else combire(n-1,r-1);
　　　　}
　　　}


第五天 9/28/2003 


回溯法:
　　回溯跟递归都是程序员考试里常出现的问题,大家必须掌握!
　　回溯法的有关概念:
　　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<r-1)&&(s.data[s.top]!=n) //有孩子
　　　　　　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<r-1)&&(s.data[s.top]!=n)
　　　　　　push(s,s.data[s.top]+1);
　　　　　}

　　背包问题: TW=20 , w[5]={6,10,7,5,8} 
　　解的条件:1) 该解答树的叶子结点
　　2) 重量最大
　　解答树如下：　　　ROOT
　　　　　　　/ | | | \
　　　　　　　　　 6 10　　 7　　　5　 8
　　　　　　　　/ | | \　 / | \　 / \　| 
　　　　　　　 10 7 5　8 7　5　8 5　 8 8
　　　　　　　　　| |　　　　　　| 
　　　　　　　　　5 8　　　　　　8
　　程序:
　　temp_w 表示栈中重量和
　　…
　　init(s); //初始化栈
　　i=0;
　　While(w[i]>TW)
　　　i++;
　　　If(i==n) Return -1; //无解
　　　Else {
　　　　Push(s,i);
　　　　Temp_w=w[i];
　　　　i++;
　　　　while(i<n)&&(temp_w+w[i]<=TW)
　　　　　{ push(s,i);
　　　　　　temp_w+=w[i];
　　　　　　i++;
　　　　}
　　　　max_w=0;
　　　　while(!empty(s))
　　　　　{ if(max_w<temp_w)
　　　　　　　max_w=temp_w;
　　　　　　　x=pop(s);
　　　　　　　temp_w-=w[x];
　　　　　　　x++;
　　　　　　　while(x<n)&&(temp_w+w[x]>TW)
　　　　　　　　x++;
　　　　　　　while(x<n)
　　　　　　　{ push(s,x);
　　　　　　　　temp_w=temp_w+w[x];
　　　　　　　　x++;
　　　　　　　　while(x<n)&&(temp_w+w[x]>TW)
　　　　　　　　x++;
　　　　　　　}
　　　　　} 
　　请大家思考:四色地图问题,比如给中国地图涂色,有四种颜色,每个省选一种颜色,相邻的省不能取同样的颜色.不许偷懒，不能选人口不多于xxxxＷ的"大国"哦!如果真的有一天台湾独立了，下场就是这样了，一种颜色就打发了，不过台湾的程序员们赚到了，省事！呵呵。

贪婪法:
　　不求最优解,速度快(以精确度换速度)

　　例:哈夫曼树,最小生成树

　　装箱问题:
　　有n个物品,重量分别为w[n]，要把这n个物品装入载重为TW的集装箱内,需要几个集装箱?
　　思想1:对n个物品排序
　　拿出第1个集装箱，从大到小判断能不能放。
　　2 …
　　3 …
　　. …
　　. …
　　思想2: 对n个物品排序
　　用物品的重量去判断是否需要一只新箱子，如果物品重量小于本箱子所剩的载重量,则装进去,反之则取一只新箱子。

　　程序:
　　count=1;qw[0]=TW;
　　for(i=0;i<n;i++)