[TypeScript] 완전 이진 트리, 이진 탐색 트리 구현

TypeScript를 통해 완전 이진트리를 구현하였습니다.

기본적으로 Tree에 들어가는 Node부터 구현하였습니다.

/** 
Tree에 들어가는 Node 구현
@param {T} data Node에 들어갈 data
@returns {TreeNode}
*/
export class TreeNode<T> {
  public data: T;
  public left: TreeNode<T> | null = null;
  public right: TreeNode<T> | null = null;

  constructor(data: T) {
    this.data = data;
  }
}

완전 이진트리 구현

배열을 받아 완전 이진트리를 구현하였습니다.

이진트리 구현 시 조건 없이 완전히 채우는 트리입니다.

import { TreeNode } from "./TreeNode";
/**
 * 배열을 받았을 때 완전 이진트리로 변환해주는 Class로써, 삽입과 수정이 불가능합니다.
 * index를 통해서 이진트리 구조를 생성
 */
export class CBT<T> {
  private root: TreeNode<T> | null = null;

  /**
   * 배열을 받아 Tree 구조를 만듭니다.
   * @param {T[]} elements 입력하고자 하는 Array
   */
  insert(elements: T[]): void {
    this.insertNode(elements, 0);
  }

  /**
   * 배열을 받아서 binaryTree를 구현합니다.
   * 재귀 함수를 통해 parent 및 하위 노드를 구현합니다.
   * @param {T[]} elements Tree Node를 이룰 Array 집합
   * @param {number} index Array의 인덱스
   * @returns {TreeNode<T> | null} 해당 값이 null일 경우 null 반환, 아니면 Tree 반환
   */
  private insertNode(elements: T[], index: number): TreeNode<T> | null {
    // 부모 선언 및 초기화
    let parent: TreeNode<T> | null = null;
    // index가 element보다 작을 경우에만 진행
    if (index < elements.length) {
      let value = elements[index];
      if (value === null || value === undefined) {
        return null;
      }

      parent = new TreeNode(elements[index]);
      if (index === 0) {
        this.root = parent;
      }
      parent.left = this.insertNode(elements, 2 * index + 1);
      parent.right = this.insertNode(elements, 2 * index + 2);
    }
    return parent;
  }

  /**
   * 이진 트리를 반전하는 메서드
   */
  invert(): void {
    this.invertNode(this.root);
  }

  /**
   * 재귀 함수를 통해 이진 트리를 반전한다.
   * @param {TreeNode<T> | null} parent
   * @returns {TreeNode<T> | null}
   */
  private invertNode(parent: TreeNode<T> | null): TreeNode<T> | null {
    if (parent) {
      [parent.left, parent.right] = [
        this.invertNode(parent.right),
        this.invertNode(parent.left),
      ];
      return parent;
    } else {
      return null;
    }
  }

  getRoot(): TreeNode<T> | null {
    return this.root;
  }
}

이진 탐색 트리 구현

숫자를 입력받아 이진 탐색트리를 구현합니다.

insert와 Search만 구현하였습니다.

import { TreeNode } from "./TreeNode";

export class BinarySearchTree {
  private root: TreeNode<number> | null = null;
  constructor() {
    this.root = null;
  }

  /**
   * Tree에 Node 삽입 매서드입니다. 하나씩 데이터를 삽입하는 구조입니다.
   * @param {number} value
   */
  insert(value: number): void {
    const newNode = new TreeNode(value);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  /**
   * 재귀함수를 통해 반복하는 insertNode 구조입니다.
   * @param {TreeNode<number>} node
   * @param {TreeNode<number>} newNode
   */
  insertNode(node: TreeNode<number>, newNode: TreeNode<number>): void {
    // newNode의 값보다 기존 Node 값이 큰 경우
    // 왼쪽으로 newNode를 보낸다.
    if (node.data > newNode.data) {
      // left가 비어있는 경우 newNode로 입력
      if (node.left === null) {
        node.left = newNode;
      } else {
        // 없는 경우 재귀함수를 통해 반복
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }
  /**
   * 노드 탐색입니다.
   * @param {number} value
   * @returns
   */
  search(value: number) {
    return this.searchNode(this.root, value);
  }

  /**
   * 재귀 함수를 통한 노드 탐색입니다.
   * @param {TreeNode<number> | null} node 재귀함수에서 반환되는 node이며, null이 나올 수 있습니다.
   * @param {number} value
   * @returns {TreeNode<number> | number | null}
   */
  private searchNode(
    node: TreeNode<number> | null,
    value: number
  ): TreeNode<number> | number | null {
    // 해당하는 데이터가 없는 경우, null 반환
    if (node === null) {
      return null;
    }
    // 해당하는 데이터 확인 시 반환 진행
    if (node.data === value) {
      return node.data;
    }

    // value값 보다 node의 데이터가 큰 경우 탐색 진행
    if (node.data > value) {
      return this.searchNode(node.left, value);
    } else {
      // 큰 경우 오른쪽으로 탐색 진행
      return this.searchNode(node.right, value);
    }
  }
  getRoot(): TreeNode<number> | null {
    return this.root ? this.root : null;
  }
}

회고

완전 이진 트리와 이진 탐색 트리 구현 시 간단하게 구현하였습니다.

그러나, 어떠한 제약 없이 구현하다 보니 "어떻게 구현할까??" 가 굉장한 관건이였습니다.

이는 코딩테스트를 통해서 다양한 조건 하에 구현해야 될 것 같습니다.