1주차 과제 - 트리를 이용하여 전위 순회, 중위 순회, 후위 순회를 검색하여 직접 구현해보세요.

 이진 트리 순회 구현 방법

  이번 과제는 이진 트리를 순회하는 로직을 구현하는 것이다. 기본적으로 이진 트리의 경우에는 트리 자료구조가 갖는 규칙에 자식 노드를 최대 2개까지 가질 수 있다는 규칙이 추가된 자료구조이다. 이진 트리를 순회하는 방법으로는 BFS와 DFS 모두 가능하지만 이번 과제에서는 DFS를 활용하여 전위 순회, 중위 순회, 후위 순회를 구현하는 것이다. 

 

  전위 순회와 중위 순회, 그리고 후위 순회를 나누는 기준은 부모 노드를 기준으로 나뉘게 된다. 만약 부모 노드를 가장 먼저 순회한다면 전위 순회가 되는 것이고, 중간에 순회하면 중위 순회, 마지막에 순회하면 후위 순회가 되는 것이다. 내가 구현한 방법은 배열에 순회하는 요소 값들을 차근 차근 push( )해서 마지막에 반환하는 방식으로 순회하는 로직을 구현했다. 

전위 순회, 중위 순회, 후위 순회 기준

  DFS는 조건을 잘 만들어 주는것이 중요하다고 생각하는데 이진 트리 순회를 위한 DFS 재귀 호출을 탈출하는 조건이 까다롭지 않기 때문에 DFS 구현 자체가 어려운것 같지는 않다.(아 물론,, 내가 이전에 작성해 놓았던 DFS 로직을 참고하고 구현하기는 했다.)

 

2022.08.16 - [📚 Language & CS knowledge/Algorithm & Data structure] - 17 트리 순회

17 트리 순회

 

클래스로 이진트리를 구현한 경우

//클래스로 이진트리를 구현한 경우
class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinaryTree {
    constructor(value) {
        this.root = new Node(value);
    }

    preOrder() { // 전위 순회
        let result = [];
        
        function traverse(node) {
            result.push(node.value);
            if(node.left) traverse(node.left);
            if(node.right)traverse(node.right);
        }
        traverse(this.root);
        
        return result;
    }

    inOrder() { // 중위 순회
        let result = [];
        
        function traverse(node) {
            if(node.left) traverse(node.left);
            result.push(node.value);
            if(node.right)traverse(node.right);
        }
        traverse(this.root);
        
        return result;
    }

    postOrder() { // 후위 순회
        let result = [];
        
        function traverse(node) {
            if(node.left) traverse(node.left);
            if(node.right)traverse(node.right);
            result.push(node.value);
        }
        traverse(this.root);
        
        return result;
    }
}

let tree = new BinaryTree(1);
tree.root.left = new Node(3);
tree.root.right = new Node(5);
tree.root.left.left = new Node(7);
tree.root.left.right = new Node(9);
tree.root.right.left = new Node(11);
console.log(tree.preOrder()); // [1, 3, 7, 9, 5, 11]
console.log(tree.inOrder()); // [7, 3, 9, 1, 11, 5]
console.log(tree.postOrder()); // [7, 9, 3, 11, 5, 1]

 

배열로 이진 트리를 구현한 경우
이진 트리의 경우에는 부모 노드는 자식 노드를 최대 2개가지 갖기 때문에 수학적 규칙을 이용하여 배열로 이진 트리를 구현할 수 있다.
let leftChildNode = parentNodeIndex * 2;
let rightChildNode = parentNodeIndex * 2 + 1;
let parentNode = parseInt(childNodeIndex / 2);

//배열로 이진트리를 구현한 경우
let pineTree = [undefined,9,3,8,2,5,undefined,7,undefined,undefined,undefined, 4];

function preOrder(binaryTree) { // 전위 순회
    let result = [];
    function traverse(level) {
        result.push(binaryTree[level]);
        if(binaryTree[level * 2]) traverse(level * 2);
        if(binaryTree[level * 2 + 1]) traverse(level * 2 + 1);
    }
    traverse(1)

    return result;
}

console.log(preOrder(pineTree));

function inOrder(binaryTree) { // 중위 순회
    let result = [];
    function traverse(level){
        if(binaryTree[level * 2]) traverse(level * 2);
        result.push(binaryTree[level]);
        if(binaryTree[level * 2 + 1]) traverse(level * 2 + 1);
    }
    traverse(1)

    return result;
}

console.log(inOrder(pineTree));

function postOrder(binaryTree) { // 후위 순회
    let result = [];
    function traverse(level) {
        if(binaryTree[level * 2]) traverse(level * 2);
        if(binaryTree[level * 2 + 1]) traverse(level * 2 + 1);
        result.push(binaryTree[level]);
    }
    traverse(1)

    return result;
}

console.log(postOrder(pineTree));

https://github.com/WooDaeHyun/Dev_course-first-assignment.git

GitHub - WooDaeHyun/Dev_course-first-assignment