数据结构(C语言版)树和叉树.pptVIP

第6章 树和二叉树 本章中主要介绍下列内容： 树的逻辑定义和基本术语 二叉树的逻辑定义及存储结构 二叉树的基本操作算法（*遍历算法） 树、森林和二叉树的转换 哈夫曼树及其应用 6.树的逻辑定义和基本术语 6.1 树 6.2 二叉树 6.3 树、森林与二叉树的转换 6.3 哈夫曼树及其应用 6.1 树_TREE 6.1.1 树的定义和基本运算 mathematical concept-Abstract data type-Data structure-Implementation-Application 1. 定义:树是一种常用的非线性结构。我们可以这样定义：树是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，...，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归。 图 6-1 结点(node/vertex) 数据元素的内容及其指向其子树根的分支统称为结点。 结点的度(degree) 结点的分支数。 终端结点（叶子leaf） 度为0的结点。 非终端结点 度不为0的结点。 结点的层次(level) 树中根结点的层次为1，根结点子树的根为第2层，以此类推。 树的度 树中所有结点度的最大值。 树的深度depth 树中所有结点层次的最大值。 有序树(ordered tree)、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。 森林(forest) 是m（m≥0）棵互不相交的树的集合。 在树结构中，结点之间的关系又可以用家族关系描述，定义如下： 孩子child、双亲parent 结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。 结点的子孙 descendant 以某结点为根的子树中的所有结点都被称为是该结点的子孙。 结点的祖先ancestor 从根结点到该结点路径上的所有结点。 兄弟sibling 同一个双亲的孩子之间互为兄弟。 堂兄弟 双亲在同一层的结点互为堂兄弟。 2. 树的基本运算 常用操作： （1） 构造一个树 CreateTree (T) （2）清空以T为根的树 ClearTree(T) （3）判断树是否为空 TreeEmpty(T) （4）获取给定结点的第i个孩子 Child(T,node,i) （5）获取给定结点的双亲 Parent(T,node) （6）遍历树Traverse(T) 对树遍历的主要目的是将非线性结构通过遍历过程线性化，即获得一个线性序列。树的遍历顺序有两种，一种是先序遍历，即先访问根结点，然后再依次用同样的方法访问每棵子树；另一种是后序遍历，即先依 6.1.2 树的存储结构 应用一段连续的存储空间存储树，要求存储结构能表示逻辑结构，即满足树的定义，即同一结点有多个不同的后继，或多个结点具有同一前驱，并且不存在相交的子树。 1. 双亲表示法: 树的双亲表示法主要描述的是结点的双亲关系，不但要存储树中结点数据元素本身的值，而且要存储结点双亲所在的位置。如图2所示： 图 6-2 根结点A存储于第0位置，无双亲，故双亲的存储位置标志设置为-1,结点B C D依次存储于1 2 3位置，其双亲所在位置是0;……. 类型定义： #define MAX_TREE_NODE_SIZE 100 typedef struct ParentNode{ EelemType info;//树中数据元素数据类型 int parent;//其双亲结点的存储位置 }; typedef struct ParentTree{ ParentNode item[MAX_TREE_NODE_SIZE]; int n; //树中当前的结点数目 }; 这种存储方法的特点是寻找结点的双亲很容易，但寻找结点的孩子比较困难。 算法实现举例,求双亲结点所在位置： int Parent(ParentTree T,int node) //返回第node个结点的双亲所在的位置