二叉树的遍历主要有三种方法：递归遍历、迭代遍历、morris遍历 。
三种顺序：前序遍历、中序遍历、后序遍历、层序遍历、
- 前序遍历：根 - 左 - 右
- 中序遍历：左 - 根 - 右
- 后序遍历：左 - 右 - 根
- 层序遍历：一层一层遍历，从上往下，从左往右
- 递归遍历：使用递归方法遍历
- 迭代遍历：使用迭代方法实现递归函数，与递归函数等价
（1）递归实现二叉树遍历
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
self.deep = 0
# 二叉树1
# node7 = TreeNode(7)
# node15 = TreeNode(15)
# node9 = TreeNode(9)
# node20 = TreeNode(20, node15, node7)
# node3 = TreeNode(3, node9, node20)
# 二叉树2
# node6 = TreeNode(6)
# node5 = TreeNode(5,None,node6)
# node4 = TreeNode(4,None,node5)
# node3 = TreeNode(3,None, node4)
# node2 = TreeNode(2,None,node3)
# 二叉树3
node7 = TreeNode(7)
node6 = TreeNode(6)
node5 = TreeNode(5,node6, node7)
node4 = TreeNode(4)
node3 = TreeNode(3)
node2 = TreeNode(2,node4, node5)
node1 = TreeNode(1, node2, node3)
root = node1
# 递归实现前序遍历
def recurrent1(root):
if root == None: return
print(root.val) # 第一次成为栈顶元素的时候进行打印
recurrent1(root.left)
recurrent1(root.right)
# 递归实现中序遍历
def recurrent2(root):
if root == None: return
recurrent2(root.left)
print(root.val) # 第二次成为栈顶元素的时候进行打印
recurrent2(root.right)
# 递归实现后序遍历
def recurrent3(root):
if root == None: return
# print(root)
recurrent3(root.left)
recurrent3(root.right)
print(root.val)
# 递归实现层序遍历
def layer_order(root):
arr = []
recurrent3(root, 1, arr)
for i in arr:
if i != None: print(i)
def recurrent3(root, index, arr):
# 我们知道二叉树每一层，节点数量最多为：1、2、4、8、16
# 其实如果我们使用一个数组存储一棵二叉树的话，他们都是有自己独一无二的下标的
# 假设第一个节点的下标为1，那么它的左子节点的下表是2*1，右子节点的下表是2*1+1
# 假设第n个节点的下标为i，那么它的左子节点的下标就是2*i,右子节点的下标就是2*i+1
if root == None: return
# 这里是为了防止数组越界的问题
l = len(arr)
if l<=index:
for _ in range(index-l+1):
arr.append(None)
arr[index] = root.val
recurrent3(root.left, 2*index, arr)
recurrent3(root.right, 2*index+1, arr)
layer_order(root)
（2）迭代实现二叉树遍历
from collections import deque
import queue
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
self.deep = 0
# 二叉树1
# node7 = TreeNode(7)
# node15 = TreeNode(15)
# node9 = TreeNode(9)
# node20 = TreeNode(20, node15, node7)
# node3 = TreeNode(3, node9, node20)
# 二叉树2
# node6 = TreeNode(6)
# node5 = TreeNode(5,None,node6)
# node4 = TreeNode(4,None,node5)
# node3 = TreeNode(3,None, node4)
# node2 = TreeNode(2,None,node3)
# 二叉树3
node7 = TreeNode(7)
node6 = TreeNode(6)
node5 = TreeNode(5, node6, node7)
node4 = TreeNode(4)
node3 = TreeNode(3)
node2 = TreeNode(2, node4, node5)
node1 = TreeNode(1, node2, node3)
root = node1
# 使用迭代的方法实现前序遍历
def Fun1(root):
if root != None:
stack = deque()
stack.append(root)
while len(stack) > 0:
root = stack.pop()
if root != None:
print(root.val)
stack.append(root.right)
stack.append(root.left)
# 使用迭代的方法实现中序遍历
def Fun2(root):
stack = deque()
while len(stack)>0 or root != None:
if root != None:
stack.append(root)
root = root.left
else:
root = stack.pop()
print(root.val)
root = root.right
# 使用迭代的方法实现后序遍历
def Fun3(root):
stack = deque()
prev = None
while len(stack)>0 or root != None:
while root != None:
stack.append(root)
root = root.left
root = stack.pop()
if root.right == None or root.right == prev:
print(root.val)
prev = root
root = None
else:
stack.append(root)
root = root.right
# 使用迭代的方法实现层序遍历
def Fun4(root):
q = queue.Queue()
q.put(root)
while not q.empty():
node = q.get()
if node != None: print(node.val)
if node.left != None: q.put(node.left)
if node.right != None: q.put(node.right)
Fun4(root)
（3）使用morris实现二叉树遍历
# 首先需要维护中序线索二叉树
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
self.deep = 0
# 二叉树1
# node7 = TreeNode(7)
# node15 = TreeNode(15)
# node9 = TreeNode(9)
# node20 = TreeNode(20, node15, node7)
# node3 = TreeNode(3, node9, node20)
# 二叉树2
# node6 = TreeNode(6)
# node5 = TreeNode(5,None,node6)
# node4 = TreeNode(4,None,node5)
# node3 = TreeNode(3,None, node4)
# node2 = TreeNode(2,None,node3)
# 二叉树3
node7 = TreeNode(7)
node6 = TreeNode(6)
node5 = TreeNode(5, node6, node7)
node4 = TreeNode(4)
node3 = TreeNode(3)
node2 = TreeNode(2, node4, node5)
node1 = TreeNode(1, node2, node3)
root = node1
# morris节点实现前序遍历
def fun1(cur):
if cur == None: return
most_right = None
while cur != None:
most_right = cur.left
if most_right != None: # 先找左子树
while most_right.right != None and most_right.right != cur: # 找左子树的最右边的节点
most_right = most_right.right
if most_right.right == None:
most_right.right = cur # 将叶子节点的指针进行维护,建立线索指针
print(cur.val)
cur = cur.left
continue
if most_right.right == cur:
most_right.right = None # 删除线索指针
else: # 找右子树
print(cur.val)
cur = cur.right
# morris节点实现中序遍历
def fun2(cur):
if cur == None: return
most_right = None
while cur != None:
most_right = cur.left
if most_right != None: # 先找左子树
while most_right.right != None and most_right.right != cur: # 找左子树的最右边的节点
most_right = most_right.right
if most_right.right == None:
most_right.right = cur # 将叶子节点的指针进行维护,建立线索指针
cur = cur.left
continue
if most_right.right == cur:
most_right.right = None # 删除线索指针
# else: # 找右子树
# print(cur.val)
print(cur.val)
cur = cur.right
# morris节点实现后序遍历
def fun3(cur):
if cur == None: return
root = cur
most_right = None
while cur != None:
most_right = cur.left
if most_right != None: # 先找左子树
while most_right.right != None and most_right.right != cur: # 找左子树的最右边的节点
most_right = most_right.right
if most_right.right == None:
most_right.right = cur # 将叶子节点的指针进行维护,建立线索指针
cur = cur.left
continue
if most_right.right == cur:
most_right.right = None # 删除线索指针
printf(cur.left)
cur = cur.right
printf(root)
def printf(head):
# 首先将链表进行反转
tail = reverse(head)
while tail != None:
print(tail.val)
tail = tail.right
reverse(tail)
def reverse(head):
next = None
prev = None
cur = head
while cur != None:
next = cur.right
cur.right = prev
prev = cur
cur = next
return prev
fun3(root)
网友评论