算法导论习题 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