자바스크립트의 나무

이번 주에 우리는 JavaScript에서 나무 데이터 구조를 구현할 것입니다.

소개

트리는 조직도, 계보 트리, 컴퓨터 파일 시스템, 웹 페이지의 HTML 요소(문서 개체 모델 또는 DOM이라고도 함), 상태 다이어그램 등을 포함하여 실제 계층적 정보를 모델링할 수 있는 훌륭한 데이터 구조입니다.

트리는 트리 노드로 구성됩니다. 트리 노드는 다음을 포함하는 매우 간단한 데이터 구조입니다.

데이터

각 자식 자체가 트리 노드인 자식 목록

트리에 데이터를 추가하거나 트리에서 데이터를 제거하고 두 가지 다른 방법으로 트래버스할 수 있습니다.

깊이 우선 또는

너비 우선
이 수업에서는 트리 노드 데이터 구조를 JavaScript의 클래스로 구현합니다.

class TreeNode {
  constructor(data) {
    this.data = data;
    this.children = [];
  }
};

자식 추가

다음 작업은 트리에 자식을 추가하는 것입니다. children 배열의 각 자식은 TreeNode의 인스턴스여야 하지만 사용자 인터페이스가 다른 형식으로도 데이터를 추가할 수 있도록 허용하고 싶습니다.

예를 들어 자식을 추가하는 메서드가 .addChild()인 경우 tree.addChild(3)와 tree.addChild(new TreeNode(3)) 호출을 수용하려고 합니다.

class TreeNode {
  constructor(data) {
    this.data = data;
    this.children = [];
  }
  addChild(child) {
    if (child instanceof TreeNode) {
      this.children.push(child);
    } else {
      this.children.push(new TreeNode(child));
    }
  }
};

자식 제거

.addChild()와 마찬가지로 데이터 또는 TreeNode 일치를 기반으로 트리에서 자식을 제거하기 위한 유연한 인터페이스를 제공하고자 합니다. 예를 들어 자식을 제거하는 메서드가 .removeChild()인 경우 다음을 실행할 수 있기를 원합니다.

const blue = 'blue';
const green = new TreeNode('green');
tree.addChild(blue);         // add data
tree.addChild(green);        // add TreeNode
tree.removeChild('blue');    // remove by data
tree.removeChild(green);    // remove by TreeNode

트리에서 자식을 제거할 때 실행하는 일반적인 단계는 다음과 같습니다.

If target child is an instance of TreeNode,
  Compare target child with each child in the children array
  Update the children array if target child is found
Else 
  Compare target child with each child's data in the children array
  Update the children array if target child is found
If target child is not found in the children array
  Recursively call .removeChild() for each grandchild.

자식을 배열로 구현했기 때문에 배열 .filter() 메서드를 사용하여 자식을 업데이트할 수 있습니다. .addChild()와 마찬가지로 instanceof를 사용하여 대상 자식이 TreeNode의 인스턴스인지 확인할 수도 있습니다.

class TreeNode {
  constructor(data) {
    this.data = data;
    this.children = [];
  }

  addChild(child) {
    if (child instanceof TreeNode) {
      this.children.push(child);
    } else {
      this.children.push(new TreeNode(child));
    }
  }
  removeChild(childToRemove) {
    const length = this.children.length;
    this.children = this.children.filter(child => {
      if (childToRemove instanceof TreeNode) {
        return childToRemove !== child;
      } else {
        return child.data !== childToRemove;
      }
    });

    if (length === this.children.length) {
      this.children.forEach(child => child.removeChild(childToRemove));
    }
  }
};

예쁜 프린트

우리 나무의 구조를 시각적으로 매혹적인 방식으로 보여줄 수 있다면 좋지 않을까요? 우리는 당신에게 우리 트리의 형식화된 텍스트 디스플레이를 제공할 유용한 방법인 .print()를 제공했습니다.

예를 들어 루트 노드 15, 자식 3, 12, 0 및 손자 6, 9, 19, 8, 10, 19로 시작하는 3개 수준의 트리가 아래에 표시됩니다.

15
-- 3
-- -- 6
-- -- 9
-- 12
-- -- 19
-- -- 8
-- 0
-- -- 10
-- -- 19

이 방법은 0으로 초기화된 하나의 매개변수 level을 사용하여 전체 트리 구조를 위에서 아래로 인쇄할 수 있습니다.

class TreeNode {
  constructor(data) {
    this.data = data;
    this.children = [];
  }

