算法导论习题 10.4-5

瞳人


发布于 Jan. 7, 2017, 9:34 p.m.

0 个评论

Algorithm


题目

写出一个 \( \mathit{O} (n) \) 时间的非递归过程,输出给定的含 \( n \) 个结点的二叉树中的每个结点的关键字。要求只能使用除树本身以外固定量的额外存储空间,而且在过程中不能修改该树,哪怕是暂时的。

思路

一般基于深度优先的非递归遍历二叉树的算法,需要使用一个栈来记录未展开遍历的结点,那么该空间复杂度应该是 \( \mathit{O} (n) \) 的。用栈主要是为了能够便于返回上一层。而在算法导论第 10 章中的二叉树结构本身就包含了指向其父结点的指针,因此可以不需要使用栈来回溯。我们先访问结点本身,然后再访问其左子树,然后访问其右子树。用回溯来源结点判断下一个访问结点,具体策略如下。

  1. 若从结点的左子树返回,则若有右子树,则遍历右子树;否则返回至父节点。
  2. 若从结点的右子树返回,则返回父节点。
  3. 否则,为第一次访问该结点,输出其关键字。若有左子树,则先遍历左子树;否则若有右子树,则遍历右子树;若为叶子结点,则返回至父节点。
  4. 循环 1 至 3 步,直至结点为空。

代码

Python 代码如下:我们用 node 来指示当前访问结点, last_node 来指示上一个访问的结点,即回溯来源结点,一开始将 last_node 赋值为 root 是为了避免判断其是否为 None

 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
# coding=utf-8
__author__ = 'answ.me'


class Node:
    def __init__(self, key=None, left=None, right=None, parent=None):
        self.key = key
        self.left = left
        self.right = right
        self.parent = parent

    def set_left(self, left):
        self.left = left
        left.parent = self

    def set_right(self, right):
        self.right = right
        right.parent = self


def print_tree(root):
    node = root
    last_node = node
    while node is not None:
        if last_node == node.left:
            last_node = node
            if node.right is not None:
                node = node.right
            else:
                node = node.parent
        elif last_node == node.right:
            last_node = node
            node = node.parent
        else:
            print(node.key)
            last_node = node
            if node.left is not None:
                node = node.left
            elif node.right is not None:
                node = node.right
            else:
                node = node.parent


def test_root():
    print('expected: 1')
    root = Node(1)
    print_tree(root)


def test_root_left():
    print('expected: 1 2')
    root = Node(1)
    root.set_left(Node(2))
    print_tree(root)


def test_root_right():
    print('expected: 1 3')
    root = Node(1)
    root.set_right(Node(3))
    print_tree(root)


def test_root_left_right():
    print('expected: 1 2 3')
    root = Node(1)
    root.set_left(Node(2))
    root.set_right(Node(3))
    print_tree(root)


def test_tree():
    print('expected: 1 2 4 8 5 9 3 6 7')
    root = Node(1)
    root.set_left(Node(2))
    root.set_right(Node(3))
    root.left.set_left(Node(4))
    root.left.set_right(Node(5))
    root.right.set_left(Node(6))
    root.right.set_right(Node(7))
    root.left.left.set_right(Node(8))
    root.left.right.set_left(Node(9))
    print_tree(root)


if __name__ == '__main__':
    test_root()
    test_root_left()
    test_root_right()
    test_root_left_right()
    test_tree()

对于 print_tree 函数的详解可以参考下图,其中 ln 表示 last_noden 表示 node。(我一般不打水印,但是这图我画得比较辛苦。。^_^)

Algorithm exercise 10.4-5


哎呦, 不错哦!

0 Comments


Leave a Comment:

博客搜索

友情链接

公告

本博客代码已经公布在 Github 上,欢迎交流指正。

QQ 邮箱对 mailgun 不太友好, 所以使用 QQ 邮箱的评论, 可能会无法及时收到邮件。我会尽快寻找其他解决方案的。

本人现在独自使用 linode vps, 20 美元/月, 感觉压力大, 如果有意一起合租, 可以联系我. 在我的任意一篇文章下面留言即可. 关于使用方式, 现在倾向于使用 docker.