📝 오늘 한 것

1. 자료 구조와 알고리즘 복습

📚 배운 것 (복습)

책 『누구나 자료 구조와 알고리즘』 복습

1. 자료 구조와 알고리즘

• [TIL] 211023
  • 연결 리스트
  • 이중 연결 리스트

이중 연결 리스트에서는 기록해놓은 마지막 노드에 바로 접근할 수 있고, 각 노드가 바로 앞 노드를 가리키는 링크를 가지고 있다.

• [TIL] 211024
  • 이진 트리
  • 이진 트리의 연산 💢
  • 배열 VS 연결 리스트
  • 정렬된 배열 VS 이진 트리
  • 이진 트리의 순회

🙋‍♀️ 이진 트리의 연산 中 '삭제'

class TreeNode {
  constructor(value, left_child = null, right_child = null) {
    this.value = value;
    this.left_child = left_child;
    this.right_child = right_child;
  }
}

const node_1 = new TreeNode(1);
const node_2 = new TreeNode(3);
const root = new TreeNode(5, node_1, node_2);

function remove(valueToRemove, node) {
  if (node === null) {
    return null;
  } else if (valueToRemove < node.value) {
    node.left_child = remove(valueToRemove, node.left_child);
  } else if (valueToRemove > node.value) {
    node.right_child = remove(valueToRemove, node.right_child);
  } else {
    if (node.left_child === null) {
      return node.right_child;
    } else if (node.right_child === null) {
      return node.left_child;
    } else {
      node.right_child = lift(node.right_child, node);
      return node;
    }
  }
}

function lift(node, nodeToRemove) {
  if (node.left_child) {
    node.left_child = lift(node.left_child, nodeToRemove);
    return node;
  } else {
    nodeToRemove.value = node.value;
    return node.right_child;
  }
}

💡 중위 순회

// 왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드
function traverse_and_print(node) {
  if (node === null) {
    return;
  }
  traverse_and_print(node.left_child);
  console.log(node.value);
  traverse_and_print(node.right_child);
}

[ 책 그림 참고 ]
왼쪽 자식 노드가 없을 때까지 내려가서 가장 왼쪽 자식 노드를 출력
출력한 왼쪽 자식 노드의 오른쪽 자식 노드가 없으면 그 부모 노드를 출력
그 오른쪽 자식 노드가 있다면 그 오른쪽 자식 노드를 출력

✨ 내일 할 것

1. 자료 구조와 알고리즘