프로그래밍 면접 이렇게 준비한다. - 3. 트리

1. 구현방법

 - 트리는 0개 이상의 다른 노드에 대한 레퍼런스(또는 포인터)가 들어있는 노드(데이터 원소)로 구성된다.

 - 연결 리스트에서와 마찬가지로 노드는 구조체 또는 클래스로 표현되며, 트리는 포인터 또는 레퍼런스만 있다면 어떤 언어로든 구현할 수 있다

public abstract class Node {

private Node[] children;

public Node(Node[] children){

this.children = children;

}

public int getNumChildren(){

return children.length;

}

public Node getChild(int index){

return children[index];

}

}

public class IntNode extends Node{

private int value;

public IntNode(Node[] children, int value){

super(children);

this.value = value;

}

public int getValue(){

return value;

}

}

 

 - 이 클래스에서 이 노드는 참조하는 모든 노드를 children이라는 배열에 저장한다.

 - 오류 처리 부분도 생략했고 노드를 동적으로 추가하거나 삭제할 수 없기 때문에 이 코드는 아직 제대로 구색을 갖췄다고 할 수 없다. 면접관에게 어느 코드를 어느 정도로 자세하게 작성해야 할지 물어보고 그 수준에 맞춰서 코드를 설계하면 된다. 면접관이 별다른 가이드라인을 제시하지 않는다면 코드를 작성하면서 어떤 부분을 왜 생략하거나 간략ㅎ게 만들었는지 말로라도 설명하고 넘어가도록 하자.

2. 트리와 관련된 용어들

 - 부모(Parent) : 다른 노드를 가리키는 노드는 그 노드의 부모가 된다. 위 그림에서는 B,C 가 부모노드가 된다.

 - 자식(Child) : 루트를 제외한 모든 노드는 그 노드를 가리키는 노드의 자식이 된다. 그림에서는 D,E가 B의 자식노드가 된다.

 - 자손(Descendant) : 특정 노드로부터 자식 노드로 이어지는 경로를 따라 도달할 수 있는 모든 노드는 그 특정 노드의 자손이다. 그림에서 D,E는 모두 B의 자손이다.

 - 조상(Ancestor) : 어떤 노드를 자손으로 삼고 있는 노드는 모두 그 노드의 조상이다. A,B는 D의 조상이다.

 - 잎(Leaves) : 자식이 없는 노드를 잎이라고 부른다. D,E,F,G는 모두 잎이다.