数据结构实用教程(c语言版)树.ppt

该【数据结构实用教程(c语言版)树 】是由【fanluqian】上传分享，文档一共【84】页，该文档可以免费在线阅读，需要了解更多关于【数据结构实用教程(c语言版)树 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。绿色生态环境环保主题教育
单击此处添加副标题
数据结构实用教程（C语言版）
中国水利水电出版社
第5章 树
单击此处添加副标题
本章中主要介绍下列内容：
树的逻辑定义和存储结构
二叉树的逻辑定义、存储结构
二叉树的基本操作算法
树和二叉树的转换
哈夫曼树及其应用
01
树
单击此处添加正文
03
二叉树的建立和遍历
单击此处添加正文
05
哈夫曼树
单击此处添加正文
02
二叉树
单击此处添加正文
04
树、森林与二叉树的转换
单击此处添加正文
06
本章小结
单击此处添加正文
本章目录
CONTENT
01
02
03
04
树的定义
树的表示方法
树的基本术语
树的存储结构
树
树的定义
树是n（n≥0）个结点的有限集合。当n=0时称为空树。当n>0时，是非空树，它满足以下两个条件：
有且仅有一个称为根的结点；
其余结点分为m（m≥0）个互不相交的非空集合T1，T2，…，Tm，其中每个集合本身又是一棵树，称为根的子树。
树可用二元组来表示。其中，D为结点集合，R为边的集合。一棵树T如图5-1所示，则它的二元组表示方法为：
T=（D,R）
D={A,B,C,D,E,F,G,H}
R={<A,B>,<A,C>,<A,D>,<B,E>,<C,F>,<C,G>,<D,H>,<F,I>}
图5-1 树的逻辑结构图
树的二元组表示法
树的表示方法
树的逻辑结构表示有树形表示法，文氏图表示法，凹入表示法和广义表表示法等。
1．树形表示法
这是树的最基本的表示，使用一棵倒置的树表示树结构。图5-1就是采用这种方法。
2．文氏表示法
使用集合以及集合的包含关系描述树结构。图5-2（a）就是图5-1的树的文氏图表示法。
3．凹入表示法
使用线段的伸缩关系描述树的结构。图5-2（b）就是图5-1的树的凹入表示法。
4．广义表表示法
将树的根结点写在括号的左边，除根结点外的其余结点写在括号内并用逗号间隔来描述树的结构。图5-2（c）就是图5-1的树的广义表表示法。
文氏图表示法 (b)凹入图表示法 (c)广义表表示法
图5-2 树的其它表示方法
树的三种表示方法
结点的度
结点所拥有的分支数目或后继结点个数称为该结点的度（Degree）。例如图5-1所示的树中结点A的度为3，结点C的度为2，结点E的度为0。
叶子（终端结点）
度为零的结点称为叶子结点。例如图5-1所示的树中结点E、G、H、I为叶子结点。
56%
Option 2
47%
Option 4
结点
树的度
树中各结点度的最大值称为该树的度。例如图5-1所示的树的度为3。
树的结点包含一个数据元素及若干指向其子树的分支。
30%
Option 3
23%
Option 1
树的基本术语
01
分支结点
度不为零的结点称为分支结点。例如图5-1所示的树中的A、B、C、D、F都是分支结点。
02
孩子结点
一个结点的后继称为该结点的孩子结点。例如图5-1所示的树中A的孩子结点为B、C、D。
03
双亲结点
一个结点称其为其后继结点的双亲结点。例如图5-1所示的树中A是B、C、D的双亲结点，C是F、G的双亲。
04
兄弟结点
同一双亲结点下的孩子结点互称为兄弟结点。例如图5-1所示的树中B、C、D互为兄弟结点， F、G互为兄弟结点，但不同双亲的两个同层结点不互为兄弟结点，如G和H不互为兄弟结点。
树的基本术语