考研笔记

板子：前序、中序、后序递归遍历

三种遍历的代码只有一处不同：visit 放在两个递归调用的前面、中间还是后面。

代码

void visit(BiTNode *p) { printf("%d ", p->data); }   // 访问结点：这里是输出，做题时换成题目要做的事
 
void PreOrder(BiTree T) {                    // 前序：根 → 左 → 右
    if (T == NULL) return;                   // 递归出口：空树什么都不做
    visit(T);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}
 
void InOrder(BiTree T) {                     // 中序：左 → 根 → 右
    if (T == NULL) return;
    InOrder(T->lchild);
    visit(T);
    InOrder(T->rchild);
}
 
void PostOrder(BiTree T) {                   // 后序：左 → 右 → 根
    if (T == NULL) return;
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    visit(T);
}

复杂度：时间 ；空间 ， 是树高，即递归栈的深度，最坏 。

例：

        1
      /   \
     2     3
    / \     \
   4   5     6

前序 1 2 4 5 3 6；中序 4 2 5 1 3 6；后序 4 5 2 6 3 1。

递归题套哪个框架

后面几乎所有二叉树算法题都是这三种遍历之一：

需要什么用哪种例子
先处理根，再把信息往下传给子树前序（靠参数）WPL：深度作为参数往下传
按从小到大的顺序处理 BST中序判断 BST
先拿到左右子树的结果，再往上交给根后序（靠返回值）树高、结点数、判断平衡

易错点

  • 递归出口 if (T == NULL) return; 放在第一行，不要先访问 T->data 再判空。
  • 参数写 BiTree T 就够了，不用 &，因为遍历不修改指针本身。建树这类要修改指针的函数才写 BiTree &T。
  • 答复杂度时，递归遍历的空间是 ，不是 。

链接

反向链接