怎么在C++項目中遍歷二叉樹

怎么在C++項目中遍歷二叉樹？針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

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

#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++項目中遍歷二叉樹問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。