二叉树的遍历

先序遍历 # 递归 def pre_through(head): if head is None: return print(head.val) pre_through(head.left) pre_through(head.right) # 非递归 def pre_through(head): if head is None: return s = list() s.append(head) while head: head = s.pop(0) print(head.val) if head.left: s.append(head.left) if head.right: s.append(head.right) 中序遍历 def inorder_through(head): if head is None: return pre_through(head.left) print(head.val) pre_through(head.right) def inorder_through(head): s = list() s.append() while head is not None and len(s) != 0: if head is not None: s.append(head) head = head.left elif head is None: head = s.pop(0) print(head.val) head = head.right 后序遍历 def pos_through(head): if head is None: return pre_through(head.left) pre_through(head.right) print(head.val) def pos_through(head): if head is None: return s1, s2 = list(), list() s1.append(head) while s1: head = s1.pop() s2.append(head) if head.left: s1.append(head.left) if head.right: s1.append(head.right) while s2: print(s1.pop()) 层次遍历 def level_through(head): if head is None: return ret = list() ret.append(head) q = ret while ret: for i in ret: print(i.val) ret = [] while q: head = q.pop(0) if head.left: ret.append(left) if head.right: ret.append(right) q = ret # 使用 for 循环打印了每层的节点, 然后将前一层打印的节点的左右节点加入到队列中 def level_through(head): if head is None: return ret = list() ret.append(head) q = ret last, nlast = head, head while ret: for i in ret: if i == nlast: print(i.val) else: print(i.val, end = " ") ret = [] while q: head = q.pop(0) if head.left: ret.append(head.left) nlast = head.left if head.right: ret.append(head.right) nlast = head.right q = ret