PyBST在Python2中实现了二进制树、AVL树、Splay树和红黑树。此外，PyBST还提供了一个模块，用于使用networkx和matplotlib绘制这些树。
https://pypi.org/project/pybst/
https://github.com/TylerSandman/py-bst
1.pybst的若干准备
在python3中使用，需要做必要的修改。
|
1 2 3 |
pip3 install networkx pip3 install matplotlib pip3 install pybst |
首先，修改文件 "/Library/Frameworks/Python.framework/Versions/3.7/lib/python3.7/site-packages/pybst/draw.py", 21行。
将import bstree as bst 改为import pybst.bstree as bst，或直接 注释掉。
然后，修改文件 "/Library/Frameworks/Python.framework/Versions/3.7/lib/python3.7/site-packages/pybst/bstree.py",196行。
将if not isinstance(key,(int,long, float)): 里的long删除，因为python3中已经没有long类型，可以查找其它有long判断的地方删除。
最后，参考 https://www.cnblogs.com/harrychinese/p/binary_tree_visualization.html 在bstree.py中，为BSTree类，添加3个方法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
def get_node_for_normal_binary_tree(self, key, *args): """ 修改自T.get_node(key,...) -> Node。 获得一个普通的节点。 """ 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_normal_binary_tree(key, start.right) if node: return node else: node = self.get_node_for_normal_binary_tree(key, start.left) return node def insert_right(self, key, value, *args): """ 指定 作为右侧子节点插入 """ if not isinstance(key,(int,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): """指定 作为左侧子节点插入 """ if not isinstance(key,(int,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) |
2.可视化示例
pybst的相关方法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
is_valid() ->如果树是其类型的有效树，则生成True，否则生成False。 preorder() ->前序遍历。 inorder() ->中序遍历。 postorder() ->后序遍历。按后序法生成树中的节点序列。 levelorder() ->层次遍历（广度优先-横向优先）。按层生成一系列节点。 get_node(key) ->提取树中属性为key的节点。 insert(key,val) <=>Tree[key]=value。 ->将键属性为key和值属性为val的新节点插入到树中。 insert_from(seq) ->将seq[(key1，val1)，(key2，val2)，…，(keyn，valn)]中的键和值插入到树中。 get_max() <=>max(Tree)。 ->提取树中最右分支的节点，而不是值最大的。 get_min() <=>min(Tree)。 ->提取树中最左分支的节点，而不是值最小的。 get_element_count() <=>len(Tree)。 ->提取树中的元素数。 get_height() ->提取树的高度，根节点不计在内。 delete(key) <=>del Tree[key]。 ->从树中删除具有属性key的节点。 delete_from(seq) ->从树中删除带有seq[key1，key2，…，keyn]中的键的节点。 plot_tree(tree) ->通过使用networkx和matplotlib打印树，提供树的可视化表示。 # 自加入的3个方法 get_node_for_normal_binary_tree(key) ->作为普通节点返回 insert_right(key, value, parent_node) ->插入右子节点 insert_left(key, value, parent_node) ->插入左子节点 |
示例一个元素为1-7的可视化：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
from pybst.bstree import BSTree from pybst.draw import plot_tree class Node: def __init__(self, item, left=None, right=None): self.item = item self.left = left self.right = right ''' 二叉树： 1 2 3 4 5 6 7 ''' class Tree: def __init__(self): self.__root = None def add(self, *items): # 向二叉树添加元素。多个 for i in items: self.__add(i) def __add(self, item): # 向二叉树添加元素 node = Node(item) if not self.__root: self.__root = node self.__btree = BSTree() self.__btree.insert(self.__root.item, 'Root') # 根节点 return breadth = [self.__root] while len(breadth) > 0: current = breadth.pop(0) btree_parent = self.__btree.get_node_for_normal_binary_tree(current.item) if not current.left: current.left = node self.__btree.insert_left(current.left.item, '', btree_parent) return else: breadth.append(current.left) if not current.right: current.right = node self.__btree.insert_right(current.right.item, '', btree_parent) return else: breadth.append(current.right) def breadth_travel(self): # 二叉树广度优先遍历-横向遍历-层级遍历 if not self.__root: print("Empty") return print(self.__root.item, end="\t") breadth = [self.__root] while len(breadth) > 0: current = breadth.pop(0) if current.left: print(current.left.item, end="\t") breadth.append(current.left) if current.right: print(current.right.item, end="\t") breadth.append(current.right) print() print("最右：", self.__btree.get_max().key) # 提取树中最右边的节点。 print("最左：", self.__btree.get_min().key) # 提取树中最左边的节点。 print("节点数量：", self.__btree.get_element_count()) # 提取树中的元素数 print("树高：", self.__btree.get_height()) # 树深度还要+1 plot_tree(self.__btree) tree = Tree() tree.add(1, 2, 3, 4, 5, 6, 7) tree.breadth_travel() # 1 2 3 4 5 6 7 # 最右： 7 # 最左： 4 # 节点数量： 7 # 树高： 2 |
- end
声明
本文由崔维友 威格灵 cuiweiyou vigiles cuiweiyou 原创，转载请注明出处：http://www.gaohaiyan.com/2867.html
承接App定制、企业web站点、办公系统软件 设计开发，外包项目，毕设
