Search Binary Tree (no example)

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;
    }
}