文章出處

 二叉樹是一個重要的數據結構, 本文基于"二叉查找樹"的python可視化 pybst 包, 做了一些改造, 可以支持更一般的"二叉樹"可視化. 關于二叉樹和二叉查找樹的概念以及常用操作和算法基礎, 可以看后面的參考文章.


===================================
二叉查找樹可視化包 pybst
===================================
pypi 有一個"二叉查找樹"的可視化的package, 是 pybst 包, 該包依賴 matplotlib 和 networkx, 所以推薦在 Anaconda 發行版上安裝.

以下代碼可以直接在 dreampie shell中執行

 

# 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)

 

===================================
讓 pybst 包支持普通二叉樹
===================================

因為 bst 包自動會按照"二叉查找樹"的規則排列節點, 比如key小的話, 會放在左邊, key多的話, 會放在右邊, 也會自動選擇合適的父節點.
所以不能支持普通的二叉樹的可視化, 我對 pybst 包 bstree.py 做了修改, 可以支持普通的二叉樹的可視化.

-----------------------------------
增加 binarytree.py 模塊
-----------------------------------

file bstree.py -> binarytree.py , 最終也放到 site-packages\pybst\ 目錄下.
class BSTree --> BinaryTree
并為新的 BinaryTree 類增加下面 3 個方法, 這些方法修改自 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 方法
-----------------------------------
# 文件名 binary_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
===================================

# 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/ , 很全面,可以算作是 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
創建二叉查找樹、查找二叉樹中的某個節點、刪除某個節點、
新增節點、查找某個節點的父節點、查找最小節點
對二叉樹進行前序遍歷、中序遍歷、后序遍


文章列表


不含病毒。www.avast.com
arrow
arrow
    全站熱搜
    創作者介紹
    創作者 大師兄 的頭像
    大師兄

    IT工程師數位筆記本

    大師兄 發表在 痞客邦 留言(0) 人氣()