树的建立以及节点删除出现的错误

描述

对于一间公司来说，它成立之时所做的第一件事恐怕就是任命CEO了。之后，CEO就会开始雇用员工，也会有员工离职去别的公司。假设公司中的每一个员工（包括 CEO在内）都可以直接雇用新的员工，而公司中的所有员工（包括CEO）也都可能会跳槽离开，则某公司在成立一段时间之后的的组织结构如图1

VonNeumann是公司的CEO，他直接雇用了两个人，分别是Tanenbaum和Dijkstra。在公司中，某员工的几个直接下属，他们的职位是由员工们的工龄决定的，在图中即表现为从从左至右职位越来越低，譬如Tanenbaum的职位就比Dijkstra要高。

当一个员工雇用了新的下属时，该下属在该员工雇佣的所有下属中，职位是最低的。假设VonNeumann又雇用了Shannon，则VonNeumann的三名下属职位从高到低分别是Tanenbaum、Dijkstra和Shannon。

当公司中的员工离职，则有两种情况。若他没有雇用任何下属，则他会被从公司的组织结构中拿掉。若他有直接的下属，则他的直接下属中职位较高的人，会升职并补上缺位。而该下属若也有下属，则他的下属中职位最高的，会补上他升值后空出的位子。以此类推，直到某个尚未雇用下属的员工升职。

假设图1中的Tanenbaum跳槽离开了，则Stallings会补上它的位置，而Knuth会补上Stallings的位置。图2图3分别展示了基于图1的两种的操作的结果。图2： VonNeumann雇用了Shannon。图3： Tanenbaum跳槽。

输入

输入的第一行是 CEO 的姓名。题目中所有的人名的长度都在2-20之间，且由大小写字母、数字和短线（减号）组成。每个名字都包含至少一个大写和一个小写字母。

在第一行后会有很多行内容，他们由如下的规则构成：

[老员工] hires [新员工]fire [老员工]print

[老员工] 是已经在公司工作的人的名字，而[新员工]是即将被雇用的员工的名字。以上三种规则组成的内容可能会按照任何顺序出现。但公司中会至少有一名员工（CEO），且公司的规模最大不会超过 1000 人。

输出

对于每一个打印命令，按照如下规则输出当前公司的结构信息：

每一行包含一个人名第一行是CEO的名字，从第一列开始对于图4形式的树

输出如下VonNeumann +Tanenbaum ++Stallings +++Knuth +++Hamming +++Huffman ++Silberschatz +Dijkstra*关于print的说明：从ceo开始打印，职位每降低一个等级（参考图片和输出），在名字前面加上一个加号。先序（自己->左枝->右枝）输出整棵树的节点。整棵树遍历完之后输出一行"---------"(具体长度看测试用例1)。输入以EOF结束

学长代码链接：1. 点击打开链接

                        2. 点击打开链接

这个题我花了很长时间，其实错误对我而言确实是不明显：

我的正确代码如下：

