Back-End/Algorithm
Search Binary Tree (no example)
무지맘
2023. 3. 8. 00:24
1. Problem
- 이진 트리에서 원하는 값을 찾아보자.
// 이진 트리란?
1) 값(key)을 가진 노드들의 모임
2) 노드는 자식 노드를 왼쪽 하나(left subtree), 오른쪽 하나(right subtree)를 가질 수 있다.
3) 왼쪽 자식의 노드 값은 부모 노드(root)보다 작거나 같고, 오른쪽 자식의 노드 값은 크거나 같다.
2. Input
1) 이진 트리를 가리키는 포인터 tree
2) 찾아야 할 값 keyin
3. Output
1) 찾아야 할 값이 있는 노드를 가리키는 포인터 p
4. PseudoCode
void search(node_pointer tree, keytype keyin, node_pointer p){
boolean found;
p = tree;
found = false;
while(!found){
if(p->key == keyin)
found = true;
else if(keyin < p->key)
p = p->left;
else
p = p->right;
}
}