[Data Structure] Tree - Linked List로 표현하기

Tree를 Linked List로 표현하기

---

• 리스트로 트리를 표현한 방법과 다르게 위의 방법은 Node와 Reference를 이용한다. -> 즉 Linked List로 표현

• 중요한 것은 Left, right는 다른 Binary Tree instance를 참조한다는 점이다.

• 예를들면, 우리가 새로운 Left Child를 트리에 추가 할 때, 우리는 또다른 BinaryTree instance를 생성하고, root의 self.leftchild를 새 tree의 Reference로 지정한다.

• 리스트로 tree를 만들었을 때와 마찬가지로 Left Child를 추가할 때, Left Child가 없으면 그냥 root에 node를 넣으면 되고 만약 Left Child가 있다면 원래 Node를 한 레벨 낮추고 새 Node instance를 생성 후, 새 Node의 Left Child를 기존의 Node로 지정해준다 그리고 나서 Root Node의 Left Child를 새 Node로 지정해 주는 방식이다.

• insertRight도 마찬가지로 동작한다.

class BinaryTree:
    
    def __init__(self, rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None
        
    def insertLeft(self, newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t
            
    def insertRight(self, newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t
            
    def getRightChild(self):
        return self.rightChild
    
    def getLeftChild(self):
        return self.leftChild
    
    def setRootVal(self, obj):
        self.key = obj
    
    def getRootVal(self):
        return self.key

r = BinaryTree('a')
print(r.getRootVal())
print(r.getLeftChild())
r.insertLeft('b')
print(r.getLeftChild())
print(r.getLeftChild().getRootVal())
r.insertRight('c')
print(r.getRightChild())
print(r.getRightChild().getRootVal())
r.getRightChild().setRootVal('hello')
print(r.getRightChild().getRootVal())
​
#결과
​
a
None
<__main__.BinaryTree object at 0x7f77d00e15c0>
b
<__main__.BinaryTree object at 0x7f77d00e1b00>
c
hello

Exercise

Write a function buildTree that returns a tree using the list of lists functions that looks like this:

def buildTree():
    r = BinaryTree('a')
    r.insertLeft('b')
    r.getLeftChild().insertRight('d')
    r.insertRight('c')
    r.getRightChild().insertLeft('e')
    r.getRightChild().insertRight('f')
    
    return r
​
ttree = buildTree()

#test
​
print(ttree.getRightChild().getRootVal() == 'c') #True
print(ttree.getLeftChild().getRightChild().getRootVal() == 'd') #True
print(ttree.getRightChild().getLeftChild().getRootVal() == 'f') #False