数据结构c语言问题,在删除树节点出错,求帮助啊
程序代码:
#include<stdio.h> #include<stdlib.h> #define N 10 typedef struct tree{ int data; struct tree *left; struct tree *right; }Tree; typedef struct queue{ Tree *store[N]; int f; int r; }Queue; void init_queue(Queue *q) { q->f=0; q->r=0; } void inqueue(Queue *s,Tree *value) { if((s->r+1)%(N)==s->f) { printf("error\n"); return; } s->store[s->r]=value; s->r=(s->r+1)%(N); } Tree *dequeue(Queue *s) { Tree *temp; if(s->r==s->f) return NULL; temp=s->store[s->f]; s->f=(s->f+1)%(N); return temp; } void init_array(int a[],int n) { int i; for(i=0;i<n;i++) a[i]=i; } Tree *init_tree(int value) { Tree *newnode=(Tree *)malloc(sizeof(Tree)); newnode->data=value; newnode->right=NULL; newnode->left=NULL; return newnode; } int is_empty(Queue *q) { if(q->f==q->r) return 1; else return 0; } /*void insert_tree(Tree *root,int value) { Tree *subtree=(Tree *)malloc(sizeof(Tree)); subtree->data=value; subtree->right=NULL; subtree->left=NULL; while(root->right&&root->data<value) root=root->right; while(root->left&&root->data>value) root=root->left; if(root->data<value) root->right=subtree; if(root->data>value) root->left=subtree; if(root->data=value) return; }*/ void insert_tree(Tree *root,int value) { while(root) { if(root->data==value) return; if(root->data>value) { if(root->left) root=root->left; else { Tree *t=init_tree(value); root->left=t; return; } } else//(root->data<value) { if(root->right) root=root->right; else { Tree *t=init_tree(value); root->right=t; return; } } } } void inorder(Tree *root) { if(root==NULL) return; inorder(root->left); printf("%d\n",root->data); inorder(root->right); } int tree_lenght(Tree *root) { int lenght; if(root==NULL) return 0; else { int left_lenght=tree_lenght(root->left); int right_lenght=tree_lenght(root->right); lenght=((left_lenght>=right_lenght)?left_lenght:right_lenght)+1; return lenght; } } void levelorder(Tree *root) { Tree *t; Queue *q=(Queue *)malloc(sizeof(Queue)); init_queue(q); inqueue(q,root); while(q->f!=q->r) { t=dequeue(q); printf("%d\n",t->data); if(t->left) inqueue(q,t->left); if(t->right) inqueue(q,t->right); } } Tree *search_tree(Tree *root,int value) { if(root==NULL) return NULL; if(root->data==value) return root; if(root->data>value) return search_tree(root->left,value); else return search_tree(root->right,value); } Tree *search_max(Tree *root) { Tree *temp; if(!root->right&&!root->left) return NULL; if(!root->right&&root->left) { temp=root->left; root->left=NULL; return temp; } if(root->right&&!root->left) { temp=root->right; root->right=NULL; return temp; } if(root->right&&root->left&&root->left->right==NULL) { temp=root->right; root->right=NULL; return temp; } root=root->left; while(root->right->right) root=root->right; temp=root->right; root->right=NULL; return temp; } Tree *search(Tree *root,int value) { if(root==NULL) return NULL; if(root->data==NULL) return NULL; while(1) { if(root->data>value) { if(root->left==NULL) return NULL; else if(root->left->data==value) return root; else root=root->left; } if(root->data<value) { if(root->right==NULL) return NULL; else if(root->right->data==value) return root; else root=root->right; } } } int extent(Tree *root) { if(!root->right&&root->left) return 0; if(root->right&&!root->left) return 1; if(root->right&&root->left) return 2; } void delet_tree(Tree *root,int value) { Tree *s; Tree *node; Tree *temp; if(!search(root,value)) return ; node=search(root,value); if(node->left->data==value) { temp=search_max(node->left); if(!temp) { s=node->left; node->left=NULL; free(s); } else { s=node->left; node->left=temp; if(extent(s)==0) { temp->left=s->left; } if(extent(s)==1) { temp->right=s->right; } if(extent(s)==2) { temp->left=s->left; temp->right=s->right; } free(s); } } if(node->right->data==value) { temp=search_max(node->right); if(!temp) { s=node->right; node->right=NULL; free(s); } else { s=node->right; node->right=temp; if(extent(s)==0) { temp->right=s->right; } if(extent(s)==1) { temp->left=s->left; } if(extent(s)==2) { temp->left=s->left; temp->right=s->right; } free(s); } } } void main() { int i; Tree *root=(Tree *)malloc(sizeof(Tree)); root->data=N/2; root->right=NULL; root->left=NULL; for(i=0;i<N;i++) insert_tree(root,random()%N); //levelorder(root); delet_tree(root,7); levelorder(root); }