트리(Tree)

사실 중요한건 이진탐색트리다. 책에도 이진탐색트리만 나온다. 이진 탐색트리에 대한 완벽한 이해와 활용이 이번학기 자료구조 및 알고리즘 최종목표 중 하나다.

그전에 나에겐 한가지 문제가 있다. 자료구조와 재귀가 머리속에서 바로 연상되지 않는다. 요문제를 트리를 공부하며 꼭 해결해보자! 일단 다행인건 내가 트리가 뭔지는 안다는 것이다. 복습겸 이진탐색트리를 js로 만들어보자.

function Node(data){
    this.data = data;
    this.left = null;
    this.right = null;
}

Node.prototype.show = function(){
    return this.data
}

function BST(){
    this.root = null;
}

BST.prototype.insert = function(data){
    if(this.root === null){
        this.root = new Node(data)
    }else{
        var current = this.root
        var parent
        while(true){
            //크면 오른쪽
            parent = current
            if(current.data < data){
                current = current.right
                if(current === null){
                    parent.right = new Node(data)
                    break;
                }
            //작으면 왼쪽
            }else{
                current = current.left
                if(current === null){
                    parent.left = new Node(data)
                    break;
                }
            }
        }
    }
}

var bst = new BST()

BST에는 전위,중위,후위라는 세가지 탐색방법이 있다(.....?..뭐??)

• 전위탐색에서는 먼저 루트노드를 방문한다음 루트의 왼쪽자식을 중심으로 서브트리를 같은방식으로 탐색하며(이것은 깊이우선탐색과 같은말 같다.) 마지막으로 루트노드의 오른쪽 자식을 중심으로 서브트리를 탐색한다.

function preOrder(node){
    if(node !== null){
        console.log(node.data)
        preOrder(node.left)
        preOrder(node.right)
    }
}

• 중위탐색은 노드의 오름차순 키값으로(즉 젤왼쪽부터 올라옴) BST클래스의 모든 노드를 탐색한다. 재귀를 쓰는군요 역시

function inOrder(node){
    if(node !== null){
        inOder(node.left)
        console.log(node.data)
        inOrder(node.right)
    }
}
//역시 재귀가 잘 안떠오른다. 피보나치때랑 비슷한느낌.

• 후위탐색은 루트노드의 왼쪽자식을 중심으로 서브트리를 먼저방문한 다음 루트노드의 오른쪽자식을 중심으로하는 서브트리를 방문하며 마지막으로 루트노드를 방문한다.? 존나 하나도 이해안됨.

function postOrder(node){
    if(node !== null){

        preOrder(node.left)
        preOrder(node.right)
        console.log(node.data)
    }
}

대충은 이해함. 낼도 이해하길 하늘에 허락을 구해본다.