ADT Tree{ 数据对象: D={1=<i<=n, n>=0, a(i)属于 ElemType类型} 数据关系: R={<a(i), a(j)> | a(i), a(j)属于 D, 1=<i<=n, 1=<j<=n, 其中每个元素只有一个前驱,可以有零个或多个后继,有且仅有一个元素没有前驱} 基本运算: InitTree(&t):初始化树:构造一棵空树 t。 ClearTree(&t):销毁树:释放树 t所占胡空间。 Parent(t):求元素 t的前驱。 Sons(t):求元素 t的所有后继。 }
这种存储结构是一种顺序存储结构,用一组连续空间存储树的所有节点,
同时在每个节点中设置一个伪指针指示双亲节点的位置。 结构体类型定义:
typedef struct{
ElemType data;
int parent;
} PTree[MaxSize];
这种存储结构中,每个节点不仅包含数据,还包括指向所有孩子节点的指针。 按照树的度设计节点的最大孩子节点个数。 结构体定义如下:
typedef struct node{
ElemType data;
struct node* sons[MAX_SONS];
} TSonNode;
这个存储结构为每个节点设计三个域:一个数据元素域、一个指向当前节点第一个字节点的指针域、一个指向该节点下一个兄弟节点的指针域。 结构体类型定义:
typedef struct tnode{
ElemType data;
struct tnode* first_son;
struct tnode* next_brother;
} TSBNode;
1、先根遍历
(1)访问根节点。
(2)按照从左到右的顺序先根遍历根节点的每一棵子树。
2、后根遍历
(1)按照从左到右的顺序后根遍历每一棵子树。
(2)访问根节点。