二叉树是一个重要的数据结构, 本文基于"二叉查找树"的python可视化 pybst 包, 做了一些改造, 可以支持更一般的"二叉树"可视化. 关于二叉树和二叉查找树的概念以及常用操作和算法基础, 可以看后面的参考文章.
===================================二叉查找树可视化包 pybst ===================================pypi 有一个"二叉查找树"的可视化的package, 是 pybst 包, 该包依赖 matplotlib 和 networkx, 所以推荐在 Anaconda 发行版上安装.以下代码可以直接在 dreampie shell中执行
# demo1: 简单测试示例# 导入指定类和函数from pybst.bstree import BSTreefrom 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 和 11plot_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 classclass 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 BinaryTreefrom 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)
# reversedef 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 # 测试reveseroot=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) # 测试reveseroot=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