程序员考试补课笔记

今天继续是讲二叉树，树一个重要的操作就是遍历。所谓遍历就是输出所有的结点，二叉树不同于树只有前序和后序遍历，因为二叉树左右子树木特点，所有还有另一种遍历方法，就是中序。这些遍历也十分简单，最主要的还是看根遍历的前后来分别是前中后序遍历的。下面看图第十四天这些颜色圈着代表分别当一个树来看，所有我们知道其规律就可以写出程序来了，程序也十分简单，如下：
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->datadata) insert (h->left);
　　　　if(p->data>h->data) insert(h->right);
　　}
}
　　看上去很简单的几行，可是因为递归就得弄明白一些思路，看看它是如何产生插入到合适的位置，和前一堂课的建立二叉树思路一样，也是比较他的值大小排位置。大家要好好的看明白。就是因为我们班里的几个同学都对树比较陌生，跟不上来所以老师决定先把树告一断落，其实树还有很多方面的知识还没有讲到，只好等过一排思维清晰了才可以继续，其实如果我之前没有自己看过一下，到老师说的时候可能真的听不明白，突意间飞来的大难点啊。