Question

10.4-2

算法导论 10.4-2 O(n) 时间 递归遍历二叉树

TREE-PRINT(T)
1  print key[T]
2  if left[T] != NIL
3    TREE-PRINT(left[T])
4  if right[T] != NIL
5    TREE-PRINT(right[T])

10.4-3

算法导论 10.4-3 O(n) 二叉树 非递归遍历

TREE-PRINT(T, S)
 1  print key[T]
 2  PUSH(S, T)
 3  while true
 4    if left[T] != NIL
 5      then T <- left[T]
 6    else
 7      do
 8        T = POP(S)
 9        if T = NIL
10          then return
11      while left[T] = NIL
12      T <- right[T]

10.4-4

与二叉树的遍历过程相同

10.4-5

见 算法导论-10.4-5

采用类似中序遍历的处理方法，对一个结点，可以分为以下几种情况

1.从父结点进入子结点进行处理

（1）如果有左孩子，就处理左孩子

（2）返回到自己

（3）访问自己

（4）如果有右孩子，就处理右孩子

（5）返回到自己的父结点

2.从左孩子返回，说明左孩子已经处理过，自己还没访问，自己的右孩子也没有处理过，就进行 1-（2）

3.从右孩子返回，说明左右孩子都已经处理，自己也访问过，就返回到更上层

4.返回到根结点时，遍历结束

10.4-6

去掉 parent 指针，当布尔值为 1 时，rightchild 指向父结点，当布尔值为 0 值，rightchild 指向右兄弟，其余用法保持不变