程序员考试补课笔记-第十四天

　　今天继续是讲二叉树，树一个重要的操作就是遍历。所谓遍历就是输出所有的结点，二叉树不同于树只有前序和后序遍历，因为二叉树左右子树木特点，所有还有另一种遍历方法，就是中序。这些遍历也十分简单，最主要的还是看根遍历的前后来分别是前中后序遍历的。下面看图第十四天这些颜色圈着代表分别当一个树来看，所有我们知道其规律就可以写出程序来了，程序也十分简单，如下：
out1(btree *t) /*前序遍历*/
{
　　printf("%d",t->data);
　　out1(t->left);
　　out1(t->right);
}

out2(btree *t) /*中序遍历*/
{
　　out2(t->left);
　　printf("%d",t->data);
　　out2(t->right);
}

out3(btree *t) /*后序遍历*/
{
　　out3(t->left);
　　out3(t->right);
　　printf("%d",t->data);
}
　　上面三种遍历是不是很简单（这个递归想一想就明白的了），而且他们很像似只是改变了行位置，我们由此可以看出如果是前序的那个输出是最先的，跟着才是进入左树到右树。看完了遍历就看看二叉查找树，二叉查找树是这样的一种树，他的左结点都小于根，右结点都大于左结点。有这么一种性质所以他的插入特别好办，用中序遍历的方法设计这个排序算法特别好，因为这个树本来就是这样排序下来的。下面就来看看程序是如何实现的
insert(btree *h,btree *p)
{
　　if(h= =NULL) h=p; p->left=p->right=NULL; /*最后一个结点一定是没有左右子树*/
　　else
　　{
　　　　if(p->data<h->data) insert (h->left);
　　　　if(p->data>h->data) insert(h->right);
　　}
}
　　看上去很简单的几行，可是因为递归就得弄明白一些思路，看看它是如何产生插入到合适的位置，和前一堂课的建立二叉树思路一样，也是比较他的值大小排位置。大家要好好的看明白。就是因为我们班里的几个同学都对树比较陌生，跟不上来所以老师决定先把树告一断落，其实树还有很多方面的知识还没有讲到，只好等过一排思维清晰了才可以继续，其实如果我之前没有自己看过一下，到老师说的时候可能真的听不明白，突意间飞来的大难点啊。
　　时间真的用了很多在这些树上，而且还没有什么大的效果。老师也马上看机行事，跳过这节来讲一下查找这章。到于查其实我们平常也接触得多了，特别是我以前学Foxbase的时候，基本上什么都离不开查找，不过当时的查找就是这么一条命令就搞定了。现在要自己编出来也真的挺好玩的，以前完全封装性的Foxbase命令，今天就要编成这个系统的C语言来深入研究它，之前说的链表和结构就是用来做数据库的了（如果我没有估错的话）。说多了费了，马上讲讲学习查找的情况。顺序查找相信大家都知道原理了，因为一个一个顺序的判断是否相等这是最常见的了。我在这里就不再多讲，继续讲下一个，折半查找法。在讲这个之前老师和我们做了一个游戏，就是他在纸上写下一个数值，范围在1到1000内让我们来猜，如果我们说的数大过这个数老师就是太大了，反之就太小了。其实这个折半原理早就在QB里见过了，也没有什么难度嘛。很快我们就按照那个方法给猜出来了得数，老师都见我们懂了的样子就直接叫我们写个程序好了，当时我一时看到这题有重复的规律性就一直以递归的思路来做这题了，可是我错了，不过这个错令我学到了另一个技巧。下面先来看看我的程序，如下：
假如a[]已经是有了值，而且还是顺序排好的了。
serch(int r, int k, int n)
{
　　int mid;
　　if(r>k) return(-1);
　　else
　　{
　　　　mid=(r+k)/2;
　　　　if(a[mid]>n) serch(r,mid-1,n);
　　　　if(a[mid]<n) serch(mid+1,k,n);
　　　　if(a[mid]= =n) return(mid) /*注意就是这里有问题了*/
　　}
}
　　好像看上去没有什么问题似的，其实问题都挺大的，因为返回值根本不能返到最顶的那个自调用里，就只能返回一层，所有我的答案也根本出不来嘛。虽然老师还是赞了我一下会去用递归来做这题（其实因为本来循环可以很简单的可以实现了，而且不会浪费那么多的空间了），不过错还是错的。老师按照我的这个思路写了一个新的出来，如下：
serch(int r,int k,int n)
{
　　int mid;
　　if (r > k) return (-1);
　　mid =(r+k)/2;
　　if(a[mid]= =n) return(mid);
　　else
　　{
　　　　a[mid]<n ? r=mid+1; k=mid-1;
　　　　return (serch(r,k,n) ); /*巧妙的就是这里了*/
　　}
}
　　一条程序可以反应该人的水平说的真没错，这条程序几个地方都写得很好，特别巧妙的可以令递归返回值到最顶的那个可真棒啊。就这样随着时间的到来，我们也差不多放学了，我还真的要努力才行了，我要努力再努力，坚持再坚持。

原文转自：http://www.ltesting.net