[JAVA/자료구조] 강의노트 4-1강 : 이진트리(Binary Tree) 구현, Remove, insertLeft, insertRight, attach

안녕하세요. 오늘은 저번시간에 배운 Tree를 바탕으로 Binary Tree를 공부해보고자 합니다.

---

!) 자료구조 Tree를 잘 모르시다면?

Tree 개념설명 보러가기

---

1) What is BT

Binary Tree(이진트리)는 자식을 최대 2개까지만 가질 수 있는 Tree를 말합니다.

이진트리에서 자식은 left를 첫 번째로 하여, left child와 right child로 나누어 생각합니다.

위 그림을 살펴보면 'E'의 left child에 'G'가 위치하고 있습니다.

만약 'G'가 right child에 위치하고 있다고 생각하면 이전과 완전히 다른 트리가 되는 것입니다.

 

2) BT Teminology

- Left subtree : 루트의 왼쪽에 위치하고 있는 child 중 internal node를 root로 하는 파생되는 트리

- Right subtree : 루트의 오른쪽에 위치하고 있는 child 중 internal node를 root로 하는 파생되는 트리 

- Proper binary tree : 각각의 노드가 0혹은 2개의 자식을 가지고 있는 트리

- Inproper binary tree : proper 하지 않은 BT

- Skewed tree : BT의 자식이 한쪽방향으로만 존재하는 트리

 

3) BT Operations

- node left(node v)

- node right(node v) 

- boolean hasLeft(node v)

- boolean hasRight(node v)

- integer getDepth(node v)

- integer getHeight(node v)

- node addRoot(object e)

- node addNode(object e)

- node insertLeft(node v, object e)

- node insertRight(node v, object e)

- object remove(node v) : exception, if node v has two children

- attach(node v, T1, T2) : exception, if node v is not external

각 opveration에 대한 설명은 밑의 두 그림을 참고해주시길 바랍니다.

BT Creation Example

Remove Operation Example

 

4) BT 구현

---

'Tree + Node'코드 보러가기

---

BinNode

 
public class MyBinNode extends MyNode {
    // 0 : left, 1 : right
    
    MyBinNode(){        
        super();
    }
    
    MyBinNode(Object e){
        super(e);                            
    }
    
    public MyBinNode left( ) {
        return (MyBinNode)super.children().get(0);
    }
    
    public MyBinNode right() {        
        return (MyBinNode)super.children().get(1);        
    }
    
    public void setLeft(MyBinNode v) {
        super.children().set(0, v);        
    }
    
    public void setRight(MyBinNode v) {
        super.children().set(1, v);        
    }
 
}
 

 

Binary Tree

---

Tree Traversal 설명보러가기

---

 
public class MyBinTree extends MyTree {
    
    MyBinTree(){
        super();
    }
    
    MyBinTree(Object e){
        super(e);                            
    }
    
    public boolean isEmpty() {
        return super.size() == 0;
    }
    
    public boolean isRoot(MyBinNode v) {
        return v.parent() == null;
    }
    
    public boolean isInternal(MyBinNode v) {
        return !this.isExternal(v);        
    }
    
    public boolean isExternal(MyBinNode v) {
        if(!this.hasLeft(v) && !this.hasRight(v))
            return true;
        else
            return false;
    }
    
    public MyBinNode root() {        
        return (MyBinNode)super.root();
    }
    
    public MyBinNode parent (MyBinNode v) {
        return (MyBinNode)v.parent();
    }
    
    public MyBinNode left (MyBinNode v) {
        return (MyBinNode)v.children().get(0);
    }
    
    public MyBinNode right (MyBinNode v) {
        return (MyBinNode)v.children().get(1);
    }
    
    public boolean hasLeft (MyBinNode v) {        
        return v.children().get(0) != null;
    }
    
    public boolean hasRight (MyBinNode v) {        
        return v.children().get(1) != null;
    }
    
    public MyBinNode addRoot (Object e) {        
        return (MyBinNode)super.addRoot(e);                    
    }
    
