이진탐색트리 최댓값, 최솟값 노드 찾기, 구현

 

 

 

 

●이진검색트리의 특징

부모를 기준으로 부모보다 큰 데이터 오른쪽에, 작은 데이터는 왼쪽에.

 

따라서 루트를 중심으로 오른쪽 끝까지 찾아가면 최댓값을 찾을 수 있다.

왼쪽 끝까지 찾아가면 최솟값을 찾을 수 있다.

 

 

●최댓값, 최솟값 찾는 과정 구현

typedef struct TREE {
  int value;
  struct TREE* left;
  struct TREE* right;
} TREE;

TREE* findMax(TREE* t) {
  if(t) {
    while(t->right)
      t = t->right;
    return t;
  }
}

TREE* findMin(TREE* t) {
  if(t->left)
    t = findMin(t->left)
  return t;
}

 

반복문으로 구현할 수 있으면 반복문으로 구현하는 것이 좋다.

최댓값은 반복문으로, 최솟값은 재귀호출로 구현해보았다.