[JAVA/자료구조] 강의노트 4강 : 트리(Tree) 기본개념,Operation : Node구현+Tree구현

---

안녕하세요. 오늘은 Tree에 대하여 공부해보고자 합니다.

Tree는 파생되는 자료구조가 많기 때문에, 이번 시간엔 트리의 기본 개념에 대하여 알아보겠습니다.

 

1) What is a Tree

Tree는 이때까지 배웠던 자료구조와는 다른 계층적 자료구조입니다.

제 블로그 카테고리를 트리로 표현한다면 위와 같은 형태가 될 것입니다.

자료 간 계층구조(상하관계)를 가지고 있는 것을 확인할 수 있습니다.

이 계층구조에서 상위계층에 존재하는 자료를 그 하위계층의 parent라고 표현합니다.

반대의 경우는 children이라고 표현합니다.

즉, '개발노트&IT'는 'C++', 'JAVA', '블로그'의 parent이며, 'C++'은 '개발노트&IT'의 children입니다.

또한 최상위 parent를 root라고 표현하며, 최하위 children을 leaf라고 표현합니다.

parent - children의 관계에서,

parent는 다수의 children을 가질 수 있지만, children은 하나의 parent와만 연결되어야 합니다.

 

2) Tree Teminology

- Internal node : 적어도 하나의 child를 가지고 있는 node

예) 'XD_Diary', '개발노트&IT', '대학생활', '대외활동'

- External node(a.k.a Leaf) : children을 가지고 있지 않는 node

 예) 'GIS', 'C++', 'JAVA', '블로그', 'CJ', 'JA'

- SubTree : 트리가 포함하고 있는 노드 중 하나를 루트로 가지면서 파생되는 트리

- Ancestor of a node : 트리의 조상

('CJ' - '대외활동' - '대학생활' - 'XD_Diary')

- Descendant of a node : 트리의 자손 (Ancestor of a node의 역)

---

- Edge : 부모-자식의 관계로 묶여있는 pair of node

예) ('대학생활', '대외활동'), ('XD_Diary', 'GIS')

- Path : 가장자리에 위치한 노드까지 도달하는 경로

예) ('XD_Diary' - '대학생활' - '대외활동' - 'CJ')

- Depth of a node : root까지의 조상의 수 -1

* Depth of the root = 0

- Level : 같은 depth에 위치한 노드 집합

예) Level1: 'GIS', '개발노트&IT', '대학생활'

- Height 

Height of a node : external node까지의 depth의 최대치

Height of a node = Height of the tree 

- Degree

Degree of a node : node가 가지고 있는 children의 수

Degree of a tree : 모든 노드 중에서의 degree의 최대치

 

3) Tree Operations

- integer size()

- boolean isEmpty() 

- list nodes() 

- list elements()

- node root() - root node를 선언합니다.

- node parent(node v) - node v의 parent node를 선언합니다

- list children(node v) - node v의 children을 선언합니다.

- boolean isInternal(node v) - node v가 Internal한지 판단합니다.

- boolean isExternal(node v) - node v가 External한지 판단합니다.

- boolean isRoot(node v) - node v가 Root인지 판단합니다.

- object replace(node v, object e) - node v의 object를 e로 바꿉니다.

 

tree의 종류가 여러가지이기에, 오늘은 tree의 기본개념만 살펴보았습니다.

다음시간에는 children을 2개까지만 소유할 수 있는 binary tree에 대하여 알아보겠습니다.

 

4)  Node 구현

JAimport java.util.ArrayList;
 
public class MyNode {
    
    private Object element;
    private MyNode parent;
    private ArrayList children;
    
    public MyNode() {
        this.element = null;
        this.parent = null;
        this.children = null;
    }
    
    public MyNode(Object e) {
        this.element = e;
        this.parent = null;
        this.children = new ArrayList();
        this.children.add(null);
        this.children.add(null);        
    }
    
    public Object element() {
        return this.element;
    }
    
    public MyNode parent() {
        return this.parent;
    }
    
    public ArrayList children() {
        return this.children;
    }
    
    public int degree() {
        return this.children.size();
    }
    
    public void setElement(Object e) {
        this.element = e;
    }
    
    public void setParent(MyNode p) {
        this.parent = p;
    }
    
    public void setChildren(ArrayList c) {
        this.children = c;
    }
 
}
 

 

5) Tree 구현

import java.util.ArrayList;
 
public class MyTree {
    
    private MyNode root;
    private int totalSize;
    
    public MyTree() {
        this.root = null;
        this.totalSize = 0;        
    }
    
    public MyTree(Object e) {        
        this.root = new MyBinNode(e);                    
        this.totalSize = 1;
    }
    
    public int size() {
        return this.totalSize;
    }
    
    public MyNode root() {
        return this.root;
    }
    
    public ArrayList children(MyNode v) {
        return v.children();
    }
    
    public boolean isExternal(MyNode v) {
        return v.children().isEmpty();
    }
    
    public MyNode addRoot(Object e) {
        MyNode temp = this.root;
        this.root = new MyBinNode(e);            
        this.totalSize = 1;
        return temp;        
    }
    
    public MyNode addNode(Object e) {
        MyNode newNode = new MyBinNode(e);        
        newNode.setParent(this.root);
        this.root.children().add(newNode);        
        this.totalSize++;
        return newNode;
    }
    
    public MyNode addChild(MyNode v, Object e) {
        MyNode newNode = new MyBinNode(e);    
        newNode.setParent(v);
        v.children().add(newNode);
        this.totalSize++;
        return newNode;
    }
    
    public MyNode addChild(MyNode v, int i, Object e) {
        MyNode newNode = new MyBinNode(e);        
        newNode.setParent(v);
        v.children().add(i, newNode);
        this.totalSize++;
        return newNode;
    }
    
    public MyNode setChild(MyNode v, int i, Object e) {
        MyNode newNode = new MyBinNode(e);        
        newNode.setParent(v);
        v.children().set(i, newNode);
        return newNode;
    }
    
    public MyNode removeChild(MyNode v, int i) {
        this.totalSize--;
        return (MyNode)v.children().remove(i);
    }
 
}