分享
 
 
 

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

王朝other·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

今天继续是讲二叉树,树一个重要的操作就是遍历。所谓遍历就是输出所有的结点,二叉树不同于树只有前序和后序遍历,因为二叉树左右子树木特点,所有还有另一种遍历方法,就是中序。这些遍历也十分简单,最主要的还是看根遍历的前后来分别是前中后序遍历的。下面看图第十四天

这些颜色圈着代表分别当一个树来看,所有我们知道其规律就可以写出程序来了,程序也十分简单,如下:

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) ); /*巧妙的就是这里了*/

}

}

一条程序可以反应该人的水平说的真没错,这条程序几个地方都写得很好,特别巧妙的可以令递归返回值到最顶的那个可真棒啊。就这样随着时间的到来,我们也差不多放学了,我还真的要努力才行了,我要努力再努力,坚持再坚持。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有