BiThrtree pre; if(!(Th= new biThrnode)exit(1);∥存储分配失败 Th->LTag= link: Th->RTag= Thread;∥建头结点 Th->Rchild= th ∥右指针回指 if(!BTTh- Lchild=Th;∥若二叉树空,则左指针回指 else i Th->Lchild= bt pre= Thead Unthreading(BI,pre);∥中序遍历进行中序线索化 pre> Rchild=Th;pre→>RIag= Thead;∥对中序序列中最后一个结点进行线索化 Th->Rchild= pre ∥建非空树的头结点的右线索 6-5-2.swf 树和森林的存储表示 1树的双亲表示法 .const MAX TREE SIZE 100 typedef struct{∥结点结构 ElemType data int parent;∥双亲位置域 3 PTNode; ° ypedef struct{∥树结构 PTNode nodes MAX TREE SIZE; intr,n;∥根的位置和结点数 I PTree 2树的孩子表示法 树的孩子链表存储表示 typedef struct CTNode{∥孩子结点 int child; struct CtNode *next *ChildPtr: typedef struct t ElemType data;∥结点的数据元素 ChildPtr firstchild;∥孩子链表头指针 CTBox typedef struct t CTBox nodes MAX TREE SIZEI; ntn,r;∥结点数和根结点的位置 3 CTree; 3树和森林的孩子兄弟表示法 存储表示 typedef struct CSNodel ElemType dat struct CSNode *firstchild, *nextsibling; 3 CSNode *CSTreeBiThrTree pre; if (!(Th = new BiThrNode)) exit (1); // 存储分配失败 Th->LTag = Link; Th->RTag =Thread; // 建头结点 Th->Rchild = Th; // 右指针回指 if (!BT) Th->Lchild = Th; // 若二叉树空，则左指针回指 else { Th->Lchild = BT; pre = Thead; InThreading(BT, pre); // 中序遍历进行中序线索化 pre->Rchild = Th; pre->RTag = Thead; // 对中序序列中最后一个结点进行线索化 Th->Rchild = pre; // 建非空树的头结点的"右线索" } } 6-5-2.swf 树和森林的存储表示 1 树的双亲表示法 •const MAX_TREE_SIZE = 100; •typedef struct { // 结点结构 ElemType data; int parent; // 双亲位置域 } PTNode; •typedef struct { // 树结构 PTNode nodes[MAX_TREE_SIZE]; int r, n; // 根的位置和结点数 } PTree; 2 树的孩子表示法 •树的孩子链表存储表示 typedef struct CTNode { // 孩子结点 int child; struct CTNode *next; } *ChildPtr; • typedef struct { ElemType data; // 结点的数据元素 ChildPtr firstchild; // 孩子链表头指针 } CTBox; • typedef struct { CTBox nodes[MAX_TREE_SIZE]; int n, r; // 结点数和根结点的位置 } CTree; 3 树和森林的孩子兄弟表示法 •存储表示 typedef struct CSNode{ ElemType data; struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree;