[JavaScript 알고리즘] 트리 순회

📕Algorithm/JavaScript

[JavaScript 알고리즘] 트리 순회

_Hazel_ 2024. 10. 29. 13:37

트리 탐색에는 두 가지 주요 방법이 있습니다:

너비 우선 탐색 (Breadth-first Search, BFS)
깊이 우선 탐색 (Depth-first Search, DFS)

1. 너비 우선 탐색 (Breadth-first Search, BFS)

너비 우선 탐색은 트리의 각 레벨을 순차적으로 탐색하는 방식입니다. 먼저 루트 노드를 방문한 뒤, 바로 다음 레벨의 모든 자식 노드를 차례대로 방문합니다. 이 방식은 큐(Queue) 자료구조를 사용하여 구현되며, 가까운 노드부터 먼 노드까지 방문합니다. 예를 들어, 루트 노드의 모든 자식 노드를 먼저 방문하고 그 다음 자식의 자식 노드들을 탐색하는 순서로 진행됩니다.

너비 우선 탐색(BFS)을 반복적으로 수행하는 단계는 다음과 같습니다:

큐(queue)와 방문한 노드 값을 저장할 변수를 생성
트리 탐색에 사용할 큐(일반적으로 배열로 구현 가능)와, 방문한 노드들의 값을 저장할 변수를 준비합니다.
루트 노드를 큐에 넣음
시작점인 루트 노드를 큐에 추가합니다.
큐에 항목이 있는 동안 반복
큐가 비어 있지 않으면 계속해서 반복문을 실행합니다.
큐에서 노드를 꺼내고, 해당 노드의 값을 변수에 추가
큐에서 맨 앞에 있는 노드를 꺼내어(제거) 그 노드의 값을 방문한 노드를 저장하는 변수에 추가합니다.
왼쪽 자식이 있는 경우, 왼쪽 자식을 큐에 추가
꺼낸 노드에 왼쪽 자식 노드가 있으면 해당 자식을 큐에 추가합니다.
오른쪽 자식이 있는 경우, 오른쪽 자식을 큐에 추가
꺼낸 노드에 오른쪽 자식 노드가 있으면 해당 자식을 큐에 추가합니다.
노드 값이 저장된 변수를 반환
큐가 비게 되면, 모든 노드를 방문한 것이므로 저장된 방문 노드 값을 반환합니다.

이 과정을 통해 트리의 각 레벨을 차례로 방문하며, 가까운 노드부터 먼 노드 순서로 탐색이 이루어집니다.

구현

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}
class BinaryTree {
  constructor() {
    this.root = null;
  }
  bfs() {
    const queue = [];
    const visited = [];

    if (this.root) queue.push(this.root);
    while (queue.length > 0) {
      const curNode = queue.shift();
      visited.push(curNode.val);
      if (curNode.left) queue.push(curNode.left);
      if (curNode.right) queue.push(curNode.right);
    }
    return visited;
  }
}

const tree = new BinaryTree();
tree.root = new Node(10);
tree.root.left = new Node(6);
tree.root.right = new Node(15);
tree.root.left.left = new Node(3);
tree.root.left.right = new Node(8);
tree.root.right.right = new Node(20);

console.log(tree.bfs());

구현2

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }
  insert(val) {
    const newNode = new Node(val);
    if (this.root === null) {
      this.root = newNode;
      return this;
    } else {
      let current = this.root;
      while (true) {
        if (val === current.val) return undefined;
        if (val < current.val) {
          if (current.left === null) {
            current.left = newNode;
            return this;
          }
          current = current.left;
        } else {
          if (current.right === null) {
            current.right = newNode;
            return this;
          }
          current = current.right;
        }
      }
    }
  }
  find(val) {
    if (this.root === null) return false;
    let current = this.root;
    while (current) {
      if (val < current.val) {
        current = current.left;
      } else if (val > current.val) {
        current = current.right;
      } else {
        return true;
      }
    }
    return false;
  }
  bfs() {
    const queue = [];
    const visited = [];
    if (this.root) queue.push(this.root);
    while (queue.length) {
      const current = queue.shift();
      visited.push(current.val);
      if (current.left) queue.push(current.left);
      if (current.right) queue.push(current.right);
    }
    return visited;
  }
}

const tree = new BST();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);
console.log(tree.bfs());

2. 깊이 우선 탐색 (Depth-first Search, DFS)

깊이 우선 탐색은 트리의 특정 경로를 끝까지 탐색한 후, 다시 이전 분기점으로 돌아가 다른 경로를 탐색하는 방식입니다. DFS는 주로 스택(Stack) 자료구조를 사용하여 구현되며, 먼저 한쪽 방향으로 깊이 내려간 뒤 다시 다른 경로를 탐색합니다. DFS에는 세 가지 주요 방식이 있습니다:

전위 순회(Pre-order): 부모 노드를 먼저 방문한 후 자식 노드를 방문.

깊이 우선 탐색(DFS) 중 전위 순회(PreOrder)를 재귀적으로 수행하는 단계는 다음과 같습니다:

방문한 노드의 값을 저장할 변수를 생성
방문한 노드의 값을 저장할 배열 변수를 생성합니다.
BST의 루트를 current라는 변수에 저장
탐색을 시작할 루트 노드를 current라는 변수에 저장합니다.
헬퍼 함수 작성
헬퍼 함수를 작성하여 각 노드를 방문할 때 다음을 수행하도록 합니다.
1. 노드의 값을 방문한 노드 값 변수에 추가
  현재 노드의 값을 먼저 저장합니다. (전위 순회에서는 노드를 처음 방문하자마자 값을 저장합니다.)
2. 왼쪽 자식 노드가 있으면, 왼쪽 자식 노드를 헬퍼 함수로 호출
  현재 노드에 왼쪽 자식 노드가 있는 경우, 그 자식을 인수로 헬퍼 함수를 재귀 호출합니다.
3. 오른쪽 자식 노드가 있으면, 오른쪽 자식 노드를 헬퍼 함수로 호출
  현재 노드에 오른쪽 자식 노드가 있는 경우, 그 자식을 인수로 헬퍼 함수를 재귀 호출합니다.
current 변수를 헬퍼 함수에 전달하여 호출
위에서 생성한 current 변수를 인수로 하여 헬퍼 함수를 호출합니다. 이로써 루트 노드부터 탐색이 시작됩니다.
방문한 노드 값이 저장된 배열 반환
모든 노드를 방문한 후, 방문한 노드 값이 저장된 배열을 반환합니다.

이 과정을 통해 전위 순회를 수행하여 루트부터 시작해 왼쪽과 오른쪽 순서로 각 노드를 방문하게 되며, 모든 노드 값을 담은 배열이 최종적으로 반환됩니다.

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

class bst {
  constructor() {
    this.root = null;
  }
  insert(val) {
    const newNode = new Node(val);
    if (this.root === null) {
      this.root = newNode;
      return this;
    } else {
      let current = this.root;
      while (true) {
        if (val === current.val) return undefined;
        if (val < current.val) {
          if (current.left === null) {
            current.left = newNode;
            return this;
          }
          current = current.left;
        } else {
          if (current.right === null) {
            current.right = newNode;
            return this;
          }
          current = current.right;
        }
      }
    }
  }
  dfsPreOrder() {
    const result = [];
    function traverse(node) {
      if (!node) return;
      result.push(node.val);
      traverse(node.left);
      traverse(node.right);
    }
    traverse(this.root);
    return result;
  }
}

const tree = new bst();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);

console.log(tree.dfsPreOrder());// 출력: [10, 6, 3, 8, 15, 20]

중위 순회(In-order): 왼쪽 자식을 방문하고 부모 노드를 방문한 후 오른쪽 자식을 방문 (주로 이진 트리에 사용).

깊이 우선 탐색(DFS) 중에서 중위 순회(InOrder)를 재귀적으로 수행하는 단계는 다음과 같습니다:

방문한 노드의 값을 저장할 변수를 생성
방문한 노드의 값을 저장할 배열 변수를 생성합니다.
BST의 루트를 current라는 변수에 저장
탐색을 시작할 루트 노드를 current라는 변수에 저장합니다.
헬퍼 함수 작성
헬퍼 함수를 작성하여 각 노드를 방문할 때 다음을 수행하도록 합니다.
왼쪽 자식 노드가 있으면, 왼쪽 자식 노드를 헬퍼 함수로 호출
현재 노드에 왼쪽 자식 노드가 있는 경우, 그 자식을 인수로 헬퍼 함수를 재귀 호출합니다.
노드의 값을 방문한 노드 값 변수에 추가
왼쪽 자식 노드들을 모두 방문한 후, 현재 노드의 값을 저장합니다.
오른쪽 자식 노드가 있으면, 오른쪽 자식 노드를 헬퍼 함수로 호출
현재 노드에 오른쪽 자식 노드가 있는 경우, 그 자식을 인수로 헬퍼 함수를 재귀 호출합니다.
current 변수를 헬퍼 함수에 전달하여 호출
위에서 생성한 current 변수를 인수로 하여 헬퍼 함수를 호출합니다. 이로써 루트 노드부터 탐색이 시작됩니다.
방문한 노드 값이 저장된 배열 반환
모든 노드를 방문한 후, 방문한 노드 값이 저장된 배열을 반환합니다.

