이 진 트 리 의 python 시각 화 및 상용 조작 코드

이 진 트 리 는 중요 한 데이터 구조 입 니 다. 본 고 는 '이 진 트 리 찾기' 의 python 시각 화 pybst 패 키 지 를 바탕 으로 개 조 를 했 습 니 다. 더욱 일반적인 '이 진 트 리' 시각 화 를 지원 할 수 있 습 니 다. 이 진 트 리 와 이 진 트 리 의 개념 과 자주 사용 되 는 조작 과 알고리즘 을 바탕 으로 뒤의 참고 글 을 볼 수 있 습 니 다.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 이 진 트 리 시각 화 패키지 pybst = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
다음 코드 는 dreampie 셸 에서 직접 실행 할 수 있 습 니 다.
 

# demo1:       

#         
from pybst.bstree import BSTree
from pybst.draw import plot_tree

#      
tree=BSTree()

tree.insert(10, '') 
"""
insert()    :       (key 10, value a), key      , value        ,          . 
       parent   ,            parent    ,          .
       ,     insert()        parent   , bst             ,               . 
           ,          ,       ,     get_node()  . 
"""

#   key=10   
parent_node=tree.get_node(10)

#  key=10         ,   bst       ,             parent_node, 
#  3        parent_node     ,          
tree.insert(11, '', parent_node)

#         ,        : 10   11
plot_tree(tree)

 
 

# demo2:          

#      
tree=BSTree()
tree.insert(90, '')

node_90=tree.get_node(90) 
tree.insert(50, '', node_90) 
tree.insert(150, '', node_90)

node_50=tree.get_node(50) 
tree.insert(20, '', node_50) 
tree.insert(75, '', node_50)

node_20=tree.get_node(20) 
tree.insert(5, '', node_20) 
tree.insert(25, '', node_20)

node_75=tree.get_node(75) 
tree.insert(66, '', node_75) 
tree.insert(88, '', node_75)
tree.insert(98, '', node_75) #   98          88   ,    75   .

#         
plot_tree(tree)

 
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
bst 가방 은 자동 으로 '이 진 트 리 찾기' 의 규칙 에 따라 노드 를 배열 합 니 다. 예 를 들 어 key 가 작 으 면 왼쪽 에 놓 고 key 가 많 으 면 오른쪽 에 놓 고 적당 한 부모 노드 를 자동 으로 선택 합 니 다. 그래서 일반적인 이 진 트 리 의 시각 화 를 지원 할 수 없습니다. 저 는 pybst 가방 bstree. py 를 수정 하여 일반적인 이 진 트 리 의 시각 화 를 지원 할 수 있 습 니 다.
binarytree. py 모듈 추가
file bstree. py - > biary tree. py, 최종 적 으로 site - packages \ pybst \ 디 렉 터 리 에 도 넣 습 니 다. class BSTree -- > Binary Tree 및 새로운 Binary Tree 류 에 다음 세 가지 방법 을 추가 합 니 다. 이 방법 들 은 BSTree. get 에서 수정 합 니 다.node () 와 insert () 방법.

    def get_node_for_binary_tree(self,key,*args):
        """
        T.get_node(key,...) -> Node. Produces the Node in T with key
        attribute key. If there is no such node, produces None.
        """
        if len(args) == 0:
            start = self.Root
        else:
            start = args[0]

        if not start:
            return None
        
        if key == start.key:
            return start
        else:        
           node =  self.get_node_for_binary_tree(key, start.right)
           if node:
               return node
           else:
               node =  self.get_node_for_binary_tree(key, start.left)
               return node
   
            

    def insert_right(self,key,value,*args):
        """
        T.insert(key,value...) <==> T[key] = value. Inserts
        a new Node with key attribute key and value attribute
        value into T.
        """
        if not isinstance(key,(int,long,float)):
            raise TypeError(str(key) + " is not a number")
        else:
            if not self.Root:
                self.Root = Node(key,value)
            elif len(args) == 0:
                if not self.get_node_for_binary_tree(key,self.Root):
                    self.insert(key,value,self.Root)
            else:
                child = Node(key,value)
                parent = args[0] 
                if not parent.right:
                    parent.right = child
                    child.parent = parent
                else:
                    self.insert(key,value,parent.right)
                   
                        
    def insert_left(self,key,value,*args):
        """
        T.insert(key,value...) <==> T[key] = value. Inserts
        a new Node with key attribute key and value attribute
        value into T.
        """
        if not isinstance(key,(int,long,float)):
            raise TypeError(str(key) + " is not a number")
        else:
            if not self.Root:
                self.Root = Node(key,value)
            elif len(args) == 0:
                if not self.get_node_for_binary_tree(key,self.Root):
                    self.insert(key,value,self.Root)
            else:
                child = Node(key,value)
                parent = args[0]
                if not parent.left:
                    parent.left = child
                    child.parent = parent
                else:
                    self.insert(key,value,parent.left)                      

