数据结构课件——二叉树(c语言).ppt

《数据结构课件——二叉树(c语言).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树与线索二叉树6.4树和森林6.5哈夫曼树及其应用2本章重点讨论树与二叉树的概念、性质、存储结构及其各种运算，并研究一般树、森林和二叉树的转换关系；此外，作为树形结构的应用，介绍了哈夫曼树及其哈夫曼编码。3树和图是两种应用极为广泛的数据结构，也是这门课程的重点。它们的特点在于非线性。树是一种以分支关系定义的层次结构。在这种结构中，每个数据元素至多只有一个前趋，但可以有多个后继；数据元素之间的关系是一对多的层次关系。树形结构主要用于描述客观世界中具有层次

2、结构的数据关系。6.1树的定义和基本术语4树型结构在客观世界中广泛存在并在多个领域中已有重要应用：1.树的应用(1)首先，我们来看一个家族树6.1.1树的概念5(2)高校管理组织机构也可用树来形象表示:6(3)树的其它方面应用:在计算机的编译程序中，可用树来表示源程序的语法结构在数据库系统中，树形结构也是信息的重要组织形式之一在通信领域，利用最优树（哈夫曼）编码，可以大大提高信道利用率，缩短信息传输时间，降低成本。72.树的定义树(Tree)是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：(1

3、)有且仅有一个特定的称为根(Root)的结点；(2)其余的结点可分为m(m≥0)个互不相交的子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subree)。树的定义是一个递归的定义，它反映了树的固有特性，即一棵树由若干棵子树构成，且各子树间互不相交，而每棵子树又由若干棵更小的子树构成。8例如下图中，（a）是只有一个根结点的树；（b）是有8个结点的一般树，其中A是根，其余结点分成三个互不相交的子集：T1={B、E、F}，T2={C}，T3={D、G、H}，而且它们都是A的子树，且其本身也是一棵树。

4、9有序树和无序树：若将树中每个结点的各子树看成是从左至右有序且不能交换，则称该树为有序树，否则称为无序树。图6.4给出了两棵不同的有序树。图6.4两棵不同的有序树10如上所述，树型图表示是树结构的主要表示方法。树还可有其他的表示形式，如下图（a）为集合表示法或范氏图法，（b）为凹入表示法或缩格法，（c）为广义表表示法或嵌套括弧法等。6.1.2树的表示116.1.3树结构的基本术语树的结点：是指一个数据元素及若干指向其子树的分支，通常用一个结构体或记录来描述，在树形表示中用一个圆圈及短线表示。结点的度：树中的一个结点拥有

5、的子树数称为该结点的度(Degree)。如图A的度为3；B的度为2；F的度为0。结点12叶子或终端结点：是指度为零的结点。如图叶子结点有：E、F、C、G、H。分支结点或非终端结点：是指度不为零的结点。如图中的分支结点有：B、D。树的度：该树中各结点的度的最大值。如图中树的度为3。13结点的层次：从根开始定义，根为第一层，根的孩子为第二层，以此类推，即设根结点的层数为1，其余结点的层数等于其双亲结点的层数加1。若某结点在第i层，则其孩子结点就在第i+1层。树的深度或高度：是指树中结点的最大层次数。该树的深度（高度）为3。

6、第二层第三层第一层14有时，在实际应用中也引用家族树中的一些习惯用语来描述树，如孩子、双亲、祖先、子孙和兄弟等。如将某结点的子树的根称为该结点的孩子，相应地，将该结点称为孩子的双亲；同一个双亲的孩子之间互称为兄弟，其双亲在同一层次上的称为堂兄弟等等。祖先则是从根结点到该结点所经过分支上的所有结点，而以某结点作为根的子树中任一个结点都称为该结点的子孙。15路径：若树中存在一个结点序列k1，k2，…，kj，使得ki是ki＋1的双亲（1≤i

7、的数目。在树形表示中，路径表示从k1出发自上而下地通过k2，k3，…，kj各结点。如图：A，B，E是一条路径，其长度为2；A，C是一条路径，其长度为1。16森林：是指m（m≥0）棵互不相交的树的集合。如图是由四棵树构成的森林。17二叉树（BinaryTree）是另一种重要的树型结构，在实际应用中具有重要的意义。本节将详细地讨论二叉树的定义、重要性质、存储方式、运算及其应用。6.2二叉树186.2.1二叉树的定义与基本操作1、二叉树定义二叉树是n（≥0）个结点的有限集合，这个集合可以是空集合，或者由一个根结点和两棵互不相

8、交的分别称为根的左子树和右子树的二叉树组成。显然，由定义可知，二叉树具有递归性质，它的特点是每个结点至多只有二棵子树即二叉树中任何结点的度数不大于2，而且，二叉树的子树有左右之分，其次序不能任意颠倒。应该指出的是，二叉树与树是两个不同的概念，它不19A图6.5二叉树与度为2的一般树的区别举例BCD(a)二叉树1ABCD(b)二叉树