一道笔试题,由树的双亲关系生成树!
现在有一张表,其中存储了父子关系如
table parentChild
ParentID childID
3 7
2 6
2 5
2 4
1 3
1 2
,现需要由此表得到相映的树,请给出实现代码??
[解决办法]
// PCBCtr.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
#include <conio.h>
#include <stdlib.h>
#define Line 6
#define MadChlid 3
struct PCBT
{
int key;
PCBT* childID[MadChlid];
};
PCBT* head;
int TreeTable[Line][2];
int getHead()
{
int ThisHead = 0;
int i,j,k;
ThisHead = TreeTable[0][0];
for(i = 0;i<Line;i++){
if(ThisHead == TreeTable[i][1]){
ThisHead = TreeTable[i][0];
}
}
return ThisHead;
}
int FindChild(PCBT* NewPCB)
{
PCBT* child;
int i,j=0,k;
for(k=0;k<MadChlid;k++){
(NewPCB->childID)[k] = NULL;
}
for(i = 0;i<Line;i++){
if(TreeTable[i][0] == NewPCB->key){
child = (PCBT*)malloc(sizeof(PCBT));
child->key = TreeTable[i][1];
(NewPCB->childID)[j] = child;
FindChild(child);
j++;
}
}
return 0;
}
int main(int argc, char* argv[])
{
PCBT* NewPCB;
TreeTable[0][0] = 3;
TreeTable[0][1] = 7;
TreeTable[1][0] = 2;
TreeTable[1][1] = 6;
TreeTable[2][0] = 2;
TreeTable[2][1] = 5;
TreeTable[3][0] = 2;
TreeTable[3][1] = 4;
TreeTable[4][0] = 1;
TreeTable[4][1] = 3;
TreeTable[5][0] = 1;
TreeTable[5][1] = 2;
head = NULL;
NewPCB = (PCBT*)malloc(sizeof(PCBT));
NewPCB->key = getHead();
head = NewPCB;
FindChild(head);
return 0;
}
不知道是不是这样,我用很笨的方法,从根接点开始递归
不过我觉得从根接点开始递归可能更好.
[解决办法]
怎么发不了贴?
[解决办法]
C代码:
#define MAX_TREE_SIZE 100
typedef struct PTNode{//结点结构
int data; //自己可以再选其它的类型
int parent; //双亲位置域
}PTNode;
typedef struct(//树结构
PTNode nodes[MAX_TREE_SIZE];
int r,n;//根的位置和结点数
)PTree;
只是树结构选择和上面不同,其它操作相似