数据结构第5章树和二叉树

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

1、树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树、森林与二叉树的转换哈夫曼树第5章树和二叉树本章的主要内容是树的定义树：n（n≥0）个结点的有限集合。当n＝0时，称为空树；任意一棵非空树满足以下条件：⑴有且仅有一个特定的称为根的结点；⑵当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。5.1树的逻辑结构树的定义是采用递归方法(a)一棵树结构(b)一个非树结构(c)一个非树结构5.1树的逻辑结构树的定义ACBG

2、FEDHIACBGFDACBGFDE树的应用举例——文件结构5.1树的逻辑结构MyComputerC:D:E:etcWINDOWSProgramFilesPictureMusic…………………………………………树的基本术语结点的度：结点所拥有的子树的个数。树的度：树中各结点度的最大值。5.1树的逻辑结构CGBDEFKLHMIJA5.1树的逻辑结构叶子结点：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点。CGBDEFKLHMIJA树的基本术语孩子、双亲：树中某结点子树的根结点称为这个结点的孩

3、子结点，这个结点称为它孩子结点的双亲结点；兄弟：具有同一个双亲的孩子结点互称为兄弟。5.1树的逻辑结构CGBDEFKLHMIJA树的基本术语路径：如果树的结点序列n1,n2,…,nk有如下关系：结点ni是ni+1的双亲（1<=i

4、本术语结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。树的深度：树中所有结点的最大层数，也称高度。1层2层4层3层高度＝4CGBDEFKLHMIJC5.1树的逻辑结构树的基本术语CBDEFKLHJA71234568910层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。5.1树的逻辑结构树的基本术语有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。数据结构中讨论的一般都是有序树5.1树

5、的逻辑结构树的基本术语ACBGFEDACBGFEDCBDEFKLHJ森林：m(m≥0)棵互不相交的树的集合。5.1树的逻辑结构树的基本术语A同构：对两棵树，若通过对结点适当地重命名，就可以使这两棵树完全相等（结点对应相等，结点对应关系也相等），则称这两棵树同构。5.1树的逻辑结构树的基本术语ACBGFEDDAECFBG树结构和线性结构的比较线性结构树结构第一个数据元素根结点（只有一个）无前驱无双亲最后一个数据元素叶子结点(可以有多个)无后继无孩子其它数据元素其它结点一个前驱,一个后继一个双亲,多个孩子一对一一对多5

6、.1树的逻辑结构树的抽象数据类型定义ADTTreeData树是由一个根结点和若干棵子树构成，树中结点具有相同数据类型及层次关系OperationInitTree前置条件：树不存在输入：无功能：初始化一棵树输出：无后置条件：构造一个空树5.1树的逻辑结构DestroyTree前置条件：树已存在输入：无功能：销毁一棵树输出：无后置条件：释放该树占用的存储空间Root前置条件：树已存在输入：无功能：求树的根结点输出：树的根结点的信息后置条件：树保持不变树的抽象数据类型定义5.1树的逻辑结构Parent前置条件：树已存在输

7、入：结点x功能：求结点x的双亲输出：结点x的双亲的信息后置条件：树保持不变Depth前置条件：树已存在输入：无功能：求树的深度输出：树的深度后置条件：树保持不变树的抽象数据类型定义5.1树的逻辑结构PreOrder前置条件：树已存在输入：无功能：前序遍历树输出：树的前序遍历序列后置条件：树保持不变PostOrder前置条件：树已存在输入：无功能：后序遍历树输出：树的后序遍历序列后置条件：树保持不变endADT树的抽象数据类型定义5.1树的逻辑结构树的遍历操作树的遍历：从根结点出发，按照某种次序访问树中所有结点，使得

8、每个结点被访问一次且仅被访问一次。如何理解访问?抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。如何理解次序?树通常有前序（根）遍历、后序（根）遍历和层序（次）遍历三种方式。5.1树的逻辑结构树结构（非线性结构）→线性结构。遍历的实质?前序遍历树的前序遍历操作定义为：若树为空，则空操作返回；否则⑴访问根结点；⑵按照从左到右的顺序前序遍历根结点