C++樹之遍歷二叉樹實例詳解

Posted on by

在講遍歷之前，我們要先創建一個樹：

#include <iostream>
using namespace std;
typedef struct node;
typedef node *tree;

struct node{
 int data;    // 結點數值
 tree left,right;  // 左子樹和右子樹 
};
tree bt;

遍歷二叉樹有三種方式：

先序遍歷

先序遍歷的操作如下：

  • 訪問根結點
  • 先序遍歷左子樹（遞歸）
  • 先序遍歷右子樹（遞歸）

二叉樹bt的先序遍歷結果：12347536

代碼如下：

void preorder(tree bt){
 if (bt){    // 判斷不為空二叉樹 
  cout << bt->data;
  preorder(bt->left); // 遞歸遍歷左子樹 
  preorder(bt->right); // 遞歸遍歷右子樹 
 }
}

中序遍歷

中序遍歷的操作如下：

  • 中序遍歷左子樹（遞歸）
  • 訪問根結點
  • 中序遍歷右子樹（遞歸）

二叉樹bt的中序遍歷結果：7425136

代碼如下：

void inorder(tree bt){
 if (bt){    // 判斷不為空二叉樹 
  inorder(bt->left); // 遞歸遍歷左子樹 
  cout << bt->data;
  inorder(bt->right); // 遞歸遍歷右子樹 
 }
}

後序遍歷

後序遍歷的操作如下：

  • 後序遍歷左子樹（遞歸）
  • 後序遍歷右子樹（遞歸）
  • 訪問根結點

二叉樹bt的後序遍歷的結果：7452631

代碼如下：

void postorder(tree bt){
  if (bt){        // 判斷不為空二叉樹 
    postorder(bt->left);  // 遞歸遍歷左子樹 
    postorder(bt->right); // 遞歸遍歷右子樹 
    cout << bt->data;
  }
}

小結：我們使用遞歸的方式遍歷瞭二叉樹，大傢仔細觀察可以發現，先序遍歷就是先訪問根結點，再遞歸，中序遍歷是把訪問根結點放中間，後續遍歷是最後訪問。

總代碼：

#include <iostream>
using namespace std;
typedef struct node;
typedef node *tree;

struct node{
  int data;        // 結點數值
  tree left,right;    // 左子樹和右子樹 
};
tree bt;

void preorder(tree bt){
  if (bt){        // 判斷不為空二叉樹 
    cout << bt->data;
    preorder(bt->left);  // 遞歸遍歷左子樹 
    preorder(bt->right); // 遞歸遍歷右子樹 
  }
}
void inorder(tree bt){
  if (bt){        // 判斷不為空二叉樹 
    inorder(bt->left);  // 遞歸遍歷左子樹 
    cout << bt->data;
    inorder(bt->right); // 遞歸遍歷右子樹 
  }
}
void postorder(tree bt){
  if (bt){        // 判斷不為空二叉樹 
    postorder(bt->left);  // 遞歸遍歷左子樹 
    postorder(bt->right); // 遞歸遍歷右子樹 
    cout << bt->data;
  }
}

補充知識：

表達式：a+b*c

表達式二叉樹：

前綴表達式（波蘭式）：+a*bc

中綴表達式：a+b*c/d

後綴表達式（逆波蘭式）：abc*+

怎麼將中綴表達式轉換為前綴表達式或後綴表達式呢？隻需像前序遍歷和後序遍歷一樣遍歷表達二叉樹即可。

總結

到此這篇關於C++樹之遍歷二叉樹的文章就介紹到這瞭,更多相關C++遍歷二叉樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：