及其双亲表存储结构。
// c6-4.h 树的双亲表存储结构(见图6.27)#define MAX_TREE_SIZE 100struct PTNode{ TElemType data; int parent; // 双亲位置域};struct PTree{ PTNode nodes[MAX_TREE_SIZE]; int n; // 结点数}; // bo6-4.cpp 树的双亲表存储(存储结构由c6-4.h 定义)的基本操作(14 个)#define ClearTree InitTree // 二者操作相同#define DestroyTree InitTree // 二者操作相同void InitTree(PTree &T){ // 操作结果：构造空树T T.n=0;}typedef struct{ int num; TElemType name;}QElemType; // 定义队列元素类型#include"c3-2.h" // 定义LinkQueue类型(链队列)#include"bo3-2.cpp" // LinkQueue类型的基本操作void CreateTree(PTree &T){ // 操作结果：构造树T LinkQueue q; QElemType p,qq; int i=1,j,l; char c[MAX_TREE_SIZE]; // 临时存放孩子结点数组 InitQueue(q); // 初始化队列 printf("请输入根结点(字符型,空格为空): "); scanf("%c%*c",&T.nodes[0].data); // 根结点序号为0，%*c吃掉回车符 if(T.nodes[0].data!=Nil) // 非空树 { T.nodes[0].parent=-1; // 根结点无双亲 qq.name=T.nodes[0].data; qq.num=0; EnQueue(q,qq); // 入队此结点 while(i MAX_TREE_SIZE) { printf("结点数超过数组容量\n"); exit(OVERFLOW); } T.n=i; } else T.n=0;}Status TreeEmpty(PTree T){ // 初始条件：树T存在。操作结果：若T为空树，则返回TRUE；否则返回FALSE if(T.n) return FALSE; else return TRUE;}int TreeDepth(PTree T){ // 初始条件：树T存在。操作结果：返回T的深度 int k,m,def,max=0; for(k=0;k =0) // 有双亲 printf(" %c",Value(T,T.nodes[i].parent)); // 双亲 printf("\n"); }}Status InsertChild(PTree &T,TElemType p,int i,PTree c){ // 初始条件：树T存在，p是T中某个结点，1≤i≤p所指结点的度+1，非空树c与T不相交 // 操作结果：插入c为T中p结点的第i棵子树 int j,k,l,f=1,n=0; // 设交换标志f的初值为1，p的孩子数n的初值为0 PTNode t; if(!TreeEmpty(T)) // T不空 { for(j=0;j 1) // c不是p的第1棵子树 { for(k=j+1;k =l;k--) // 依次将序号l以后的结点向后移c.n个位置 { T.nodes[k+c.n]=T.nodes[k]; if(T.nodes[k].parent>=l) T.nodes[k+c.n].parent+=c.n; } for(k=0;k T.nodes[j+1].parent) { // 如果结点j的双亲排在结点j+1的双亲之后(树没有按层序排列)，交换两结点 t=T.nodes[j]; T.nodes[j]=T.nodes[j+1]; T.nodes[j+1]=t; f=1; // 交换标志置1 for(k=j;k j) T.nodes[k-1].parent--; } j--; } T.n-=n; // n为待删除结点数 }}void TraverseTree(PTree T,void(*Visit)(TElemType)){ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数 // 操作结果：层序遍历树T，对每个结点调用函数Visit一次且仅一次 int i; for(i=0;i // main6-4.cpp 检验bo6-4.cpp的主程序#include"c1.h"typedef char TElemType;TElemType Nil=' '; // 以空格符为空#include"c6-4.h"#include"bo6-4.cpp"void vi(TElemType c){ printf("%c ",c);}void main(){ int i; PTree T,p; TElemType e,e1; InitTree(T); printf("构造空树后,树空否? %d(1:是0:否) 树根为%c 树的深度为d\n",TreeEmpty(T),Root(T), TreeDepth(T)); CreateTree(T); printf("构造树T后,树空否? %d(1:是0:否) 树根为%c 树的深度为d\n",TreeEmpty(T),Root(T), TreeDepth(T)); printf("层序遍历树T:\n"); TraverseTree(T,vi); printf("请输入待修改的结点的值新值: "); scanf("%c%*c%c%*c",&e,&e1); Assign(T,e,e1); printf("层序遍历修改后的树T:\n"); TraverseTree(T,vi); printf("%c的双亲是%c,长子是%c,下一个兄弟是c\n",e1,Parent(T,e1),LeftChild(T,e1), RightSibling(T,e1)); printf("建立树p:\n"); InitTree(p); CreateTree(p); printf("层序遍历树p:\n"); TraverseTree(p,vi); printf("将树p插到树T中，请输入T中p的双亲结点子树序号: "); scanf("%c%d%*c",&e,&i); InsertChild(T,e,i,p); Print(T); printf("删除树T中结点e的第i棵子树，请输入e i: "); scanf("%c%d",&e,&i); DeleteChild(T,e,i); Print(T);} 代码的运行结果： 构造空树后,树空否? 1(1:是0:否) 树根为树的深度为0 请输入根结点(字符型,空格为空): R 请按长幼顺序输入结点R的所有孩子: ABC 请按长幼顺序输入结点A的所有孩子: DE 请按长幼顺序输入结点B的所有孩子: 请按长幼顺序输入结点C的所有孩子: F 请按长幼顺序输入结点D的所有孩子: 请按长幼顺序输入结点E的所有孩子: 请按长幼顺序输入结点F的所有孩子: GHK 请按长幼顺序输入结点G的所有孩子: 请按长幼顺序输入结点H的所有孩子: 请按长幼顺序输入结点K的所有孩子: 构造树T后,树空否? 0(1:是0:否) 树根为R 树的深度为4 层序遍历树T:(见图628(a)) R A B C D E F G H K 请输入待修改的结点的值新值: D d 层序遍历修改后的树T: R A B C d E F G H K d的双亲是A,长子是,下一个兄弟是E 建立树p: 请输入根结点(字符型,空格为空): f 请按长幼顺序输入结点f的所有孩子: ghk 请按长幼顺序输入结点g的所有孩子: 请按长幼顺序输入结点h的所有孩子: 请按长幼顺序输入结点k的所有孩子: 层序遍历树p:(见图629) f g h k
将树p插到树T中，请输入T中p的双亲结点子树序号: R 3(见图630) 结点个数=14 结点双亲 RA R B R f R C R d A E A g f h f k f
F C G F H F K F 删除树T中结点e的第i棵子树，请输入e i: C 1(见图631) 结点个数=10 结点双亲 RA R B R f R C R d A E A g f h f k f
