二叉树的遍历 —

概述

二叉树是一种重要的数据结构，前几天刚好用到了二叉树的中序遍历，顺便学习了先序、后序遍历和常用计算，这里一并总结一下。

创建节点

class TreeNode():

    def __init__(self, date, left=None, right=None):
        self.val = date
        self.left = left
        self.right = right

常用的方法

主要有求深度、节点数、节点值求和等

# 统计节点
def countNode(t):
    if t is None:
        return 0
    else:
        return countNode(t.left) + countNode(t.right) + 1

# 求数值和
def sumNode(t):
    if t is None:
        return 0
    else:
        return sumNode(t.left) + sumNode(t.right) + t.val

# 求最大深度
def maxDepth(t):
    if t is None:
        return 0
    else:
        return max(maxDepth(t.left) + 1 ,maxDepth(t.left) + 1)

先序、中序、后序遍历

三种遍历的顺序：

先序：根 -> 左树 -> 右树
中序：左树 -> 根 -> 右树
后序：左树 -> 右树 -> 根

使用递归来实现，代码如下：

# 前序遍历
def preOrder(t):
    if t is None:
        return
    else:
        print(t.val)
        preOrder(t.left)
        preOrder(t.right)

# 中序遍历
def inOrder(t):
    if t is None:
        return
    else:
        inOrder(t.left)
        print(t.val)
        inOrder(t.right)

# 后序遍历
def postOrder(t):
    if t is None:
        return
    else:
        postOrder(t.left)
        postOrder(t.right)
        print(t.val)

使用迭代来实现，代码如下：

# 非递归实现前序、中序、后序遍历

# 非递归实现前序遍历
def preOrderNonRec(t):
    if t is None:
        return
    stack = []
    while stack or t:
        while t:
            print(t.val)
            # 当前节点压栈
            stack.append(t)
            # 往下找左子树
            t = t.left
        # 当while结束时，当前节点为None，所有左子树已入栈
        t = stack.pop()
        # 弹出上一个节点，从这个节点的右树开始
        t = t.right


# 非递归实现中序遍历
def inOrderNonRec(t):
    if t is None:
        return
    stack = []
    while stack or t:
        while t:
            stack.append(t)
            t = t.left
        t = stack.pop()
        print(t.val)
        t = t.right()

# 非递归实现后序遍历
def postOrderNonRec(t):
    if t is None:
        return
    stack = []
    while stack or t:
        while t:
            stack.append(t)
            # 能左就左，没有左找右。
            t = t.left if t.left else t.right
        t = stack.pop()
        print(t.val)
        # 当栈不空 且 当前节点是栈顶的左子节点，那么应该去访问右子节点
        if stack and stack[-1].left == t:
            t = stack[-1].right
        else:
            # 没有右树时，强制退栈
            t = None

深度优先搜索和广度优先搜索

广度优先就是一层一层往下找，每层节点遍历完成后，再找下一层，使用队列来实出。
深度优先就是沿一条树找一底，再回退上一个节点重复这个过程，使用栈来实现。

# 广度优先
def BFS(t):
    if t is None:
        return
    queue = []
    queue.append(t)
    while queue:
        t = queue.pop(0)
        print(t.val)
        if t.left:
            queue.append(t.left)
        if t.right:
            queue.append(t.right)

# 深度优先
def DFS(t):
    if t is None:
        return
    stack = []
    stack.append(t)
    while stack:
        t = stack.pop()
        print(t.val)
        if t.right:
            stack.append(t.right)
        if t.left:
            stack.append(t.left)

这些方法学习起来并不难，但要熟练应用，还要勤加练习。