python实现二叉树的遍历
本文实例为大家分享了python实现二叉树的遍历具体代码,供大家参考,具体内容如下
代码:
# -*- coding: gb2312 -*- class Queue(object): def __init__(self): self.q = [] def enqueue(self, item): self.q.append(item) def dequeue(self): # if self.q != []: if len(self.q)>0: return self.q.pop(0) else: return None def length(self): return len(self.q) def isempty(self): return len(self.q)==0 class Stack(object): def __init__(self): self.s = [] def push(self, item): self.s.append(item) def pop(self): if self.s !=[]: item = self.s.pop(-1) else: item = None return item def length(self): return len(self.s) def isempty(self): return self.s == [] def top(self): return self.s[-1] class TreeNode(object): def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right self.visited = False def setData(self, data): self.data = data def setLeft(self, left): self.left = left def setRight(self, right): self.right = right def visit(self): print self.data, self.visited = True def deVisit(self): self.visited = False class BinaryTree(object): def __init__(self, root): self.root = root # 前序遍历(递归) def freshVisit(self, node): if node is not None: node.deVisit() if node.left: self.freshVisit(node.left) if node.right: self.freshVisit(node.right) # 前序遍历(递归) def preOrder(self, node): if node is not None: node.visit() if node.left: self.preOrder(node.left) if node.right: self.preOrder(node.right) # 中序遍历(递归) def inOrder(self, node): if node.left: self.inOrder(node.left) if node is not None: node.visit() if node.right: self.inOrder(node.right) # 后序遍历(递归) def postOrder(self, node): if node.left: self.postOrder(node.left) if node.right: self.postOrder(node.right) if node is not None: node.visit() # 递归遍历 def orderTraveral(self, type): if type == 0: self.preOrder(self.root) elif type == 1: self.inOrder(self.root) elif type == 2: self.postOrder(self.root) # 前序遍历(非递归) # 用到一个栈和一个队列 # 首先是根节点入栈,再循环出栈 # 出栈元素不为空,则访问 # 出栈元素有左孩子节点则入栈,如果有右孩子节点则入队列 # 出栈元素为空,则访问队列 # 队列也为空则结束循环,否则队列元素出队 # 访问出队元素,出队元素有左孩子节点则入栈,出队元素有右孩子节点则入队列 # 循环直到最后退出 def preOrderByNotRecursion(self): s = Stack() q = Queue() q.enqueue(self.root) while not s.isempty() or not q.isempty(): if not q.isempty(): item = q.dequeue() item.visit() if item.left: q.enqueue(item.left) if item.right: s.push(item.right) elif not s.isempty(): item = s.pop() item.visit() if item.left: q.enqueue(item.left) if item.right: s.push(item.right) # 前序遍历(非递归) # 用到一个栈 # 首先是根节点入栈,再循环出栈 # 栈顶元素不为空,则访问, 并置已访问标志 # 如栈顶元素有左孩子节点则入栈 # 若栈顶元素已访问,则出栈 # 出栈元素若有右孩子节点则入栈 # 循环直到栈无元素退出 def preOrderByNotRecursion2(self): s = Stack() s.push(self.root) while not s.isempty(): item = s.top() if item.visited: s.pop() if item.right: s.push(item.right) else: item.visit() if item.left: s.push(item.left) # 中序遍历(非递归) # 用到一个栈 # 先将根节点入栈,循环出栈 # 如果出栈元素有左孩子节点并且左孩子节点没有访问过则入栈 # 反之,则出栈并且访问;如果出栈元素有右孩子节点则入栈 # 重复以上循环直到栈为空 def inOrderByNotRecursion(self): s = Stack() s.push(self.root) while not s.isempty(): item = s.top() while(item.left and not item.left.visited): s.push(item.left) item = item.left else: item = s.pop() item.visit() if item.right: s.push(item.right) # 后序遍历(非递归) # 用到一个栈 # 先将根节点入栈,循环出栈 # 如果出栈元素有左孩子节点并且左孩子节点没有访问过则入栈 # 反之,如果栈顶元素如果有右孩子节点并且右孩子节点没有访问过,则入栈 # 否则,出栈并访问 # 重复以上循环直到栈为空 def postOrderByNotRecursion(self): s = Stack() s.push(self.root) while not s.isempty(): item = s.top() while(item.left and not item.left.visited): s.push(item.left) item = item.left else: if item.right and not item.right.visited: s.push(item.right) else: item = s.pop() item.visit() # 层次遍历(非递归) # 用到一个队列 # 先将根节点入队列 # 从队列取出一个元素,访问 # 如有左孩子节点则入队,如有右孩子节点则入队 # 重复以上操作直到队列入空 def layerOrder(self): q = Queue() q.enqueue(self.root) while not q.isempty(): item = q.dequeue() item.visit() if item.left: q.enqueue(item.left) if item.right: q.enqueue(item.right) # A # B C # D E F G #H if __name__ == '__main__': nE = TreeNode('E'); nF = TreeNode('F'); nG = TreeNode('G'); nH = TreeNode('H'); nD = TreeNode('D', nH); nB = TreeNode('B', nD, nE); nC = TreeNode('C', nF, nG); nA = TreeNode('A', nB, nC); bTree = BinaryTree(nA); # 前序递归遍历 print '----------前序遍历(递归)-----------' bTree.orderTraveral(0) print '\n----------中序遍历(递归)-----------' bTree.orderTraveral(1) print '\n----------后序遍历(递归)-----------' bTree.orderTraveral(2) print '\n\n----------前序遍历(非递归)-----------' print '----------方法一-----------' bTree.freshVisit(bTree.root) bTree.preOrderByNotRecursion() print '\n----------方法二-----------' bTree.freshVisit(bTree.root) bTree.preOrderByNotRecursion2() print '\n\n----------中序遍历(非递归)-----------' bTree.freshVisit(bTree.root) bTree.inOrderByNotRecursion() print '\n\n----------后序遍历(非递归)-----------' bTree.freshVisit(bTree.root) bTree.postOrderByNotRecursion() print '\n\n----------层次遍历(非递归)-----------' bTree.freshVisit(bTree.root) bTree.layerOrder()
结果:
相关推荐
kikaylee 2020-11-11
夜斗不是神 2020-11-17
YENCSDN 2020-11-17
lsjweiyi 2020-11-17
houmenghu 2020-11-17
Erick 2020-11-17
HeyShHeyou 2020-11-17
以梦为马不负韶华 2020-10-20
lhtzbj 2020-11-17
pythonjw 2020-11-17
dingwun 2020-11-16
lhxxhl 2020-11-16
坚持是一种品质 2020-11-16
染血白衣 2020-11-16
huavhuahua 2020-11-20
meylovezn 2020-11-20
逍遥友 2020-11-20