#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct node{ char name[20]; struct node * left; struct node * right; }NODE; NODE **Father=NULL; NODE **Delete=NULL; NODE *CEO=NULL; void print(NODE *ptr,int dep) { if(ptr!=NULL) { for(int i=0;i<dep;i++) printf("+"); printf("%s\n",ptr->name); } if(ptr->left!=NULL) print(ptr->left,dep+1); if(ptr->right!=NULL) print(ptr->right,dep); } void Build(NODE **ptr,char *s) { while((*ptr)!=NULL) ptr=&((*ptr)->right); (*ptr)=(NODE*)malloc(sizeof(NODE)); strcpy((*ptr)->name,s); (*ptr)->right=NULL; (*ptr)->left=NULL; } int Hire(NODE **ptr,char *p,char *q) { if(*ptr==NULL) return 0; if(strcmp(p,(*ptr)->name)==0) { if((*ptr)->left==NULL) { (*ptr)->left=(NODE*)malloc(sizeof(NODE)); (*ptr)->left->left=NULL; (*ptr)->left->right=NULL; strcpy((*ptr)->left->name,q); } else { Build(&((*ptr)->left),q); } return 1; } else { if((*ptr)->left!=NULL) Hire(&((*ptr)->left),p,q); if((*ptr)->right!=NULL) Hire(&((*ptr)->right),p,q); } return 0; } void Search(NODE **ptr, char *s) { if((*ptr)==NULL) return; if((*ptr)->left!=NULL&&strcmp((*ptr)->left->name,s)==0) { Father=ptr; Delete=&((*ptr)->left); return; } if((*ptr)->right!=NULL&&strcmp((*ptr)->right->name,s)==0) { Father=ptr; Delete=&((*ptr)->right); return; } if((*ptr)->left!=NULL) Search(&((*ptr)->left),s); if((*ptr)->right!=NULL) Search(&((*ptr)->right),s); return; } void Fire(char *s) { if(strcmp(s,CEO->name)==0 && CEO->left!=NULL) { char str[20]; strcpy(str,CEO->name); strcpy(CEO->name,CEO->left->name); strcpy(CEO->left->name,str); } else if(strcmp(s,CEO->name)==0 && CEO->right!=NULL) { char str[20]; strcpy(str,CEO->name); strcpy(CEO->name,CEO->right->name); strcpy(CEO->right->name,str); } else; Father=NULL; Delete=NULL; Search(&CEO,s); if(Father==NULL) { return; } else { if((*Father)->left== *Delete) { if((*Delete)->left==NULL) { (*Father)->left=(*Delete)->right; return; } else { char str[20]; strcpy(str,(*Delete)->name); strcpy((*Delete)->name,(*Delete)->left->name); strcpy((*Delete)->left->name,str); Fire(s); } } else if((*Father)->right== *Delete) { if((*Delete)->left==NULL) { (*Father)->right=(*Delete)->right; return; } else if((*Delete)->right==NULL) { (*Father)->right=(*Delete)->left; return; } else { char str[20]; strcpy(str,(*Delete)->name); strcpy((*Delete)->name,(*Delete)->left->name); strcpy((*Delete)->left->name,str); Fire(s); } } else; } } int main() { CEO=(NODE*)malloc(sizeof(NODE)); CEO->left=NULL; CEO->right=NULL; int input; char inputs[100],prase1[20],prase2[20],prase3[20]; scanf("%s",CEO->name); while(gets(inputs)!=NULL) { input=sscanf(inputs,"%[^ ] %[^ ] %[^ ]",prase1,prase2,prase3); if(input==1) { print(CEO,0); printf("------------------------------------------------------------\n"); } else if(input==2) Fire(prase2); else if(input==3) Hire(&CEO,prase1,prase3); } return 0; }

错误的地方是Fire函数，错误代码如下：

void Fire(char *s) { if(strcmp(s,CEO->name)==0 && CEO->left!=NULL) { char str[20]; strcpy(str,CEO->name); strcpy(CEO->name,CEO->left->name); strcpy(CEO->left->name,str); } else if(strcmp(s,CEO->name)==0 && CEO->right!=NULL) { char str[20]; strcpy(str,CEO->name); strcpy(CEO->name,CEO->right->name); strcpy(CEO->right->name,str); } else; Father=NULL; Delete=NULL; Search(&CEO,s); if(Father==NULL) { return; } else { if((*Father)->left== *Delete) // *1* { if((*Delete)->left==NULL) { (*Father)->left=(*Delete)->right; return; } else { char str[20]; strcpy(str,(*Delete)->name); strcpy((*Delete)->name,(*Delete)->left->name); strcpy((*Delete)->left->name,str); Fire(s); } } if((*Father)->right== *Delete) //错误的地方 { if((*Delete)->left==NULL) { (*Father)->right=(*Delete)->right; return; } else if((*Delete)->right==NULL) { (*Father)->right=(*Delete)->left; return; } else { char str[20]; strcpy(str,(*Delete)->name); strcpy((*Delete)->name,(*Delete)->left->name); strcpy((*Delete)->left->name,str); Fire(s); } } } }

错误之处在于程序进入*1*处的  if语句块中，将节点已经删除，但是程序依旧进行 *2* 处条件判断，但此时Delete指针所指的区域已经被删除，所以程序会提示内存访问冲突。

这件事提示我如果已经删除了一个节点，就不能再对它进行判断或者操作，否则会有内存访问冲突的错误。