  addChild(child) {
    if (child instanceof TreeNode) {
      this.children.push(child);
    } else {
      this.children.push(new TreeNode(child));
    }
  }

  removeChild(childToRemove) {
    const length = this.children.length;
    this.children = this.children.filter(child => {
      return childToRemove instanceof TreeNode
      ? child !== childToRemove
      : child.data !== childToRemove;
    });

    if (length === this.children.length) {
      this.children.forEach(child => child.removeChild(childToRemove));
    }
  }

  print(level = 0) {
    let result = '';
    for (let i = 0; i < level; i++) {
      result += '-- ';
    }
    console.log(`${result}${this.data}`);
    this.children.forEach(child => child.print(level + 1));
  }
};

깊이 우선 트리 순회

이제 트리에 노드를 추가할 수 있으므로 다음 단계는 트리를 탐색하고 그 내용을 표시하는 것입니다. 깊이 우선 또는 너비 우선의 두 가지 방법 중 하나로 이를 수행할 수 있습니다.

깊이 우선 탐색은 자식 배열의 첫 번째 자식과 해당 노드의 자식을 재귀적으로 방문하기 전에 형제와 자식을 재귀적으로 방문합니다. 알고리즘은 다음과 같습니다.

For each node
  Display its data
  For each child in children, call itself recursively

.print()를 사용하여 표시되는 이 트리를 기반으로 합니다.

15
-- 3
-- -- 6
-- -- 9
-- 12
-- -- 19
-- -- 8
-- 0
-- -- 10
-- -- 19

다음 결과를 생성하기 위해 깊이별로 탐색할 수 있습니다.

15
3
6
9
12
19
8
0
10
19

class TreeNode {
  constructor(data) {
    this.data = data;
    this.children = [];
  }

  addChild(child) {
    if (child instanceof TreeNode) {
      this.children.push(child);
    } else {
      this.children.push(new TreeNode(child));
    }
  }

  removeChild(childToRemove) {
    const length = this.children.length;
    this.children = this.children.filter(child => {
      return childToRemove instanceof TreeNode
      ? child !== childToRemove
      : child.data !== childToRemove;
    });

    if (length === this.children.length) {
      this.children.forEach(child => child.removeChild(childToRemove));
    }
  }

  print(level = 0) {
    let result = '';
    for (let i = 0; i < level; i++) {
      result += '-- ';
    }
    console.log(`${result}${this.data}`);
    this.children.forEach(child => child.print(level + 1));
  }
};

너비 우선 트리 순회

한편, 너비 우선 탐색은 자식을 방문하기 전에 첫 번째 자식부터 시작하여 최하위 수준을 방문할 때까지 추가 계층을 시작하여 자식 배열의 각 자식을 방문합니다. 알고리즘은 다음과 같습니다.

Assign an array to contain the current root node
While the array is not empty
  Extract the first tree node from the array
  Display tree node's data
  Append tree node's children to the array

.print()를 사용하여 표시되는 이 트리를 기반으로 합니다.

15
-- 3
-- -- 6
-- -- 9
-- 12
-- -- 19
-- -- 8
-- 0
-- -- 10
-- -- 19

우리는 이 결과를 생성하기 위해 그것을 폭 방향으로 횡단할 수 있습니다:

15
3
12
0
6
9
19
8
10
19

class TreeNode {
  constructor(data) {
    this.data = data;
    this.children = [];
  }

  addChild(child) {
    if (child instanceof TreeNode) {
      this.children.push(child);
    } else {
      this.children.push(new TreeNode(child));
    }
  }

  removeChild(childToRemove) {
    const length = this.children.length;
    this.children = this.children.filter(child => {
      return childToRemove instanceof TreeNode
      ? child !== childToRemove
      : child.data !== childToRemove;
    });

    if (length === this.children.length) {
      this.children.forEach(child => child.removeChild(childToRemove));
    }
  }

  print(level = 0) {
    let result = '';
    for (let i = 0; i < level; i++) {
      result += '-- ';
    }
    console.log(`${result}${this.data}`);
    this.children.forEach(child => child.print(level + 1));
  }

  depthFirstTraversal() {
    console.log(this.data);
    this.children.forEach(child => child.depthFirstTraversal());
  }

  breadthFirstTraversal() {
    let queue = [ this ];
    while (queue.length > 0) {
      const current = queue.shift();
      console.log(current.data);
      queue = queue.concat(current.children);
    }
  }
};