数据结构 树和二叉树教案

数据结构 树和二叉树教案

ID:14087208

大小:1.29 MB

页数:30页

时间:2018-07-25

数据结构 树和二叉树教案_第1页
数据结构 树和二叉树教案_第2页
数据结构 树和二叉树教案_第3页
数据结构 树和二叉树教案_第4页
数据结构 树和二叉树教案_第5页
资源描述:

《数据结构 树和二叉树教案》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////第六章树和二叉树//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

2、下面呢,我们就讨论第六章、树和二叉树。那么我们回忆一下数据结构四大类。第一类,线性结构,除了广义表以外,我们都讨论完了。现在我们开始讨论第二大类,树形结构,在树形结构里面呢,我们主要讨论两种结构。一类树,一类二叉树(线性结构里头我们讨论了什么?)。首先,我们先看树的数据类型定义。那先看数据对象D:具有相同特性的数据元素的集合,这就是它的数据对象。数据元素之间是一个什么样的关系呢,我们用下面这段话来描述。如果数据对象是一个空集,我们称之为空树。从这里看得出来,所有的数据结构都这样一个空的这样一个结构。空串、空表等等。空树的意思是一个数据元素都没有。否则的话,如果这个集合不是一个空

3、集的话,那么在这个数据结构里面一定存在一个成为根的数据元素root,而且这个数据元素一定是唯一的。就是说,一定存在,而且唯一。那么就是说除了空树以外,如果数据集合里面只有一个数据元素的话,那么这个数据元素,就是这个树的根。如果说这个数据集合里面的元素个数大于1的话,其余个结点呢,我们一定可以给它分成m个子集。这些子集互不相交。并且每个子集本身呢,又是一棵符合上面定义的树。这些子集是树,而且称之为根的子树。我们看一个例子,(画图)ABCDEFGIJ这是一个树,当然它不是空树,这个树呢是9个数据元素的集合。一定存在这一个叫做根的结点。这个A呢,我们称之为树根,除了这个根以外,我们可

4、以分成这样三个集合。以B开始的一个子集,以C开始的一个子集,和D开始的一个子集。这三个子集互不相交,每个子集呢又是一棵树,并且它和根呢,有一个关系存在,这棵树叫做根的子树。这棵树呢,又存在一个根结点,这root根和我们子树根之间,存在这一个这样一个前驱后继的关系,一般画树,我们不画箭头,但是我们讨论的是有向树,是有箭头的。就是说BCD是A的后继。那对于B的这样一个子树,又是符合我们定义的子树,那就是说它有一个根结点,它有两颗子树。在根结点和子树根之间呢,又存在一个前驱和后继的关系,那对E、F来说,它们本身又是一颗树。对于E这棵树来说,它的数据元素只有一个,所以它是仅含有根结点的

5、一颗子树。在定义的时候我们说还有空树的,但是在实际使用的时候,是没有意义的。由于我们数据结构和离散数学还是有一定的关系的,在离散数学中,为了一些数学上的完整性的定义,才有空树这样的定义,在我们数据结构中也有定义,单实际上用处不大。这就是树的类型的一个结构特性。下面我们本来就该讨论基本操作了,但是对于树来讲呢,还有一些基本术语介绍一下,以便我们对基本操作的理解。下面就看有关树的基本术语。现在先来看一下有关树的术语。树当中,它的基本单位是一个结点:什么叫结点呢:数据元素+若干指向子树的分支比如刚才我们举的那个例子,一个数据元素A+指向BCD的子树的分支,那就称一个结点。结点的度:结

6、点上指向分支的个数(在树上面每个结点的度可能是不一样的,比如我们分解到只含有一个根结点的子树时,它没有子树也没有分支,那它的度就是零。对于刚才的根结点,它的度就是3.)整个树的度;我们定义为:整个树当中所有结点的度的最大值。对于我们刚才的那棵树呢,这棵树的度呢,就是3,因为,结点最大的度是3.叶子结点:对树来说,分解到最后,对于子树来说就一个根节点,度为零的结点。(也就是只有一个根结点的子树。对于这样的一个结点,是没有子树的,它对于整个树来说,是很特殊的,叫做叶子结点。除了叶子结点,其他的结点的度都是大与零的。)反过来我们把它叫做分支结点:就是那些度大于零的结点。对于一棵树来说

7、呢,我们经常要谈到的是,根结点,叶子结点、分支结点。当然了,根结点也是分支结点的一种。树呢,我们看是一个层次的结构,那从根结点,沿着分支呢,能走到任何一个结点。从根到这个结点所经过的分支和结点,构成了一条路径。这条路径叫从根到这个结点的路径。在树里面还有一些术语,根我们族谱里面的术语差不多。因为,树这样的一个结构,最早就是从族谱中的来的。有孩子结点、双亲结点、前面我们讲到了根和子树根的关系,是父子关系,或者是双亲和孩子的关系。对于树根来说,是树根的孩子,那么反过来,这个跟对子树根来说,它是双

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。