树的实现(存储结构) (1)数组实现方法(双亲表示法) 用数组存储树的结点信息,在每个结点中附设一个指示器指示其 双亲结点在数组中的位置。结构描述: #define maXsize 100 typedef struct PTNode[ TElemType data int parent i t PTNode typedef struc I PTNode nodes [mAXSIZe] 停止放映 int n: Ptree; 结点数据元素包含:数据、父结点位置 第16页
下一页 上一页 停止放映 第 16 页 树的实现(存储结构) ⚫ (1)数组实现方法（双亲表示法） 用数组存储树的结点信息，在每个结点中附设一个指示器指示其 双亲结点在数组中的位置。结构描述： #define MAXSIZE 100 typedef struct PTNode{ TElemType data； int parent ； } PTNode； typedef struc { PTNode nodes[MAXSIZE]； int n； } Ptree； 结点数据元素包含：数据、父结点位置
双亲表示法举例 结点序号 123456789 123456789 011223 55 6 方法特点: 停止放映 找根容易,找子结点难, 要遍历整个数组。 第17页
下一页 上一页 停止放映 第 17 页 双亲表示法举例 1 2 3 4 5 6 7 8 9 结点序号 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 0 1 1 2 2 3 5 5 5 方法特点： 找根容易，找子结点难， 要遍历整个数组
树的存储结构(二) (2)链表实现方式(孩子表示法) 把每个结点的孩子结点排列起来,组成一个线性表,且以单链 表作为存储结构,则n个结点有n个孩子链表。 ●结构描述为: typedef struct CTNode typedef struct t int child: CTBox nodes MAXSIZEI struct CTNode *next: int n, r: }米 Childptr; 6 Ctree: typedef struct i TElemType data 停止放映 Childptr firstchild CTBoX 结点元素:数据、指向第一个孩子的指针 孩子结点:孩子、指向下一个孩子的指针 第18页
下一页 上一页 停止放映 第 18 页 树的存储结构（二） ⚫ (2)链表实现方式（孩子表示法） 把每个结点的孩子结点排列起来，组成一个线性表，且以单链 表作为存储结构，则n个结点有n个孩子链表。 ⚫ 结构描述为： typedef struct CTNode{ typedef struct { int child； CTBox nodes[MAXSIZE]； struct CTNode *next： int n，r； } *Childptr； } Ctree； typedef struct { TElemType data； Childptr firstchild； } CTBox； 结点元素：数据、指向第一个孩子的指针 孩子结点：孩子、指向下一个孩子的指针
孩子表示法举例 2 3 123 4 6 456789 方法特点 停止放映 便于实现对孩子的操 作,却不便于对父亲 的操作 第19页
下一页 上一页 停止放映 第 19 页 孩子表示法举例 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 2 3 ^ 4 5 ^ 6 ^ ^ ^ ^ ^ ^ 7 8 9 ^ 方法特点: 便于实现对孩子的操 作,却不便于对父亲 的操作
树的存储结构(三) ●(3)二叉链表实现方式(孩子兄弟表 示法) 以二叉链表作为树的存储结构。链表中结 点的两个链域分别指向该结点的第一个孩 子结点和下一个兄弟结点。 结构描述为: typedef struct CSNode I ElemType data struct CSNode * kfirstchild 停止放映 米 netsibling; 3 CSNode, *k CSTree 第20页
下一页 上一页 停止放映 第 20 页 树的存储结构（三） ⚫ (3)二叉链表实现方式（孩子兄弟表 示法） 以二叉链表作为树的存储结构。链表中结 点的两个链域分别指向该结点的第一个孩 子结点和下一个兄弟结点。 结构描述为： typedef struct CSNode{ ElemType data； struct CSNode *firstchild ， *netsibling； } CSNode，* CSTree；