数据结构CC版第6章 学习二叉树.pptx

《数据结构CC版第6章 学习二叉树.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构（C语言版）项目六学习二叉树树结构是指具有分支关系的结构。树状结构特别是二叉树应用非常广泛，在文件系统、编译系统、目录组织等方面更加突出。在本项目中，通过2个工作任务，向读者展示二叉树的概述、计算方法以及实际应用。目录任务一计算二叉树的前序遍历序列任务二使用Huffman树编写C语言程序计算二叉树的前序遍历序列准备知识计算二叉树的前序遍历序列树结构树形结构的种类树的相关术语二叉树的概述满二叉树和完全二叉树二叉树的性质二叉树的抽象数据类型和基本操作顺序存储结构链式存储结构二叉树的遍历线索二叉

2、树的概述中序线索二叉树的构造和遍历1.树结构1.树结构现实生活中树的例子很多，如家庭成员关系、单位人员组织机构等都是树结构。例如，一个家庭的成员关系如下：王奶奶（用A表示）有三个儿子，分别用B、C、D表示；大儿子B有两个孩子，分别用E、F表示；二儿子C有一个孩子，用G表示；三儿子D有三个孩子，分别用H、I、J表示；王奶奶的孙子E有两个孩子，分别用K、L表示；另一个孙子H也有一个孩子M。1.树结构王奶奶的家庭关系就是树结构，如下图所示为这棵树的结构。某家庭关系树2.树形结构的种类2.树形结构的种类树

3、形结构的种类有以下几种：（1）无序树（2）有序树（3）二叉树（4）霍夫曼树（5）B树（B-tree）（6）森林（forest）3.树的相关术语3.树的相关术语树的相关术语有结点（node）、结点的度（degree）、树的度、边（edge）、叶结点或终端结点（leaf）、非终端结点或分支结点（branchnode）、双亲结点或父结点、孩子结点或子结点、兄弟结点（sibling）、堂兄弟结点、结点的祖先、子孙（descendant）、结点的层序（level）、树的或深度（depth）。4.二叉树的概述

4、4.二叉树的概述二叉树(BinaryTree)是n(n≥0)个结点的有限集合，二叉树是每个结点最多有两个子树的树结构，通常子树被称作“左子树”（leftsubtree）和“右子树”（rightsubtree）。二叉树简记为BT，是一个二元组。拓展提高：从这个定义可以看出，这个集合或是空的，或是由特殊的称为根结点以及两个不相交的左子树和右子树构成。很明显这是递归定义，由此不难看出：二叉树存在空树，每个结点可以有0、1或2个孩子。4.二叉树的概述二叉树是有序树，它的左子树和右子树有严格的次序，若将其左

5、、右子树颠倒，就成为另外一棵不同的二叉树。因此，下左图、和下右图所示是不同的二叉树。二叉树的基本形态二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k-1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。5.满二叉树和完全二叉树5.满二叉树和完全二叉树满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树，如下左图所示。由定义可知，对于深度为k的满二叉树的结点个数为2k-1。完全二叉树：深度为

6、k，有n个结点的二叉树当且仅当其每一个结点都与深度为k，有n个结点的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树，如下右图所示。完全二叉树的特点是叶子结点只可能出现在层序最大的两层上，并且某个结点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。5.满二叉树和完全二叉树满二叉树与完全二叉树6.二叉树的性质6.二叉树的性质性质1：在非空二叉树中，第i层结点数最多为2i-1个(i≥1)。性质2：深度为k的二叉树结点总数最多为2k-1个。性质3：具有n个结点的完全二叉树的深度k为lo

7、g2n+1。性质4：任一棵二叉树，度为0的结点比度为2的结点多一个。如果叶结点数为n0，度为2的结点数为n2，则n0=n2+1。性质5：对于一棵具有n个结点的完全二叉树，按照层序自上而下，自左而右的顺序给每个结点编号，则对任意编号为i(1≤i≤n)的结点有下列性质：7.二叉树的抽象数据类型和基本操作7.二叉树的抽象数据类型和基本操作二叉树的抽象数据类型定义如下：ADTBinary_Tree{（1）数据对象D：一个集合，该集合中的所有元素具有相同的特性。（2）数据关系R：若D为空集，或D中仅含有一个

8、数据元素，则R＝{Φ}；否则R={H}，H是如下的二元关系。a.在D中存在唯一的称为根的结点root，它在关系H下没有前驱。b.除root以外，D中其余结点存在m(0≤m≤2)个不相交的划分，每个划分都是一棵二叉树，称为根的子树。（3）二叉树的基本操作。}7.二叉树的抽象数据类型和基本操作二叉树的基本操作包括：（1）初始化空二叉树：建立一棵以BT为根，LBT为左子树，RBT为右子树的二叉树。（2）构建二叉树：根据二叉树广义表字符串创建一个二叉树（3）判断是否为空：判断二叉树是否为空