[탐색트리] 이진탐색트리

[탐색트리] 이진탐색트리

이진탐색트리 : 내부노드에 (키,원소) 쌍을 저장하며, key(u)

- 적정이진트리 전제

- 이진탐색트리를 중위순회하면서 키가 증가하는 순서로 방문

이진탐색트리 (Binary Search Tree)의 조건

- 이진 트리는 루트를 중심으로 노드가 왼쪽에 하나 오른쪽에 하나씩 연결된다.

- 노드 N(어느 한 노드)을 기준으로 왼쪽 트리의 키값은 노드 N보다 작아야 하고, 오른쪽 트리의 키 값은 노드 N보다 커야 한다.

- 같은 키값을 갖는 노드는 없다.

문제: 이진탐색트리 구현 (전위순회 출력)

#define _CRT_SECURE_NO_WARNINGS #include #include #include // 이진탐색트리 typedef struct treeNode { int key; struct treeNode* lchild; struct treeNode* rchild; struct treeNode* parent; }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; } void getNode(node** w) { (*w) = (node*)malloc(sizeof(node)); (*w)->parent = NULL; (*w)->lchild = NULL; (*w)->rchild = NULL; } void expandExternal(node* w) {//양쪽 외부노드로 확장 node* newleft; node* newright; getNode(&newleft;); getNode(&newright;); w->lchild = newleft; w->rchild = newright; newleft->parent = w; newright->parent = w; } node* treeSearch(node* w, int k) { if (isExternal(w)) return w; if (k == w->key) return w; else if (k < w->key) return treeSearch(w->lchild, k); else return treeSearch(w->rchild, k); } void insertKey(node* root, int k) { node* w = treeSearch(root, k); if (isInternal(w)) return; else { w->key = k; expandExternal(w); return; } } void findElement(node* root, int k) { node* w = treeSearch(root, k); if (isInternal(w)) printf("%d

", k); else printf("X

"); } node* sibling(node* root, node* z) {// w와 z없애고 붙일 노드 정하기 if (root == z) return root; if (z->parent->lchild == z) return z->parent->rchild; else return z->parent->lchild; } node* inOrderSucc(node* w) {// 중위순회 계승자 구하기 node* y = w->rchild;// y는 우선 w의 오른쪽 자식으로 이동 후 if (isExternal(y)) return y; while (isInternal(y->lchild))// 거기서부터 왼쪽 자식만을 끝까지 따라 내려가면 도달하게 되는 마지막 내부노드임 y = y->lchild; return y;//중위순회 계승자 반환 } void reduceExternal(node** root, node* z) { node* w = z->parent; node* zs, * g; zs = sibling(*root, z); if (w == *root) { *root = zs; zs->parent = NULL; } else { g = w->parent; zs->parent = g; if (w == g->lchild) g->lchild = zs; else g->rchild = zs; } free(z); free(w); } node* removeElement(node** root, int k) { node* w = treeSearch(*root, k); if (isExternal(w)) { printf("X

"); return; } //삭제할 노드가 있다면 node* z = w->lchild; if (!isExternal(z))// z = w->rchild; if (isExternal(z)) reduceExternal(root, z); else {// case2 node* y = inOrderSucc(w);// 중위순회 계승자 y z = y->lchild;//노드 z는 y의 왼쪽 자식인 외부노드 w->key = y->key;//y의 내용을 w에 복사하고 reduceExternal(root, z);//노드 y와 z 삭제 } printf("%d

", k); } void printNode(node* root) { if (isExternal(root)) return; else { printf(" %d", root->key); printNode(root->lchild); printNode(root->rchild); } } void freeNode(node* root) { if (isExternal(root)) return; else { freeNode(root->lchild); freeNode(root->rchild); free(root); } } int main() { char type; int key; node* root = (node*)malloc(sizeof(node)); getNode(&root;); while (1) { scanf("%c", &type;); if (type == 'q') break; else if (type == 'i') { scanf("%d", &key;); getchar(); insertKey(root, key); } else if (type == 'd') { scanf("%d", &key;); getchar(); removeElement(&root;, key);// } else if (type == 's') { scanf("%d", &key;); getchar(); findElement(root, key); } else if (type == 'p') { printNode(root); printf("

"); } } freeNode(root); return 0; }

from http://code731.tistory.com/32 by ccl(A) rewrite - 2021-10-20 16:26:36