用用Python实现二叉树、二叉树非递归遍历及绘制的例子实现二叉树、二叉树非递归遍历及绘制的例子
今天小编就为大家分享一篇用Python实现二叉树、二叉树非递归遍历及绘制的例子,具有很好的参考价值,希
望对大家有所帮助。一起跟随小编过来看看吧
前言前言
关于二叉树的实现与遍历,网上已经有很多文章了,包括C, C++以及JAVA等。鉴于python做为脚本语言的简洁性,这里写
一篇小文章用python实现二叉树,帮助一些对数据结构不太熟悉的人快速了解下二叉树。本文主要通过python以非递归形式实
现二叉树构造、前序遍历,中序遍历,后序遍历,层次遍历以及求二叉树的深度及叶子结点数。其他非递归形式的遍历,想必
大多人应该都很清楚,就不再声明。如果你用C或者C++或者其他高级语言写过二叉树或者阅读过相关方面代码,应该知道二
叉树的非递归遍历避不开通过栈或者队列实现。是的,python也一样。但是python自带的list功能很强大,即可以当stack 又可
以当成queue。 这样用python实现二叉树就可以减少了对栈或者队列的声明及定义。
实现实现
二叉树的结点的实现二叉树的结点的实现
如上图1的的二叉树,要想实现二叉树。首先应该先声明一个二叉树结点,包括它的元素及左右子结点,这个在C/C++也是一
样的。在python里, 可以通过类声明一个结点,如下:
class BiNode(object):
"""class BiNode provide interface to set up a BiTree Node and to interact"""
def __init__(self, element=None, left=None, right=None):
"""set up a node """
self.element = element
self.left = left
self.right = right
def get_element(self):
"""return node.element"""
return self.element
def dict_form(self):
"""return node as dict form"""
dict_set = {
"element": self.element,
"left": self.left,
"right": self.right,
}
return dict_set
def __str__(self):
"""when print a node , print it's element"""
return str(self.element)
上述的dict_form interface是将结点以python字典的形式呈现出来,方便后面将树打包成字典。另外说明下由于python字典的
特性,将字典当成一个树结构来处理也是可以的。事实上,很多人是这样做的。下图测试展现了树结点的实现:
评论0