python数据结构之二叉树的遍历实例
遍历方案 有次序: 遍历的命名 根据访问结点操作发生位置命名: 注:由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。 遍历算法 1).先序遍历的递归算法定义: 3).后序遍历得递归算法定义: 一、二叉树的递归遍历: 复制代码 代码如下: # -*- coding: utf - 8 - *- class TreeNode(object): bt = BTree(root) 二、.二叉树的非递归遍历 下面就用非递归的方式实现一遍。主要用到了 stack 和 queue维护一些数据节点: 复制代码 代码如下: # -*- coding: utf - 8 - *- class TreeNode(object): def __init__(self,treenode): '前序(pre-order,NLR)遍历' stack = [] while treenode or stack: if treenode is not 0: print treenode.data stack.append(treenode) treenode = treenode.left else: treenode = stack.pop() treenode = treenode.right def inorder(self,treenode): '中序(in-order,LNR) 遍历' stack = [] while treenode or stack: if treenode: stack.append(treenode) treenode = treenode.left else: treenode = stack.pop() print treenode.data treenode = treenode.right # def postorder(self,treenode): # stack = [] # pre = 0 # while treenode or stack: # if treenode: # stack.append(treenode) # treenode = treenode.left # elif stack[-1].right != pre: # treenode = stack[-1].right # pre = 0 # else: # pre = stack.pop() # print pre.data def postorder(self,treenode): '后序(post-order,LRN)遍历' stack = [] queue = [] queue.append(treenode) while queue: treenode = queue.pop() if treenode.left: queue.append(treenode.left) if treenode.right: queue.append(treenode.right) stack.append(treenode) while stack: print stack.pop().data def levelorder(self,treenode): from collections import deque if not treenode: return q = deque([treenode]) while q: treenode = q.popleft() print treenode.data if treenode.left: q.append(treenode.left) if treenode.right: q.append(treenode.right) node1 = TreeNode(data=1) node2 = TreeNode(node1,'root') bt = BTree(root) print u''' #生成的二叉树 # ------------------------ # root # 7 8 # 6 # 2 5 # 1 3 4 # # ------------------------- ''' print '前序(pre-order,NLR)遍历 :n' bt.preorder(bt.root) print '中序(in-order,LNR) 遍历 :n' bt.inorder(bt.root) print '后序(post-order,LRN)遍历 :n' bt.postorder(bt.root) print '层序(level-order,LRN)遍历 :n' bt.levelorder(bt.root) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |