萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

二元樹前序遍歷:遞迴與非遞迴 (堆疊) 實作完整解析

前序遍歷順序:**根 → 左 → 右**。本文提供 C++ 樣板類別的遞迴與非遞迴兩種實作,並詳細解析非遞迴演算法的堆疊邏輯。

1. 遞迴實作

template 
void PreOrder(nodeType *root) {
  if (root == NULL) return;
  visit(root->data);           // 1. 造訪根節點
  PreOrder(root->lchild);      // 2. 遞迴左子樹
  PreOrder(root->rchild);      // 3. 遞迴右子樹
}

特點:程式碼簡潔、符合定義直覺,但深度過大時可能堆疊溢位。

2. 非遞迴實作 (堆疊法)

演算法邏輯

  1. 根節點入堆疊。
  2. 堆疊不為空時迴圈:
    1. 彈出堆疊頂節點 temp,造訪之。
    2. 若 temp 有右子節點 → 入堆疊 (先右)。
    3. 若 temp 有左子節點 → 入堆疊 (後左,保證左子節點在堆疊頂,優先被處理)。

代碼實作

void PreOrder_Nonrecursive(BinaryTree T) {
  if (!T) return;
  stack s;
  s.push(T);
  while (!s.empty()) {
    BinaryTree temp = s.top(); s.pop();
    visit(temp->data);
    if (temp->rchild) s.push(temp->rchild);  // 先壓右
    if (temp->lchild) s.push(temp->lchild);  // 再壓左
  }
}

另一種非遞迴寫法 (模擬遞迴過程)

void PreOrder_Nonrecursive_v2(BinaryTree T) {
  if (!T) return;
  stack s;
  BinaryTree t = T;
  while (t || !s.empty()) {
    if (t) {
      visit(t->data);
      s.push(t);
      t = t->lchild;          // 一路往左
    } else {
      t = s.top(); s.pop();
      t = t->rchild;          // 轉向右
    }
  }
}

複雜度分析

指標遞迴非遞迴
時間複雜度O(n)O(n)
空間複雜度O(h) 隱式呼叫堆疊O(h) 顯式堆疊
堆疊溢位風險有 (極深樹)無 (堆積在堆疊區)

教學重點

  • 非遞迴關鍵:**右子節點先入堆疊**,確保左子節點優先被處理。
  • 第二種寫法更接近遞迴邏輯,適合理解「模擬呼叫堆疊」概念。
  • 中序、後序非遞迴遍歷同理可推導,只需調整造訪時機與入堆順序。

熟練兩種寫法,不僅能應付面試考題,更能深入理解樹結構與堆疊的關係。

copyright © 萬盛學電腦網 all rights reserved