数据结构(C语言版)6、树及二叉树.ppt

第6章 树和二叉树;6.树的逻辑定义和基本术语 6.1 树 6.2 二叉树 6.3 树、森林与二叉树的转换 6.3 哈夫曼树及其应用;6.1 树_TREE;图 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个结点的双亲所在的位置 { if (node0||node=T.n) return -1; else { printf(“parent elem is:%?\”,T. item[parent].info); return T.item[node].parent; } };item[0];2. 孩子表示法 孩子表示法主要描述的是结点的孩子关系。由于每个结点的孩子个数不定，所以利用链式存储结构更加适宜。举例：;图 6-3 孩子表示法结构示意图 显然ChildNode和T