二叉樹(shù)先序、中序、后序遍歷 遞歸與非遞歸 Python實(shí)現(xiàn)

1.先序遍歷：根節(jié)點(diǎn)->左子樹(shù)->右子樹(shù)

# 先序打印二叉樹(shù)（遞歸）
def preOrderTraverse(node):
    if node is None:
        return None
    print(node.val)
    preOrderTraverse(node.left)
    preOrderTraverse(node.right)

# 先序打印二叉樹(shù)（非遞歸）
def preOrderTravese(node):
    stack = [node]
    while len(stack) > 0:
        print(node.val)
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)
        node = stack.pop()

2.中序遍歷：左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)

# 中序打印二叉樹(shù)（遞歸）
def inOrderTraverse(node):
    if node is None:
        return None
    inOrderTraverse(node.left)
    print(node.val)
    inOrderTraverse(node.right)

# 中序打印二叉樹(shù)（非遞歸）
def inOrderTraverse(node):
    stack = []
    pos = node
    while pos is not None or len(stack) > 0:
        if pos is not None:
            stack.append(pos)
            pos = pos.left
        else:
            pos = stack.pop()
            print(pos.val)
            pos = pos.right

3.后序遍歷：左子樹(shù)->右子樹(shù)->根節(jié)點(diǎn)

# 后序打印二叉樹(shù)（遞歸）
def postOrderTraverse(node):
    if node is None:
        return None
    postOrderTraverse(node.left)
    postOrderTraverse(node.right)
    print(node.val)

# 后序打印二叉樹(shù)（非遞歸）
# 使用兩個(gè)棧結(jié)構(gòu)
# 第一個(gè)棧進(jìn)棧順序：左節(jié)點(diǎn)->右節(jié)點(diǎn)->跟節(jié)點(diǎn)
# 第一個(gè)棧彈出順序： 跟節(jié)點(diǎn)->右節(jié)點(diǎn)->左節(jié)點(diǎn)(先序遍歷棧彈出順序：跟->左->右)
# 第二個(gè)棧存儲(chǔ)為第一個(gè)棧的每個(gè)彈出依次進(jìn)棧
# 最后第二個(gè)棧依次出棧
def postOrderTraverse(node):
    stack = [node]
    stack2 = []
    while len(stack) > 0:
        node = stack.pop()
        stack2.append(node)
        if node.left is not None:
            stack.append(node.left)
        if node.right is not None:
            stack.append(node.right)
    while len(stack2) > 0:
        print(stack2.pop().val)

4.按層遍歷：從上到下、從左到右按層遍歷

# 先進(jìn)先出選用隊(duì)列結(jié)構(gòu)
import queue
def layerTraverse(head):
    if not head:
        return None
    que = queue.Queue()      # 創(chuàng)建先進(jìn)先出隊(duì)列
    que.put(head)
    while not que.empty():
        head = que.get()    # 彈出第一個(gè)元素并打印
        print(head.val)
        if head.left:       # 若該節(jié)點(diǎn)存在左子節(jié)點(diǎn),則加入隊(duì)列（先push左節(jié)點(diǎn)）
            que.put(head.left)
        if head.right:      # 若該節(jié)點(diǎn)存在右子節(jié)點(diǎn),則加入隊(duì)列（再push右節(jié)點(diǎn)）
            que.put(head.right)

5.二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)

# 求二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)
def treeNodenums(node):
    if node is None:
        return 0
    nums = treeNodenums(node.left)
    nums += treeNodenums(node.right)
    return nums + 1

6.二叉樹(shù)的最大深度

# 二叉樹(shù)的最大深度
def bTreeDepth(node):
    if node is None:
        return 0
    ldepth = bTreeDepth(node.left)
    rdepth = bTreeDepth(node.right)
    return (max(ldepth, rdepth) + 1)