일반 이 진 트 리 시각 화 된 TreeNode class 와 util 방법tree_util.py

   
# TreeNode class
class TreeNode(object):
    def __init__(self, key, left=None, right=None):
        self.key=key
        self.left=left
        self.right=right 
        
    def  __str__(self):
        return str(self.key)
    
    
# visualization   
from pybst.binarytree import BinaryTree
from pybst.draw import plot_tree
    
def my_preorder_traverse(tree, node, parent_node, is_left, combine_action):
    print(node) 
    if combine_action:
        combine_action(tree, node, parent_node, is_left)
    if node.left: 
        is_left=True
        my_preorder_traverse(tree, node.left, node, is_left, combine_action)    
    if node.right:
        is_left=False
        my_preorder_traverse(tree, node.right, node, is_left, combine_action)    
    

def my_combine_node(tree, node, parent_node=None, is_left=True):
    if parent_node:
        parent_node_bt=tree.get_node_for_binary_tree(parent_node.key)
        if is_left:
            tree.insert_left(node.key, '', parent_node_bt)
        else:
            tree.insert_right(node.key, '', parent_node_bt)
    else:
        tree.insert(node.key, '') 
    

def my_draw_bt(root_node):
    tree=BinaryTree()
    combine_node=my_combine_node
    #                  bst     tree
    my_preorder_traverse(tree, root_node, parent_node=None, is_left=True, combine_action=combine_node)
    if combine_node:
        plot_tree(tree)

    
#        
root=TreeNode(4,
               TreeNode(2, TreeNode(1), TreeNode(3)),
               TreeNode(7, TreeNode(6), TreeNode(8))             
              ) 
my_draw_bt(root) 


root=TreeNode(4,
               TreeNode(7, TreeNode(8), TreeNode(6)),
               TreeNode(2, TreeNode(3), TreeNode(1))              
              ) 
my_draw_bt(root) 

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

# reverse
def reverse(node):
    if node:
       node.left, node.right=node.right, node.left
       if node.left:
           node.left=reverse(node.left)
       if node.right:
           node.right=reverse(node.right)
    return node
   

#   revese
root=TreeNode(4,
               TreeNode(2, TreeNode(1), TreeNode(3)),
               TreeNode(7, TreeNode(6), TreeNode(8))             
              ) 
my_draw_bt(root) 
root=reverse(root)
my_draw_bt(root) 

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

def preorder(node):
    print(node) 
    if node.left:
        preorder(node.left)
    if node.right:
        preorder(node.right)

def inorder(node):
    if node.left:
        inorder(node.left)
    print(node)
    if node.right:
        inorder(node.right)

def postorder(node):
    if node.left:
        postorder(node.left)
    if node.right:
        postorder(node.right)
    print(node)

              
#   revese
root=TreeNode(4,
               TreeNode(2, TreeNode(1), TreeNode(3)),
               TreeNode(7, TreeNode(6), TreeNode(8))             
              ) 
my_draw_bt(root) 
preorder(root) 
inorder(root) 
postorder(root) 
              

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

def find(node, key):    
    if node:
        if node.key==key:
            return node
        elif key<node.key:
            return find(node.left,key)
        else:
            return find(node.right,key)        
    return node

    
def find_min(node):    
    if node:
        if node.left:
            return find_min(node.left)
        else:
            return node
    else:
        return None
        
def find_max(node):
    if node:
        if node.right:
            return find_max(node.right)
        else:
            return node
    else:
        return None

#     
root=TreeNode(4,
               TreeNode(2, TreeNode(1), TreeNode(3)),
               TreeNode(7, TreeNode(6), TreeNode(8))             
              )       
node=find(root, 3) 
node=find(root, 500) 

find_min(root)
find_max(root)

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 참고 문헌: 이 진 트 리 의 개념 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =http://hujiaweibujidao.github.io/python/ 파 이 썬 알고리즘 서론 이 라 고 할 수 있 습 니 다.https://www.the5fire.com/python-invert-binary-tree.html 그 유명한 면접 문제,반전 이 진 트 리 의 python 버 전http://www.cnblogs.com/gaochundong/p/binary_search_tree. html, 각종 이 진 트 리 의 개념, 그리고 이 진 트 리 에서 찾 은 추가 삭제 와 옮 겨 다 니 기http://btv.melezinek.cz/binary-search-tree.html 웹 페이지 에 이 진 트 리 를 시각 적 으로 표시 하 는 여러 가지 알고리즘http://www.i3geek.com/archives/702 이 진 트 리 - 이 진 트 리 의 증가, 삭제, 검색http://www.cnblogs.com/hlxs/archive/2010/11/19/2087987.html 두 갈래 찾기 트 리 만 들 기,이 진 트 리 의 특정한 노드 를 찾 고 특정한 노드 를 삭제 하 며 노드 를 추가 하고 특정한 노드 의 부모 노드 를 찾 습 니 다. 최소 노드 를 찾 아 이 진 트 리 에 대해 앞 순 서 를 옮 겨 다 니 고 중간 순 서 를 옮 겨 다 니 며 뒤 순 서 를 찾 습 니 다.