    public MyBinNode inserLeft(MyBinNode v, Object e) {
        
        MyBinNode mbn = null;
        
        if(!this.hasLeft(v)) {            
            mbn = (MyBinNode)super.setChild(v, 0, e);            
        }
        
        return mbn;
    }
    
    public MyBinNode inserRight(MyBinNode v, Object e) {        
        
        MyBinNode mbn = null;
        
        if(!this.hasRight(v)) {
            mbn = (MyBinNode)super.setChild(v, 1, e);            
        }
        
        return mbn;        
    }
    
    public MyBinNode addNode (Object e) {
                    
        MyBinNode return_node = null;
                                                
        if(hasLeft((MyBinNode)super.root()) && hasRight((MyBinNode)super.root())) {
            // 2 children exist
            System.out.println("Can't add Node because Two Children exist !");
        }
        else if(hasLeft((MyBinNode)super.root())) {            
            // left children exist - addNode to right                                                                                    
            return_node =  this.inserRight((MyBinNode)super.root(), e);
        }
        else if(hasRight((MyBinNode)super.root())){
            // right children exist - addNode to left                                                                                        
            return_node =  this.inserLeft((MyBinNode)super.root(), e);
        }
        else {
            // children is empty            
            return_node =  this.inserLeft((MyBinNode)super.root(), e);
        }
        
        return return_node;
    }
    
    public Object replace(MyBinNode v, Object e) {
        Object temp = v.element();
        v.setElement(e);
        return temp;
    }
    
    public MyBinNode remove(MyBinNode v) throws TwoChildrenException {
        
        MyBinNode parent = (MyBinNode)v.parent();
        
        int idx = 0;
        
        if(this.left(parent) == v) {
            // v가 parent의 leftNode
            idx = 0;
        }
        else {
            // v가 parent의 rightNode
            idx = 1;
        }
        
        if(this.hasLeft(v) && this.hasRight(v)) {
            // two children
            throw new TwoChildrenException("TwochildException!!");
        }
        else if(this.hasLeft(v)) {
            // one children - left            
            MyBinNode children = (MyBinNode)v.children().get(0);
            parent.children().set(idx, children);
            children.setParent(parent);                            
        }
        else if(this.hasRight(v)) {
            // one children - right
            MyBinNode children = (MyBinNode)v.children().get(1);            
            parent.children().set(idx, children);
            children.setParent(parent);                    
        }
        else {
            // no children            
            parent.children().set(idx, null);                
        }        
            
        return v;
    }
    
    public void attach (MyBinNode v, MyBinNode t1, MyBinNode t2) throws NotExternalException{
        
        if(this.isExternal(v)) {
            this.inserLeft(v, t1.element());
            this.inserRight(v, t2.element());
        }
        else {
            throw new NotExternalException("NotExternalException !!");
        }
        
    }
    
    public void preOrder(MyBinNode v) {
        
        System.out.print(v.element()+" ");
        
        if(this.hasLeft(v))
            preOrder(this.left(v));
        
        if(this.hasRight(v))
            preOrder(this.right(v));
        
        
    }
    
    public void inOrder(MyBinNode v) {
        
        if(this.hasLeft(v)) {
            System.out.print("(");
            inOrder(this.left(v));
        }
                    
        System.out.print(v.element()+"");        
        
        if(this.hasRight(v)) {
            inOrder(this.right(v));
            System.out.print(")");
        }
        
    }
    
    
    public void postOrder(MyBinNode v) {
        
        if(this.hasLeft(v)) {
            System.out.print("(");
            inOrder(this.left(v));
        }
                        
        if(this.hasRight(v)) {
            inOrder(this.right(v));
            System.out.print(")");
        }
        
        System.out.print(v.element()+"");    
    }
    
    
    class TwoChildrenException extends Exception {
        
        TwoChildrenException(String msg){
            super(msg);
        }
        
    }
    
    class NotExternalException extends Exception {
        
        NotExternalException(String msg){
            super(msg);
        }
    }
 
}