이진트리삽입삭제문제...
글쓴이: dlwogh8046 / 작성시간: 화, 2014/11/25 - 2:57오전
중위순회로 삽입하고 후위순회로 삭제하려는데요..
코딩오류문제는 없음에도 불구하고 출력결과가 이상하게 나오네요..
어디쪽에 문제가 있는건가요?? ㅠㅠ 답답합니다;;
#include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <time.h> typedef struct TreeNode{ int key; struct TreeNode *left,*right; }TreeNode; void insertNode(TreeNode *root, int key) { TreeNode *p, *t; TreeNode *n,*succ; t=root; p=NULL; if(root) { insertNode(root->left ,key); while(t!=NULL) { if(key == t->key) return; p=t; if(key<p->key) t=p->left; else t=p->right; } n = (TreeNode*)malloc(sizeof(TreeNode)); if(n==NULL) return; n->key = key; n->left = n->right = NULL; if(p!=NULL) if(key<p->key) p->left=n; else p->right=n; else root = n; insertNode(root->right ,key); } } void deleteNode(TreeNode *root, int key) { TreeNode *p, *child, *succ, *succ_p, *t; p=NULL; t=root; if(root) { deleteNode(root->left,key); deleteNode(root->right,key); while(t!=NULL && t->key != key) { p=t; t=(key < p->key)? p->left : p->right; } if(t==NULL) { printf("찾고자하는 Key가 이진 트리에 없습니다."); return; } if((t->left==NULL)&&(t->right==NULL)) { if(p!=NULL){ if(p->left == t) p->left=NULL; else p->right=NULL; } else root=NULL; } else if((t->left==NULL)||(t->right=NULL)) { child=(t->left!=NULL) ? t->left:t->right; if(p!=NULL) { if(p->left==t) p->left=child; else p->right=child; } else root=child; } else { succ_p=t; succ=t->right; while(succ->left!=NULL) { succ_p=succ; succ=succ->left; } if(succ_p->left==succ) succ_p->left=succ->right; else succ_p->right=succ->right; t->key = succ->key; t=succ; } free(t); } } void displayNode(TreeNode *root) { if(root!=NULL) { displayNode(root->left); printf("%d ",root->key); displayNode(root->right); } } int main() { int *n,i,r; TreeNode *root = NULL; srand((unsigned)time(NULL)); n = (int*)malloc(100*sizeof(int)); for(i=0; i<100; i++) { r=(rand()%100)+1; n[i]=r; insertNode(root,n[i]); } displayNode(root); }
Forums:
insertnode 에서 노드를 찾는것을 2번
insertnode 에서 노드를 찾는것을 2번 수행하네요.
중위순회를 하면서 그 안에서 이진탐색.. 이것은 이진트리에서 삽입하는 방법이 아닙니다. 특별한 목적이 있는게 아니라면요.
노드를 찾는 것은 이진탐색 1번으로 수행하는 것입니다.
main을 보니 root가 초기값이 null인데 insertnode 에선 null일경우의 처리가 없습니다.
그 외에도 이상한? 코드들이 몇몇 보이는데,
소스가 나와있는 책을 보고 다시 한번 따라해보시길 바랍니다.
댓글 달기