不太清楚Loadtree这个方法是怎么实现的,进入到ADD方法的时候应该就因为没有父节点退出了呀,怎么成功的呢
下面有文件内容
/*
2021-10-15
树的实现
表达方式:双亲-长子-右兄弟表示法
存储结构:链式
要求不能存储data(关键字)相同的结点。
规定:访问的含义是printf
*/
#include <stdio.h>
#include <stdlib.h>
enum Status {NA, OK, EMPTY, NO_MEM, PARENT_NOT_EXIST, EXIST};
//既描述每个结点,也描述树
typedef struct _Node
{
int data;
int level;
struct _Node *parent;
struct _Node *first;
struct _Node *right;
}NODE,*PNODE;
PNODE Create(int value);
void Destroy(PNODE root);
void PreOrder(PNODE root);
void PostOrder(PNODE root);
void LevelOrder(PNODE root);
PNODE Find(PNODE root, int value);
//添加一个新的结点,作为其父结点的最小孩子
enum Status Add(PNODE root, int father, int child);
PNODE LoadTree(char *file);
int main()
{
PNODE Root, p;
enum Status r;
int ch;
int v, pv;
//Root = Create(0);
Root = LoadTree("tree.txt");
ch=-1;
while(ch)
{
printf("------------------\n");
printf("1 - Add\n");
printf("2 - Delete\n");
printf("3 - PreOrder\n");
printf("4 - PostOrder\n");
printf("5 - LevelOrder\n");
printf("6 = Find\n");
printf("0 - Exit\n");
printf("------------------\n");
printf("Select:");
flushall();
scanf("%d", &ch);
switch(ch)
{
case 6:
printf("输入要查找结点内容:");
scanf("%d", &v);
p = Find(Root, v);
if(p)
printf("找到!\n");
else
printf("未找到!\n");
break;
case 1:
printf("输入父结点内容:");
scanf("%d", &pv);
printf("输入新添加结点内容:");
scanf("%d", &v);
r = Add(Root, pv, v);
switch(r)
{
case OK:
printf("操作成功!\n");
break;
case NO_MEM:
printf("操作失败:创建结点时内存不足!\n");
break;
case PARENT_NOT_EXIST:
printf("操作失败:父结点%d不存在!\n", pv);
break;
case EMPTY:
printf("操作失败:树是空的!\n");
break;
}
break;
case 2:
/*
printf("输入要删除结点内容:");
scanf("%d", &v);
*/
break;
case 3:
PreOrder(Root);
printf("\n");
break;
case 4:
PostOrder(Root);
printf("\n");
break;
case 5:
LevelOrder(Root);
break;
}
}
Destroy(Root);
return 0;
}
PNODE Create(int value)
{
PNODE p = (PNODE)malloc(sizeof(NODE));
if(p)
{
p->data = value;
p->level = 1;
p->parent = p->first = p->right = NULL;
}
return p;
}
void Destroy(PNODE root)
{
}
/*
目前有问题,通过测试发现问题,再进行分析。
1)可以添加重复结点,改正
先“检查”要添加的结点是否存在
2)
*/
enum Status Add(PNODE root, int father, int child)
{
PNODE parent, p, q, pre;
enum Status status = NA;
if(root == NULL)
return EMPTY;
p = Find(root, child);
if(p)
return EXIST;
parent = Find(root, father);
if(!parent)
return PARENT_NOT_EXIST;
//parent是父
q = Create(child);
if(!q)
{
return NO_MEM;
}
q->parent = parent;
q->level = parent->level + 1;
//找到root的原最小孩子结点,pre指向
pre = NULL;
p = parent->first;
while(p)
{
pre = p;
p = p->right;
}
//令q为其最小的孩子
if(pre)
{
pre->right = q;
}
else
{
parent->first = q;
}
return OK;
}
/*
树的前序遍历操作定义为:
若树为空,则空操作返回;否则
⑴ 访问根结点;
⑵ 按照从左到右的顺序前序遍历根结点的每一棵子树。
*/
void PreOrder(PNODE root)
{
PNODE p;
if(root == NULL)
return;
printf("%d ", root->data);
p = root->first;
while(p)
{
PreOrder(p);
p = p->right;
}
}
void PostOrder(PNODE root)
{
PNODE p;
if(root == NULL)
return;
p = root->first;
while(p)
{
PostOrder(p);
p = p->right;
}
printf("%d ", root->data);
}
void LevelOrder(PNODE root)
{
//用数组模拟队列
PNODE q[100], p, pChild;
int front = 0, rear = 0;
if(!root)
return;
//1)入队不访问,出队访问
//2)入队访问,队时不访问
q[rear++] = root;
while(front != rear)
{
p = q[front++];
printf("%d ", p->data);
pChild = p->first;
while(pChild)
{
q[rear++] = pChild;
pChild = pChild->right;
}
}
printf("\n");
}
/*
找到,返回其指针;
否则,返回NULL
*/
PNODE Find(PNODE root, int value)
{
PNODE p, q;
if(root == NULL)
return NULL;
//根结点就是要查找的结点
if(root->data == value)
{
return root;
}
//根结点不是其父结点,root的每棵子树中查找
p = root->first;
q = NULL;
while(p)
{
q = Find(p, value);
if(q)
break;
p = p->right;
}
return q;
}
/*
从文件中读入结点及关系信息
*/
PNODE LoadTree(char *file)
{
PNODE p = NULL;
char s[128];
int pv, cv, k;
FILE *fp = fopen(file, "r");
if(fp)
{
while(!feof(fp))
{
fgets(s, 128, fp);
k = 0;
while(s[k] && s[k] != ',')
k++;
if(!s[k])
{
cv = atoi(s);
p = Create(cv);
}
else
{
pv = atoi(s);
cv = atoi(s + k + 1);
Add(p, pv, cv);
}
}
fclose(fp);
}
return p;
}
0
0,110000
0,130000
0,120000
110000,110100
110000,110200
130000,130100
130100,130102
130100,130105
130200,130201
130000,130600
130600,130601
130600,130602
130601,130601001
130601,130601002
0,610000
610000,610100
610000,610200
610100,610101
610100,610102
610100,610103