算法导论10.3 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 308 阅读时长 ≈ 1 分钟

10.3-1

10.3-2

1
2
3
4
5
6
PRINT-BINARY-TREE-RECURSIVE(x)
  if x == NIL
    return
  print x.key
  PRINT-BINARY-TREE-RECURSIVE(x.left)
  PRINT-BINARY-TREE-RECURSIVE(x.right)

10.3-3

1
2
3
4
5
6
7
8
9
10
11
12
PRINT-BINARY-TREE-NONRECURSIVE(x)
  let S be a new STACK
  p = x
  while not STACK-EMPTY(S) or p != NIL
      // 一直沿着左子节点走，如果发现走不下去，那么回退父节点，并且开始走右子节点。
      while p != NIL
        print p.key
        PUSH(S, p)
        p = p.left
      if not STACK-EMPTY(S)
        p = POP(S)
        p = p.right

10.3-4

1
2
3
4
5
6
7
8
PRINT-TREE(x)
  if x == NIL
    return
  print x.key
  p = x.left-child
  while p != NIL
    PRINT-TREE(p)
    p = p.right-sibling

\(\star\) 10.3-5

基本思想是上一次访问节点pre和当前节点q选择下一次访问的节点。

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
PRINT-BINARY-TREE-NONRECURSIVE-CONSTANT-SPACE(x)
  Let S be a new STACK.
  pre = NIL
  q = x
  while q != NIL
    if q.p == pre
      // 说明上一次访问的是q的父节点，说明子树q还没被访问过。
      print q.key
      pre = q
      // 尝试向下访问
      if q.left != NIL
        q = q.left
      else if q.right != NIL
        q = q.right
      // 这是个叶节点，返回。
      else
        q = q.p
    else if q.left == pre and q.right != NIL
      // 如果左子树为空，右子树非空，可以发现不会从这里进入右子树。
      pre = q
      q = q.right
    else
      // 左右子树都访问过，返回到父节点。
      pre = q
      q = q.p

\(\star\) 10.3-6

这种新节点x'包含如下\(3\)个新属性：

  • x'.left 和原来的x.left_child语义完全相同，表示x'最左边的儿子。
  • x'.is-right 布尔值，判断x'是否为自己最右边的兄弟。也就是说，判断自己是否为父节点最右边的孩子。
  • x'.right 如果x'.is_right为False，那么x'.right链接的是自己的右边的兄弟；否则链接的是自己的父节点。

遍历自己的兄弟时，如果遍历着发现x.is_right = True，那么说明回到了父节点。