이 과정을 통해 이진 탐색 트리(BST)를 중위 순회하며, 왼쪽부터 순서대로 노드를 방문합니다.

구현

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

class bst {
  constructor() {
    this.root = null;
  }
  insert(val) {
    const newNode = new Node(val);
    if (this.root === null) {
      this.root = newNode;
      return this;
    } else {
      let current = this.root;
      while (true) {
        if (val === current.val) return undefined;
        if (val < current.val) {
          if (current.left === null) {
            current.left = newNode;
            return this;
          }
          current = current.left;
        } else {
          if (current.right === null) {
            current.right = newNode;
            return this;
          }
          current = current.right;
        }
      }
    }
  }
  dfsInOrder() {
    const result = [];
    function traverse(node) {
      if (!node) return;
      traverse(node.left);
      result.push(node.val);
      traverse(node.right);
    }
    traverse(this.root);
    return result;
  }
}

const tree = new bst();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);

console.log(tree.dfsInOrder());// 출력: [3, 6, 8, 10, 15, 20]

후위 순회(Post-order): 자식 노드를 먼저 방문한 후 부모 노드를 방문.

깊이 우선 탐색(DFS) 중 후위 순회(PostOrder)를 재귀적으로 수행하는 단계는 다음과 같습니다:

방문한 노드의 값을 저장할 변수를 생성
방문한 노드의 값을 저장할 배열 변수를 생성합니다.
BST의 루트를 current라는 변수에 저장
탐색을 시작할 루트 노드를 current라는 변수에 저장합니다.
헬퍼 함수 작성
헬퍼 함수를 작성하여 각 노드를 방문할 때 다음을 수행하도록 합니다.
왼쪽 자식 노드가 있으면, 왼쪽 자식 노드를 헬퍼 함수로 호출
현재 노드에 왼쪽 자식 노드가 있는 경우, 그 자식을 인수로 헬퍼 함수를 재귀 호출합니다.
오른쪽 자식 노드가 있으면, 오른쪽 자식 노드를 헬퍼 함수로 호출
현재 노드에 오른쪽 자식 노드가 있는 경우, 그 자식을 인수로 헬퍼 함수를 재귀 호출합니다.
노드의 값을 방문한 노드 값 변수에 추가
왼쪽과 오른쪽 자식 노드들을 모두 방문한 후, 현재 노드의 값을 저장합니다.
current 변수를 헬퍼 함수에 전달하여 호출
위에서 생성한 current 변수를 인수로 하여 헬퍼 함수를 호출합니다. 이로써 루트 노드부터 탐색이 시작됩니다.
방문한 노드 값이 저장된 배열 반환
모든 노드를 방문한 후, 방문한 노드 값이 저장된 배열을 반환합니다.

이 과정을 통해 후위 순회가 수행되며, 각 노드를 왼쪽과 오른쪽 순서로 먼저 방문한 후, 마지막에 현재 노드를 방문하여 배열에 추가합니다. 최종적으로 모든 노드 값을 담은 배열이 반환됩니다.

구현

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

class bst {
  constructor() {
    this.root = null;
  }
  insert(val) {
    const newNode = new Node(val);
    if (this.root === null) {
      this.root = newNode;
      return this;
    } else {
      let current = this.root;
      while (true) {
        if (val === current.val) return undefined;
        if (val < current.val) {
          if (current.left === null) {
            current.left = newNode;
            return this;
          }
          current = current.left;
        } else {
          if (current.right === null) {
            current.right = newNode;
            return this;
          }
          current = current.right;
        }
      }
    }
  }
  dfsPostOrder() {
    const result = [];
    function traverse(node) {
      if (!node) return;
      traverse(node.left);
      traverse(node.right);
      result.push(node.val);
    }
    traverse(this.root);
    return result;
  }
}

const tree = new bst();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);

console.log(tree.dfsPostOrder());// 출력: [3, 8, 6, 20, 15, 10]

정리

트리는 루트와 자식 노드를 포함하는 비선형 데이터 구조입니다.

이진 트리(Binary Trees)는 각 부모가 최대 두 개의 자식을 가질 수 있으며, 노드의 값은 어떤 타입이든 될 수 있습니다.
이진 탐색 트리(Binary Search Trees, BST)는 이진 트리의 특정한 형태로, 부모 노드의 왼쪽에 있는 모든 노드는 부모의 값보다 작고, 오른쪽에 있는 모든 노드는 부모의 값보다 큽니다.
트리를 탐색할 때는 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)을 사용할 수 있습니다.

