数据结构——二叉树的类实现

Posted on |

遍历算法

深度优先遍历

先序遍历

递归遍历
1
2
3
4
5
6
def preorder(t,proc):
    if not t:
        return
    proc(t.data)
    preorder(t.left,proc)
    preorder(t.right,proc)
非递归遍历

在先序遍历中，访问的顺序依次为$根->左子树->右子树$。本方法先访问根结点，采用栈保存遇到的当前结点并暂不访问，并沿着树的左分支下。

循环中需要维持一种不变关系：假设变量t一直取值为当前待遍历子树的根，栈中保存当前遇到但尚未遍历的右子树。即循环条件是当前树非空（这棵树需要遍历）或者栈非空（还存在尚未遍历的部分）。

  • 由于先序遍历，先访问当前结点数据，当前结点的右分支入栈，下一步应该沿着树的左分支下行
  • 遇到空树时回溯，从弹出栈顶元素(最近的一个右子树),像二叉树一样遍历该右子树

每遇到空树,意味着完成遍历一棵子树：

  • 如果是一颗左子树，说明已遍历完该左子树，下一步应该访问与其对应的右子树（即栈顶元素）
  • 如果是一颗右子树，说明已遍历完以它为右子树的更大子树，下一步应该处理更上一层的子树的右子树（即栈顶元素）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    def preorder_nonrec(t,proc):
        stack=[]
        while t or stack:
            while t:
                proc(t.data)
                stack.append(t.right)
                t=t.left
                # print('next:', t.data if t else None,end=' ')
                # print('\tstack: ',[t.data if t else None for t in stack ])
            # print('-'*40)

            t=stack.pop()
            # print('-pop:', t.data if t else None,end=' ')
            # print('\tstack: ',[t.data if t else None for t in stack ])

    if __name__=='__main__':
        t=BinTNode(1,BinTNode(2,BinTNode(4),BinTNode(5)),BinTNode(3,BinTNode(6),BinTNode(7)))
        print('preorder_nonrec:'),preorder_nonrec(t,lambda x:print('proc:',x))
        print()

    # preorder_nonrec:
    # proc: 1
    # next: 2 	stack:  [3]
    # proc: 2
    # next: 4 	stack:  [3, 5]
    # proc: 4
    # next: None 	stack:  [3, 5, None]
    # ----------------------------------------
    # pop : None 	stack:  [3, 5]
    # ----------------------------------------
    # pop : 5 	stack:  [3]
    # proc: 5
    # next: None 	stack:  [3, None]
    # ----------------------------------------
    # pop : None 	stack:  [3]
    # ----------------------------------------
    # pop : 3 	stack:  []
    # proc: 3
    # next: 6 	stack:  [7]
    # proc: 6
    # next: None 	stack:  [7, None]
    # ----------------------------------------
    # pop : None 	stack:  [7]
    # ----------------------------------------
    # pop : 7 	stack:  []
    # proc: 7
    # next: None 	stack:  [None]
    # ----------------------------------------
    # pop : None 	stack:  []

中序遍历

递归遍历
1
2
3
4
5
6
def inorder(t,proc):
    if not t:
        return
    inorder(t.left,proc)
    proc(t.data)
    inorder(t.right,proc)
迭代遍历

在中序遍历中，访问的顺序依次为$左子树->根->右子树$.本方法沿着树的左分支下行，并采用栈保存遇到的当前结点并暂不访问.

循环中维持一种不变关系：假设变量t一直取值为当前待遍历子树的根，暂不访问该根节点，并入栈存储。即循环条件是当前树非空（这棵树需要遍历）或者栈非空（还存在尚未遍历的部分）。
循环体中，应先沿着左子树下行，一路上当前结点入栈，这用到一个循环。内部循环至空树时回溯，从弹出栈顶元素（左子树为空，则弹出的是左子树的根；右子树为空，则弹出的是右子树的根的父结点），访问当前结点，下一步遍历当前节点的右子树。

每次遇到空树，意味着完成遍历一个子树。

  • 如果是一颗左子树，说明已遍历完该左子树，下一步应该访问以它为左子树的根结点（栈顶元素）。
  • 如果是一颗右子树，说明已遍历完以它为右子树的更大子树，下一步应该处理更上一层的子树（即右子树的根的父结点，栈顶元素）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
def inorder_nonrec(t,proc):
    stack=[]
    while t or stack:
        while t:                # 沿左分支下行，完成左分支的遍历
            stack.append(t)     # 中序遍历，暂不处理根数据，当前分支入栈
            t=t.left            # 转向下一个左分支
            # print('next:', t.data if t else None,end=' ')
            # print('\tstack: ',[t.data if t else None for t in stack ])
        # print('-'*40)

        t=stack.pop()           # 遇到空树时回溯，应当弹出栈顶元素（最近的根结点）
        proc(t.data)            # 处理根数据
        t=t.right               # 转向右分支
        # print('next:', t.data if t else None,end=' ')
        # print('\tstack: ',[t.data if t else None for t in stack ])
if __name__=='__main__':
    t=BinTNode(1,BinTNode(2,BinTNode(4),BinTNode(5)),BinTNode(3,BinTNode(6),BinTNode(7)))
    print('inorder_nonrec:'),inorder_nonrec(t,lambda x:print('proc:',x))
    print()

# inorder_nonrec:
# next: 2 	stack:  [1]
# next: 4 	stack:  [1, 2]
# next: None 	stack:  [1, 2, 4]
# ----------------------------------------
# proc: 4
# next: None 	stack:  [1, 2]
# ----------------------------------------
# proc: 2
# next: 5 	stack:  [1]
# next: None 	stack:  [1, 5]
# ----------------------------------------
# proc: 5
# next: None 	stack:  [1]
# ----------------------------------------
# proc: 1
# next: 3 	stack:  []
# next: 6 	stack:  [3]
# next: None 	stack:  [3, 6]
# ----------------------------------------
# proc: 6
# next: None 	stack:  [3]
# ----------------------------------------
# proc: 3
# next: 7 	stack:  []
# next: None 	stack:  [7]
# ----------------------------------------
# proc: 7
# next: None 	stack:  []

后序遍历

递归遍历
迭代遍历

变量t的值是当前结点（可能为空）。在遍历循环中维持一种不变关系：

  • 栈中结点序列的左边是二叉树已遍历的部分，右边是未遍历部分
  • 如果t不为空，则其父结点是栈顶结点
  • 如果t为空时，栈顶就是应该访问的结点
    根据被访问结点是其父结点的左子节点或右子节点，决定下一步：如果是左子结点就转到右子结点；如果是右子结点，就应该处理根节点并强行退栈。