알고리즘 런타임에러 질문입니다.

Question

※ 조건: 종료(q) 명령 때까지 삽입(i), 탐색(s), 삭제(d), 인쇄(p), 명령을 반복 입력받아 수행한다.i <키> : 입력 <키>에 대한 노드 생성 및 트리에 삽입d <키> : 입력 <키>가 트리에 존재하면 해당 노드 삭제 후 삭제된 키를 출력, 없으면 ‘X’를 출력s <키> : 입력 <키>가 트리에 존재하면 해당 키를 출력, 없으면 ‘X’를 출력p : 현재 트리를 전위순회로 인쇄q : 프로그램 종료1. 트리 노드는 아래의 구조체를 이용하여 구현한다.lChildparentrChildkeynode 2. 전위순회는 루트 노드를 먼저 방문하고, 왼쪽 부트리, 오른쪽 부트리 순서로 순회한다.3. 트리 노드 삭제 시, 삭제할 노드 w의 자식 중 하나(z이라 하자)라도 잎인 경우는 아래 그림 <삭제 예시 1>처럼 w를 z과 함께 삭제하고, 반대쪽 자식 노드(그림에서 8을 저장한 노드)가 w를 계승한다 – reduceExternal(z) 함수 사용.#include#includetypedef struct Node { int key; struct Node* parent; struct Node* lChild; struct Node* rChild;}Node;int isExternal(Node* w) { if ((w->lChild == NULL) && (w->rChild == NULL)) { return 1; } else { return 0; }}int isInternal(Node* w) { if ((w->lChild != NULL) && (w->rChild != NULL)) { return 1; } else { return 0; }}Node sibling(Node w) { if (w->parent == NULL) { return; } if (w->parent->lChild == w) { return w->parent->rChild; } else { return w->parent->lChild; }}Node inOrderSucc(Node w) { w = w->rChild; if (isExternal(w)) { return; } while (isInternal(w->lChild)) { w = w->lChild; } return w;}void reduceExternal(Node root, Node z) { Node w, zs, * g; w = z->parent; zs = sibling(z); if (w->parent == NULL) { root->lChild = zs->lChild; root->rChild = zs->rChild; root->lChild->parent = zs; root->rChild->parent = zs; zs->parent = NULL; } else { g = w->parent; zs->parent = g; if (w == g->lChild) { g->lChild = zs; } else if (w == g->rChild) { g->rChild = zs; } } free(z); free(w); return zs;}Node treeSearch(Node w, int k) { if (isExternal(w)) { return w; } if (w->key == k) { return w; } else if (w->key > k) { return treeSearch(w->lChild, k); } else { return treeSearch(w->rChild, k); }}void insertItem(Node* w, int k) { Node lChildNode = (Node)malloc(sizeof(Node)); Node rightChildNode = (Node)malloc(sizeof(Node)); Node* p = treeSearch(w, k); p->key = k; p->lChild = lChildNode; p->rChild = rightChildNode; lChildNode->parent = p; rightChildNode->parent = p; lChildNode->lChild = NULL; lChildNode->rChild = NULL; rightChildNode->lChild = NULL; rightChildNode->rChild = NULL;}int removeElement(Node* w, int k) { Node * p = treeSearch(w, k); Node z, y; int e; if (isExternal(p)) return -1; e = p->key; z = p->lChild; if (!isExternal(z)) z = p->rChild; if (isExternal(z)) reduceExternal(p, z); else { y = inOrderSucc(p); z = y->lChild; p->key = y->key; reduceExternal(p, z); } return e;}void printTree(Node* w) { if (isExternal(w)) { return; } else { printf(" %d", w->key); printTree(w->lChild); printTree(w->rChild); }}void freeTree(Node* w) { if (isExternal(w)) { return; } else { freeTree(w->lChild); freeTree(w->rChild); free(w); }}void main() { char text; int key, value; Node w = (Node)malloc(sizeof(Node)); w->parent = NULL; w->lChild = NULL; w->rChild = NULL; while (1) { scanf("%c", &text); if (text == 'i') { scanf("%d", &key); insertItem(w, key); getchar(); } else if (text == 'd') { scanf("%d", &key); value = removeElement(w, key); if (value == -1) { printf("X "); } else { printf("%d ", value); } getchar(); } else if (text == 's') { scanf("%d", &key); if (treeSearch(w, key)->key != key) { printf("X "); } else { printf("%d ", treeSearch(w, key)->key); } getchar(); } else if (text == 'p') { printTree(w); printf(" "); getchar(); } else if (text == 'q') { break; } } freeTree(w);}어디에서 런타임에러가 나는지 모르겠습니다.

honolulu · Answer

F5 누르고 죽는 위치를 확인해 보세요.

알고리즘 런타임에러 질문입니다.

1개의 답변

기술 목록