자식 노드가 없는 노드를 삭제하는 단계는 다음과 같습니다:

삭제하려는 노드와 그 부모 노드를 찾기
삭제해야 할 노드와 그 부모 노드를 찾습니다.
삭제할 값이 부모 노드보다 큰 경우
삭제하려는 노드의 값이 부모 노드의 값보다 큰 경우, 부모 노드의 right(오른쪽 자식) 속성을 null로 설정합니다.
삭제할 값이 부모 노드보다 작은 경우
삭제하려는 노드의 값이 부모 노드의 값보다 작은 경우, 부모 노드의 left(왼쪽 자식) 속성을 null로 설정합니다.
삭제하려는 노드가 루트 노드인 경우
삭제하려는 노드가 루트 노드일 경우, 트리의 root를 null로 설정합니다.

이 절차를 통해 자식이 없는 노드를 안전하게 삭제할 수 있습니다.

자식 노드가 하나인 노드를 삭제하는 단계는 다음과 같습니다:

삭제하려는 노드와 그 부모 노드를 찾기
삭제할 노드와 그 부모 노드를 찾습니다.
삭제하려는 노드의 자식이 오른쪽에 있는지 왼쪽에 있는지 확인
삭제할 노드의 자식이 오른쪽에 있는지 왼쪽에 있는지를 확인합니다.
삭제할 값이 부모 노드보다 큰 경우
삭제하려는 노드의 값이 부모 노드의 값보다 큰 경우, 부모 노드의 right(오른쪽 자식) 속성을 삭제하려는 노드의 자식 노드로 설정합니다.
삭제할 값이 부모 노드보다 작은 경우
삭제하려는 노드의 값이 부모 노드의 값보다 작은 경우, 부모 노드의 left(왼쪽 자식) 속성을 삭제하려는 노드의 자식 노드로 설정합니다.
삭제하려는 노드가 루트 노드인 경우
삭제하려는 노드가 루트 노드일 경우, 트리의 root 속성을 삭제할 노드의 자식 노드로 설정합니다.

이 절차를 통해 자식이 하나뿐인 노드를 안전하게 삭제하고 트리의 연결을 유지할 수 있습니다.

자식 노드가 두 개인 노드를 삭제하는 단계는 다음과 같습니다:

삭제하려는 노드와 그 부모 노드를 찾기
삭제할 노드와 그 부모 노드를 찾습니다.
전임 노드(Predecessor Node)를 찾고 변수에 저장
삭제할 노드의 전임 노드(대체할 노드)를 찾고, 이를 변수에 저장합니다.
전임 노드의 왼쪽 속성을 삭제할 노드의 왼쪽 속성으로 설정
전임 노드의 left 속성을 삭제할 노드의 left 속성으로 설정하여, 삭제할 노드의 왼쪽 자식 노드를 전임 노드가 참조하도록 합니다.
삭제할 값이 부모 노드보다 큰 경우
삭제할 노드의 값이 부모 노드의 값보다 큰 경우, 부모 노드의 right(오른쪽 자식) 속성을 삭제할 노드의 오른쪽 속성으로 설정합니다.
삭제할 값이 부모 노드보다 작은 경우
삭제할 노드의 값이 부모 노드의 값보다 작은 경우, 부모 노드의 left(왼쪽 자식) 속성을 삭제할 노드의 오른쪽 속성으로 설정합니다.
삭제하려는 노드가 루트 노드인 경우
삭제하려는 노드가 루트 노드일 경우, 트리의 root를 삭제할 노드의 오른쪽 속성으로 설정합니다.

이 과정을 통해 자식이 두 개인 노드를 삭제하고, 트리의 연결을 유지하면서 구조를 올바르게 유지할 수 있습니다.

'📕Algorithm > JavaScript' 카테고리의 다른 글

[JavaScript 알고리즘] 이진 검색 트리 (0)	2024.10.27
[JavaScript 알고리즘] 큐 (0)	2024.10.27
[JavaScript 알고리즘] 스택 (0)	2024.10.26
[JavaScript 알고리즘] 다중 연결 리스트 (1)	2024.10.24
[JavaScript 알고리즘] 단일 연결 리스트 (2)	2024.10.22

현재글[JavaScript 알고리즘] 트리 순회

Hazel's 기술 블로그

자바스크립트, 자바스크립트알고리즘, 선택정렬, 빅오표기법, 재귀, 합병정렬, 버블정렬, 시간복잡도, 자료구조, 알고리즘, 삽인정렬,

Today :
Yesterday :

일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30

Hazel's 기술 블로그