第五章 二叉树的遍历

5.3 二叉树的遍历和线索二叉树

基础概念

相关提炼内容见 tree-traversal。

二叉树的遍历

先序遍历 PreOrder

遍历结点的顺序如下，先是 根结点、再是左子树，最后右子树

    1                1
   / \     =>       / \
  2   3            2   5
                  / \ / \
                 3  4 6  7

先序遍历的算法实现（递归）

void PreOrder(BiTree T) {
  if (T != NULL){         // 如果二叉树非空，则继续
    visit(T);             // 访问根结点内容
    PreOrder(T->lchild);  // 访问左子树内容
    PreOrder(T->rchild);  // 访问右子树内容
  }
}

中序遍历 InOrder

遍历结点的顺序如下，先是 左子树、再是根节点，最后右子树

    2                4
   / \     =>       / \
  1   3            2   6
                  / \ / \
                 1  3 5  7

中序遍历的算法实现（递归）

void InOrder(BiTree T) {
  if (T != NULL){
    InOrder(T->lchild);
    visit(T);
    InOrder(T->rchild);
  }
}

后续遍历 PostOrder

遍历结点的顺序如下，先是 左子树、再是根节点，最后右子树

    3                7
   / \     =>       / \
  1   2            3   6
                  / \ / \
                 1  2 4  5

void PostOrder(BiTree T) {
  if (T != NULL){
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    visit(T);
  }
}
 

递归算法和非递归算法的转换

中序遍历的非递归算法

void InOrder2(BiTree T, SqStack S) {
  InitStack(S);
  BiTree p = T;
  while (p || !IsEmpty(S)) {
    if (p) {
        Push(S, p);
        p = p->lchild;
    }
    else {
        Pop(S, p);
        visit(p);
        p = p->rchild;
    }
  }
}

先序遍历非递归

TODO

后续遍历非递归（比较难）

TODO

层次遍历

字面意思，一行一行遍历

     1
    / \
   2   3
  / \ / \
 4  5 6  7

void LevelOrder(BiNode T) {   // 输入根结点
  InitQueue(Q)
  BiTree p;
  EnQueue(Q, T);
  while (!IsEmpty(Q)) {      // 判断队列是否为空
    DeQueue(Q, p);
    visit(p);                // 访问p结点
    if (p->lchild != NULL)
        EnQueue(Q, p->lchild);
    if (p->rchild != NULL)
        EnQueue(Q, p->rchild);
  }
}

二级推论

• （先序 + 中序） => 唯一的二叉树
• （后序 + 中序） => 唯一的二叉树
• （层序 + 中序） => 唯一的二叉树

线索二叉树

TODO