二叉树是有限个元素的集合，该集合或者为空、或者有一个称为根节点（root）的元素及两个互不相交的、分别被称为左子树和右子树的二叉树组成。
遍历二叉树通过递归是非常简单的，非递归的话需要通过栈（深度优先，前序、中序、后序都属于深度优先）或者队列（广度优先，例如层次搜索）来实现。
class Node:
'节点类'
def __init__(self,value = -1,key = -1):
self.value = value
self.key = key
self.lchild = None
self.rchild = None
class Tree:
'树类'
def __init__(self):
self.root = None
# 使用非递归方法插入数据
# def add(self,value):
# node = Node(value)
# #如果没有根节点
# if self.root==None:
# self.root = node
# else:
# n = self.root
# while True:
# if value > n.value:
# if n.rchild == None:
# n.rchild = node
# break
# else:
# n = n.rchild
# elif value < n.value:
# if n.lchild == None:
# n.lchild = node
# break
# else:
# n = n.lchild
# else:
# print('二叉排序树不能有同样的值')
# exit()
#使用递归方法插入数据
def add(self,value,key,my_node = None):
node = Node(value,key)
# 如果没有根节点
if self.root == None:
self.root = node
else:
if my_node==None:
n = self.root
else:
n = my_node
if value > n.value:
if n.rchild == None:
n.rchild = node
else:
self.add( value,key,n.rchild)
elif value < n.value:
if n.lchild == None:
n.lchild = node
else:
self.add(value,key,n.lchild)
else:
print('二叉排序树不能有同样的值')
exit()
def search(self,value):
n = self.root
try:
while value!= n.value:
if value>n.value:
n = n.rchild
else:
n = n.lchild
print(n.key)
#通过except处理没有搜索到数字的情况非常优雅
except AttributeError:
print('没有你要搜索的数字')
#前序遍历
def front_ergodic(self,node = None):
# 递归方法
# #先输出当前根节点
# if node == None:
# node = self.root
# print(node.value)
#
# #输出左边节点
# if node.lchild != None:
# self.front_ergodic(node.lchild)
#
# # 输出右边节点
# if node.rchild != None:
# self.front_ergodic(node.rchild)
# 非递归方法1
# node = self.root
# nodes = []
# while node:
# print(node.value)
# if node.rchild:
# nodes.append(node.rchild)
# if node.lchild:
# node = node.lchild
# else:
# # try:
# # node = nodes.pop()
# # except IndexError:
# # exit()
# if len(nodes)!=0:
# node = nodes.pop()
# else:
# exit()
# 非递归方法2 每次输出根节点，把左右节点入栈，出栈下一个节点
node = self.root
nodes = []
while node:
print(node.value)
if node.rchild:
nodes.append(node.rchild)
if node.lchild:
nodes.append(node.lchild)
try:
node = nodes.pop()
except:
exit()
# 中序遍历
def middle_ergodic(self,node = None):
#递归方法
# if node == None:
# node = self.root
#
# # 递归左边节点
# if node.rchild != None:
# self.middle_ergodic(node.lchild)
#
# print(node.value)
#
# # 递归右边节点
# if node.rchild != None:
# self.middle_ergodic(node.rchild)
#非递归方法
nodes = []
node = self.root
while nodes or node:
while node:
nodes.append(node)
node = node.lchild
node = nodes.pop()
print(node.value)
node = node.rchild
# 后序遍历
def after_ergodic(self,node = None):
# 递归方法
# if node == None:
# node = self.root
#
# # 遍历左边节点
# if node.lchild != None:
# self.after_ergodic(node.lchild)
#
# # 遍历右边节点
# if node.rchild != None:
# self.after_ergodic(node.rchild)
#
# print(node.value)
#非递归方法1 思维模式比较混乱
# node = self.root
# nodes = []
# markNode = None
#
# while nodes or node:
# while node:
# nodes.append(node)
# node = node.lchild
# node = nodes.pop()
# if not node.rchild or node.rchild is markNode:
# print(node.value)
# markNode = node #marknode 标记前一次被输出的node
# node = None
# else:
# nodes.append(node)
# node = node.rchild
# 非递归方法1 很取巧的一个办法，通过根后前输出 ，然后逆向
node = self.root
nodes = []
list = []
while node:
# print(node.value)
list.append(node.value)
if node.lchild:
nodes.append(node.lchild)
if node.rchild:
node = node.rchild
else:
if nodes:
node = nodes.pop()
else:
break
print(list[::-1])
# 层次遍历
def storey_ergodic(self,node = None):
#队列实现
myQueue = []
node = self.root
myQueue.append(node)
while myQueue:
node = myQueue.pop(0)
print(node.value)
if node.lchild != None:
myQueue.append(node.lchild)
if node.rchild != None:
myQueue.append(node.rchild)
if __name__ == '__main__':
'主函数'
list= [5,4,7,8,6,1,3,2,9,10]
my_tree = Tree()
for i in range(len(list)):
my_tree.add(list[i],i)
# 二叉排序树搜索
# my_tree.search(10)
# my_tree.front_ergodic()
# my_tree.middle_ergodic()
my_tree.after_ergodic()
# my_tree.storey_ergodic()