初级软考资料:程序员考试补课笔记-第十三天
发布时间：2010/3/27 9:06:08 来源：城市学习网 编辑：admin
今天特别的兴奋，起床也起得特别的早。在走之前我把电脑开了，那当然是为了做服务器，我不知道我开学后能不能够这样做，因为家里的一些因素。不过只要能为大家服务我已经很开心了，而且也一种强激的幸福感，这种幸福并不是一般的家庭幸福。我为坚持做下去的，我也常常问一些网友关于这件事，他们都说只有你自己可以就行了，他们都支持我坚持做下去。好吧，说远了离题了，我说说今天的补课吧。
今天的课程也令我吃了一惊，是讲数据结构里的树。为什么队列和堆栈都没有讲就直接讲树呢？会不会太快了一点，而且我们刚放完假有些人都没有集中精神到课堂来。不过我会相信老师的选择的，应该有他的理由。那么就来讲讲树的一些基本概念，大家都知道树是数据结构里的非线性结构之一，和之前说的链表是完全不同的，链表就只有前驱和后继结点，但树就不是了，他可以有很多的结点，称为分支结点，而且他的分支结点又可以有分支结点。因为树接触到的概念太多了，只好自己看一下书才行。树运用得很广范，像我们操作系统里文件管理就是了，多级的目录。二级目录就像树的子树，而且子树里可能还有很多的子树，越往下就越多级。
我们来试试定义一个树的结构，一般树都分得很随意，所有我们这里也随便画一个树来说一下。看图第十三天图一我们看到圆圈就代表一个结点，而且最顶的那个就是根结点，往下的就是子结点。子结点的上一个就是父结点，同一级的结点左右都是为兄弟结点。我们按照这样的结构定义一个，如下：
structtree
;
下面来看看如何建立一棵树。
structtreep，r;
r=malloc);/建立根结点空间/
r->data=3;/根结点赋值/
r->next=r->pre=r->up=NULL;
p=malloc);/建立第二个结点/
r->down=p;/根结点的子结点连向新的子结点/
p->data=5;/子结点赋值/
p->pre=NULL;
p->next=malloc);
p->next->data=2;
p->next->pre=p;
:
:
:
因为结点多而无规律性，所有这种建立方法是不能采用的，现在只是拿出来研究一下一棵树是如何建立起来的。
现在说说另一种树“二叉树”。因为二叉树与一般的树结构比较，二叉树在结构上更规范和更有确定性，因此，应用也比树更为广泛。二叉树与树不同，首先二叉树可以为空，空的二叉树没有结点；另外，在二叉树中，结点的子树是有序的，分左、右两棵子二叉树。
二叉树又是如何建立的呢？这里很简单，因为二叉树有其规律性，下面请看
typedefstructbnode
btree;
voidcreat
}
voidinsert
这条程序不单只建立了一个树，而且还给排好了序（左小右大）。输入相应的数值看看结果，如图第十三天图二。
今天也就是这些了，还有得就是要多看些递归的程序，因为树的建立和操作离不开递归。还有的就是大家做做如下一题，就是已知有一个无序的二叉树，让我们用中序遍历排列成由大到小的程序。
