7树和森林.ppt.ppt

第7章 树和森林;第7章 树和森林; 7.1 树的定义和基本术语;(b)一般的树;树还可有其它的表示形式。;树的相关术语 结点　 结点的度　 树的度　 叶子结点 双亲结点 孩子结点 兄弟结点 祖先结点 子孙结点　 树的深度（高度） 路径 路径长度;将树中结点的各子树看成从左至右有次序的，称该树为有序树，否则称为无序树。 有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。 森林(Forest)是m(m≥0)棵互不相交的树的集合。子树的集合即为森林。;第7章 树和森林;7.2 树的操作与存储;7.2.2 树的存储结构 在大量的应用中，可用多种形式的存储结构来表示树。这里介绍三种常用的结构。 一、双亲表示法 用数组存储树的结点，每个结点中存储其父结点的位置： #define MAXNODE 100 typedef struct PTNode { DataType data； int parent； //双亲位置域 }PTNodeType； PTNodeType t[MAXNODE];;例如，下图展示一棵树双亲表示法存储结构。 ;利用了每个结点（除根以外）只有唯一的双亲的性质。 PARENT(T，x)：可以在常量时间内实现。 ROOT(x)：反复调用PARENT操作，直到遇见无双亲的结点时，便找到了树的根。 但是，求结点的孩子时需要遍历整个结构。;二、孩子表示法 多重链表：每个结点有多个指针域，每个指针指向一棵子树的根结点。 两种格式：