Binary Tree

이진Tree는 Tree구조 중 Node가 Left와 Right만 갖는 Tree를 의미합니다.

 

Tree에 대한설명은....

(추후 Tree 페이지 추가후 삽입예정입니다)

 

추상화된 Binary Tree

Binary Tree는 각 Node마다 Left, Right를 구분하며, Left 와 Right는 각각 다른 Node를 Pointing하는 구조를 가지고 있습니다.

 

이때 Node C처럼 Left와 Right가 모두 빈 Node를 Leaf Node라고 합니다.

 

이러한 이진 Tree를 구현하는 방법은 Array를 이용한 구현 방법과, Node를 이용한 구현방법이 있습니다.

 

Node와 Array를 활용한 Binary Tree의 구현

두가지 방법 모두 Tree를 구현할 수 있지만, 완전 이진 Tree가 아니면 Array를 활용할 경우 불필요한 Memory가 사용됩니다

 

이러한 Binary Tree는 Binary Search Tree나 Thread Tree, Heap 등과 같은 응용된 자료구조의 기초로 사용됩니다.

 

Python으로 구현된  Binary Tree입니다(Random하게 좌우로 Element를 추가하는 Binary Tree입니다 :) )

import random
import copy
class node:
    def __init__(self, left, value, right):
        self.left = left
        self.value = value
        self.right = right

class tree:
    def __init__(self):
        self.top_node = node(None, None, None)
        #if True, Next add will be occur in left node
        self.tree_depth = 0


    def add(self, element, start_node = 999, node_value = None):
        if start_node == 999:
            start_node = self.top_node                    
        if node_value == None:
            if start_node.value == None:
                start_node.value = element
                return True
            elif start_node.left == None:
                start_node.left = node(None, element, None)
                return True
            elif start_node.right == None:
                start_node.right = node(None, element, None)
                return True
            else:                               
                if bool(random.getrandbits(1)):                
                    self.add(element, start_node.left, node_value)
                else:
                    self.add(element, start_node.right, node_value)
        
        #특정 Node value 이후에 Left Node의 위치에 Node를 삽입
        elif node_value != None:        
            validation = 0
            if start_node != None:
                if start_node.value == node_value:
                    start_node.left = node(start_node.left, element, None)
                    return validation+1
                else:
                    if start_node.left != None:
                        validation = self.add(element, node_value, start_node.left) + validation
                    if start_node.right != None:
                        validation = self.add(element, node_value, start_node.right) + validation
            return True if validation !=0 else False


	#지정된 Element가 있을경우 Value를 Tree에서 삭제
	def delete(self, node_value, start_node = 999):
        if start_node == 999:
            start_node = self.top_node                    
        validation = 0        
        if start_node != None and start_node.left != None:            
            if start_node.left.value == node_value:
                if start_node.left.left == None:
                    if start_node.left.right!=None:
                        start_node.left = start_node.left.right
                    elif start_node.left.right == None:
                        start_node.left = None
                else:
                    start_node.left = start_node.left.left
                return validation+1
        
        elif start_node != None and start_node.right != None:            
            if start_node.right.value == node_value:
                if start_node.right.left == None:
                    if start_node.right.right != None:
                        start_node.right = start_node.right.right
                    elif start_node.right.right == None:
                        start_node.right = None
                else:
                    start_node.right = start_node.right.left
                return validation+1
        if start_node.left != None:
            validation = self.delete(node_value, start_node.left) + validation
        if start_node.right != None:
            validation = self.delete(node_value, start_node.right) + validation
        return True if validation !=0 else False


    def count_node(self, start_node=999):        
        if start_node == 999:
            start_node = self.top_node
        if start_node==None:
            node_count = 0
        else:
            node_count = 1
        if start_node.left != None:
            node_count = self.count_node(start_node.left) + node_count
        if start_node.right != None:
            node_count = self.count_node(start_node.right) + node_count
        return node_count
    
    
    def count_leaf_node(self, start_node=999):               
       if start_node == 999:
           start_node = self.top_node       
       if start_node.right==None and start_node.left == None:
           leaf_node_count = 1           
       else:
           leaf_node_count = 0
       if start_node.left != None:
           leaf_node_count = self.count_leaf_node(start_node.left) + leaf_node_count
       if start_node.right != None:
           leaf_node_count = self.count_leaf_node(start_node.right) + leaf_node_count
       return leaf_node_count               


    def max_depth_cal(self,current_depth = 0, start_node = 999):               
        if start_node == 999:
           start_node = self.top_node               
        if start_node.left == None and start_node.right == None:            
            if self.tree_depth<current_depth:
                self.tree_depth = current_depth    
            return -1                        
        else:
            current_depth = current_depth +1 
        current_depth_for_right = copy.deepcopy(current_depth)
        if start_node.left != None:
            self.max_depth_cal(current_depth,start_node.left)        
        if start_node.right != None:
            self.max_depth_cal(current_depth_for_right,start_node.right)    
        return self.tree_depth


    def show(self, start_node = 999):
        if start_node == 999:
           start_node = self.top_node    
        print(start_node.value)
        if start_node.left == None and start_node.right == None:
            print("node end")
        if start_node.left != None:
            print("left")
            self.show(start_node.left)
        else:
            print("left is empty")
        if start_node.right != None:
            print("right")
            self.show(start_node.right)
        else:
            print("right is empty")
            
               

test = [2,0,4,1,3,6,7,5]

test_tree = tree()
for i in test:    
    test_tree.add(i)

test_tree.count_node()
==> 8
test_tree.count_leaf_node()
==> 4
test_tree.max_depth_cal()
print(test_tree.tree_depth)
==> 3
test_tree.show()
==> 
2
left
0
left
1
node end
left is empty
right is empty
right
5
node end
left is empty
right is empty
right
4
left
3
node end
left is empty
right is empty
right
6
left
7
node end
left is empty
right is empty
right is empty
'''
위 결과로부터 추상화된 Binary Tree
   2
  / \
 0   4 
/ \ / \
1 5 3 6
     /
    7
'''