1 #-*- coding:utf-8 -*- 2 class Node: 3 def __init__(self,data): 4 self.data=data 5 self.lchild=None 6 self.rchild=None 7 8 class Tree: 9 def __init__(self): 10 self.queue=[]#利用队列存储树的节点 11 self.flag=0#存储树根后flag置为1 12 self.root=None 13 14 #建树 15 def createTree(self,list): 16 while True: 17 #list中没有数据，表示建树完成 18 if len(list)==0: 19 return 20 #flag为0，表示树根不存在 21 if self.flag==0: 22 self.root=Node(list[0]) 23 #讲树根存入队列 24 self.queue.append(self.root) 25 #树根已创建，flag置为1 26 self.flag=1 27 #剔除list中第一个已经使用数 28 list.pop(0) 29 else: 30 ''' 31 treeNode:队列中的第一个节点(该节点左右孩子不完全存在) 32 添加treeNode的左右孩子，当添加treeNode的右孩子之后， 33 将队列中的第一个节点出队。 34 ''' 35 treeNode=self.queue[0] 36 if treeNode.lchild==None: 37 treeNode.lchild=Node(list[0]) 38 self.queue.append(treeNode.lchild) 39 list.pop(0) 40 else: 41 treeNode.rchild = Node(list[0]) 42 self.queue.append(treeNode.rchild) 43 list.pop(0) 44 self.queue.pop(0) 45 46 47 # 递归实现先序遍历 48 def front_digui(self,root): 49 if root==None: 50 return 51 else: 52 print root.data, 53 self.front_digui(root.lchild) 54 self.front_digui(root.rchild) 55 # 递归实现中序遍历 56 def middle_digui(self,root): 57 if root==None: 58 return 59 else: 60 self.middle_digui(root.lchild) 61 print root.data, 62 self.middle_digui(root.rchild) 63 # 递归实现后序遍历 64 def behind_digui(self,root): 65 if root==None: 66 return 67 else: 68 self.behind_digui(root.lchild) 69 self.behind_digui(root.rchild) 70 print root.data, 71 72 # 队栈实现先序遍历 73 def front_queueAndStack(self,root): 74 if root==None: 75 return 76 #定义一个栈,存储节点 77 stack=[] 78 node=root 79 while stack or node: 80 #从树根开始一直输出左孩子 81 while node: 82 print node.data, 83 #将输出的节点加入栈中 84 stack.append(node) 85 node=node.lchild 86 #该节点不存在左节点时,该节点出栈,搜索该节点右节点， 87 node=stack.pop() 88 node=node.rchild 89 # 队栈实现中序遍历 90 def middle_queueAndStack(self,root): 91 if root==None: 92 return 93 # 定义一个栈,存储节点 94 stack = [] 95 node = root 96 while stack or node: 97 #一直查找树的左节点,一直进栈 98 while node: 99 stack.append(node) 100 node=node.lchild 101 node=stack.pop()#该节点不存在左节点，该节点出栈，查找右节点 102 print node.data, 103 node=node.rchild 104 # 队栈实现后序遍历 105 def behind_queueAndStack(self,root): 106 if root==None: 107 return 108 # 定义一个栈,存储节点 109 stack_1 = [] 110 stack_2 = [] 111 node = root 112 stack_1.append(node) 113 while stack_1: 114 #该节点出栈1.左右节点进栈1(对于左右节点,右节点先出栈1,也先进栈1) 115 node=stack_1.pop() 116 if node.lchild: 117 stack_1.append(node.lchild) 118 if node.rchild: 119 stack_1.append(node.rchild) 120 #该节点进栈2 121 stack_2.append(node) 122 while stack_2: 123 print stack_2.pop().data, 124 # 队栈实现层次遍历 125 def level_queueAndStack(self,root): 126 if root==None: 127 return 128 stack_1=[] 129 stack_2=[] 130 stack_1.append(root) 131 stack_2.append(root) 132 while stack_1: 133 node=stack_1.pop(0) 134 if node.lchild: 135 stack_1.append(node.lchild) 136 stack_2.append(node.lchild) 137 if node.rchild: 138 stack_1.append(node.rchild) 139 stack_2.append(node.rchild) 140 while stack_2: 141 print stack_2.pop(0).data, 142 143 144 if __name__ == '__main__': 145 list=[0,1,2,3,4,5,6,7,8,9,] 146 tree=Tree() 147 tree.createTree(list) 148 tree.front_digui(tree.root) 149 print ' ' 150 tree.middle_digui(tree.root) 151 print ' ' 152 tree.behind_digui(tree.root) 153 print ' ' 154 tree.front_queueAndStack(tree.root) 155 print ' ' 156 tree.middle_queueAndStack(tree.root) 157 print ' ' 158 tree.behind_queueAndStack(tree.root) 159 print ' ' 160 tree.level_queueAndStack(tree.root)