算法导论习题 10.4-5
由 瞳人
发布于 Jan. 7, 2017, 9:34 p.m.
0 个评论
题目
写出一个 \( \mathit{O} (n) \) 时间的非递归过程，输出给定的含 \( n \) 个结点的二叉树中的每个结点的关键字。要求只能使用除树本身以外固定量的额外存储空间，而且在过程中不能修改该树，哪怕是暂时的。
思路
一般基于深度优先的非递归遍历二叉树的算法，需要使用一个栈来记录未展开遍历的结点，那么该空间复杂度应该是 \( \mathit{O} (n) \) 的。用栈主要是为了能够便于返回上一层。而在算法导论第 10 章中的二叉树结构本身就包含了指向其父结点的指针，因此可以不需要使用栈来回溯。我们先访问结点本身，然后再访问其左子树，然后访问其右子树。用回溯来源结点判断下一个访问结点，具体策略如下。
- 若从结点的左子树返回，则若有右子树，则遍历右子树；否则返回至父节点。
- 若从结点的右子树返回，则返回父节点。
- 否则，为第一次访问该结点，输出其关键字。若有左子树，则先遍历左子树；否则若有右子树，则遍历右子树；若为叶子结点，则返回至父节点。
- 循环 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_node，n 表示 node。（我一般不打水印，但是这图我画得比较辛苦。。^_^）
0 Comments