[C 언어] RBTree 중위 순회, 배열로 변환 구현

✔️ RBTree 이론 보고 오기 => 클릭

✔️ RBTree 구현 정리 노션 => 클릭

✔️ RBTree 구현 전체 코드 => 클릭

🎄 배열로 전환

tree_to_array(tree, array, n)
=> RB tree의 내용을 key 순서대로 주어진 array로 변환
=> array의 크기는 n으로 주어지며 tree의 크기가 n 보다 큰 경우에는 순서대로 n개 까지만 변환
=> array의 메모리 공간은 이 함수를 부르는 쪽에서 준비하고 그 크기를 n으로 알려줍니다.

• rbtree_to_array 함수에서는 트리가 비어있지 않은 경우에만 중위순회를 시작
• 중위순회를 위해 inorder 함수를 호출
• inorder 함수에서는 재귀적으로 왼쪽 서브트리를 순회한 후 현재 노드의 키 값을 배열에 저장하고, 그 다음에는 오른쪽 서브트리를 순회하여 배열에 저장
• 함수는 마지막으로 업데이트된 배열 인덱스를 반환하여 순회가 종료된 후의 배열 인덱스를 반환

/* 6. array로 변환 */
// 트리의 노드들을 배열에 저장하는 함수
int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n) {
  // 트리가 비어있지 않다면 중위순회 시작
  if (t->root != t->nil) {
    inorder(t->root, t, arr,0);
  }
  return 0;
}

// 중위 순회하며 트리의 노드들을 배열에 저장하는 함수
int inorder(node_t *x, const rbtree *t, key_t *arr, int i){
  if(x == t->nil) // 현재 노드가 nil인 경우, 종료
    return i;
  i = inorder(x->left ,t,arr,i); // 왼쪽 서브트리를 중위 순회하여 배열에 저장하고, 배열 인덱스를 업데이트
  arr[i++] = x->key; // 현재 노드의 키 값을 배열에 저장하고, 배열 인덱스를 증가
  i = inorder(x->right,t,arr,i); // 오른쪽 서브트리를 중위 순회하여 배열에 저장하고, 배열 인덱스를 업데이트
  return i;
}