Tree

• Tree는 비선형이고 계층을 갖고있는 자료구조입니다.
• 나무와 유사하게 계층적 구조를 갖고 있는 것을 의미합니다.
• 트리의 주된 목적은 탐색이며, 검색엔진, 댓글 구현 등 매우 다양한 곳에서 응용이 되고 있습니다.

Binary Tree Structure(이진 트리)

최대 2개의 자식을 갖는 트리 구조입니다.

이진트리의 탐색

• 전위 순회(pre-order)는 루트에서 왼쪽 트리를 탐색하고 오른쪽 트리를 순회합니다.
• 중위 순회(in-order)는 왼쪽트리의 끝부터 탐색을 시작하고 루트를 탐색 후 오른쪽 트리를 순회합니다.
• 후위 순회(post-order)는 왼쪽트리 끝부터 탐색을 시작하여 오른쪽 트리를 탐색 후 루트를 순회합니다.

Tree를 javascript로 구현

이진 트리로써 루트와 비교했을때 루트보다 큰 값은 오른쪽으로, 작은 값은 왼쪽으로 보내는 트리구조.

const BinarySearchTree= () => {
  const Node = (key) => {
  this.key = key;
    this.left = null;
    this.right = null;
  };
  let root = null;
  // 트리구조에 data를 담는 구조 구현
  // 값이 작으면 왼쪽, 값이 크면 오른쪽
  const insertNode = (node, newNode) => {
    if(newNode.key < node.key){
      if(node.left === null){
        node.left = newNode;
      } else {
        insertNode(node.left, newNode);
      }
    } else {
      if(node.right === null){
        node.right = newNode;
      } else {
        insertNode(node.right, newNode);
      }
    }
  }
  // 트리구조에 data를 추가할 때
  this.insert = (key) => {
    let newNode = new Node(key);
    if(root === null){
      root = newNode;
    } else {
      insertNode(root, newNode);
    }
  };
  // 전위 순회
  const preOrderTraverseNode = (node, callback) => {
    if(node !== null){
      callback(node.key);
      preOrderTraverseNode(node.left, callback);
      preOrderTraverseNode(node.right, callback);
    }
  }
  this.preOrderTraverse = (callback) => {
    preOrderTraverseNode(root, callback);
  };
  // 중위 순회
  var inOrderTraverseNode = (node, callback) => {
    if(node !== null){
      inOrderTraverseNode(node.left, callback);
      callback(node.key);
      inOrderTraverseNode(node.right, callback);
    }
  }
  this.inOrderTraverse = (callback) => {
    inOrderTraverseNode(root, callback);
  };
  // 후위 순회
  var postOrderTraverseNode = (node, callback) => {
    if(node !== null){
      postOrderTraverseNode(node.left, callback);
      postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  }
  this.postOrderTraverse = (callback) => {
    postOrderTraverseNode(root, callback);
  };
  // 트리구조의 최소값 (가장 왼쪽에 있는 마지막 값은 가장 트리구조에서 가장 작은 숫자이다.)
  this.min = () => {
    return minNode(root);
  }
  const minNode = (node) => {
    if(node){
      while(node && node.left !== null){
        node = node.left;
      }
      return node.key
    }
    return null;
  };
  // 트리구조의 최대값 (가장 오른쪽에 있는 마지막 값은 가장 트리구조에서 가장 큰 숫자이다.)
  this.max = function () {
    return maxNode(root);
  }
  const maxNode = (node) => {
    if(node){
      while(node && node.right !== null){
        node = node.right;
      }
      return node.key;
    }
    return null;
  };
  // 트리구조에서 원하는 값을 찾을 때.
  this.search = (key) => {
    return searchNode(root, key);
  };
  const searchNode = (node, key) => {
    if(node === null){
      return false;
    }
    if(key < node.key){
      return searchNode(node.left, key)
    } else if(key > node.key){
      return searchNode(node.left, key)
    } else {
      return true;
    }
  }
}
const printNode = (value) => {
  console.log(value);
}