이진 트리 (전방순회)_BST _ Python

- Python 으로 이진트리를 구현하는 방법이다.

- 우선 큰 BST라는 나무를 만들기 전에 작은 잎가지 (Node) 클래스를 구현해주자.(하나 하나씩 따라가자.)

class Node:
	def __init__(self,data):
    	self.data=data
        self.left = None
        self.right =None

- 그 다음, BST를 구현해줄 건데, BST 클래스를 구현해준다음. __init__ data 에 root값을 지정해주자. 이 root 값을 기준으로 값들이 insert 혹은 remove 될 것이다.

 

- insert 함수를 구현해보자.

# __insert 함수에서는 어떤 node 에다가 더해줄 것인지를 말해준다.
def __insert(self,node,data):	
	# node == None 즉 left -> right -> left -> 이리저리 왔다리 갔다리 하다가 None 인곳에 도착하면,
    # None(data) 클래스를 생성해준다는 의미이다.
    if node == None : 
    	return Node(data)
    # data 가 node.data 값보다 작을때, 왼쪽으로 밀어넣어준다.
    if data < node.data:
    	node.left = self.__insert(node.left,data)
    # data 가 node.data 값보다 클 때, 오른쪽으로 밀어넣어준다. 
    else:
    	node.right = self.__insert(node.right,data)
    return node
    
# insert 함수에서는 root 함수부터 차례대로 값을 찾아갈 수록 root함수로 node 를지정해준다.
def insert(self,data):
	self.root = self.__insert(self.root,data)

 

-inorder 함수를 구현해보자 . inorder 함수는 전위 순회로 구현하였다.

# inorder 순회를 구현해준다.
def __inorder(self,node):
	if node == None : return
    # 왼쪽부터 순회를 돌린다.
   	self.__inorder(sel.left)
    # 왼쪽을 모두 순회 하였으면, data 값 뽑아주고
    print(self.data, end='')
    # 오른쪽 값 순회
    self.__inorder(self.right)
    
# inorder 는 (root node)뿌리서부터 inorder 을 시킨다.
def inorder(self):
	self.__inorder(self.root)
    return
   	

 

-inorder_successor 는 바꿔야 하는 data 를 나열시켰을때, data 그 다음 으로 오는 값을 말한다.

- 무슨 의미냐하면, __inorder_successor(node.right) 을 실행시켜, data 그 다음에 오는 node 의 위치값을 찾고, data 의 값을 __inorder_successor(node.right).data 로 바꿔주는 역활을 한다.

-여기 이미지를 보게 되면  ,  만약 root node 를 바꾸고 싶다면,

1. 첫번 째로, 바꾸고 싶은 데이터의 node 를 root 부터 left-> right -> 이런식으로 찾아간다.

2. 바꾸고 싶은 data의 값이 들어있는 node 를 찾으면,

3. node 의 inorder_successor 을 찾아 inorder_successor.data 를 바꾸고 싶은 data에다가 넣어 바꿔준다.(그림의 3번 부분)

4. 이제 inorder_successor node 의 data를 지워준다.(4) 왜냐면 inorder_successor 의 데이터를 끌어올려서 더이상 밑의 node 에 있으면 안되기 때문이다.

 

 

- 그외 의 그냥 자식 node 들이 하나씩만 있을땐, 아무거나 끄집어서 끌어올려준다. (그림에서 보면 60 데이터를 지우고 싶다하면, 65를 강제로 끌고 올라온다.)

def __remove(self,node,data):
	if node == None : return node
    
    # data 를 찾아가는 과정
    if data<node.data:
    	node.left = self.__remove(node.left,data)
    elif:
    	node.right = self.__remove(node.right,data)
    
    # data == node.data 일때.
    else:
    	# 오른쪽 leaf 가 남아있을때,
    	if node.left == None:
        	temp = node.right
            node = None
            return temp
        # 왼쪽 leaf 가 남아있을때,
        elif node.right == None:
        	temp = node.left
            node = None
            return temp
        # 둘다 node 가 있을 때, inorder_successor 을 이용해서 구해준다.
        temp = __inorder_successor(node.right)
        node.data = temp.data
        # node의 오른쪽 부분에 해당하는 곳에 temp.data를 지우기 위한 반복문을 시행한다.
        node.right = self.__remove(node.right,temp.data)
        
   	return node

---

- 자 이제 전체 code 구현이다.

class Node: 
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None
    
    def __insert(self,node,data):
        if node == None:
            return Node(data)
        if data<node.data:
            node.left = self.__insert(node.left, data)
        else:
            node.right = self.__insert(node.right,data)
        return node
    
    def insert(self, data):
        self.root = self.__insert(self.root,data)

    def __inorder(self, node):
        if node == None: return
        self.__inorder(node.left)
        print(node.data, end = "")
        self.__inorder(node.right)

    def inorder(self):
        self.__inorder(self.root)
        return

    # inorder_successor 는 인오더 순회하였을시 , 바로 다음에 오는 값을 말한다.
    def __inorder_successor(self, node):
        p = node
        while p.left != None: p = p.left
        return p

    def __remove(self, node, data):
        if node == None: return node
        if data<node.data:
            node.left = self.__remove(node.left, data)
        elif data>node.data:
            node.right = self.__remove(node.right, data)
        #data ==node.data 에 도달하였을시 else문 실행.
        else:
            # 만약 left 가 비워져있다면, 오른쪽에 있는 node가 그대로 이어져 올라온다.
            if node.left == None:
                temp = node.right
                node = None
                return temp
            # 만약 right 이 비워져있다면, 왼쪾에 있는 node 가 그대로 이어져 올라온다.
            elif node.right == None:
                temp = node.right
                node = None
                return temp
            # 둘다 해당이 안되었을시. 즉 node 가 left , right 꽉차있을때  혹은 비워져있을때,
            temp = self.__inorder_successor(node.right)
            node.data = temp.data
            node.right = self.__remove(node.right, temp.data)

        return node
    
    def remove(self,data):
        self.root = self.__remove(self.root,data) 
    
bst= BST()
bst.insert(5)
bst.insert(2)
bst.insert(8)
bst.insert(4)
bst.insert(1)
bst.insert(6)
bst.insert(9)
bst.inorder()
print()

bst.remove(2)
bst.inorder()
print()

bst.remove(5)
bst.inorder()
print()

구현 한 모습