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

更新時間：2021年03月11日 11:38:47 作者：Linyiwei

這篇文章主要給大家介紹了關(guān)于C++樹之遍歷二叉樹的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

在講遍歷之前，我們要先創(chuàng)建一個樹：

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

struct node{
 int data;    // 結(jié)點數(shù)值
 tree left,right;  // 左子樹和右子樹 
};
tree bt;

遍歷二叉樹有三種方式：

先序遍歷

先序遍歷的操作如下：

訪問根結(jié)點
先序遍歷左子樹（遞歸）
先序遍歷右子樹（遞歸）

二叉樹bt的先序遍歷結(jié)果：12347536

代碼如下：

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

中序遍歷

中序遍歷的操作如下：

中序遍歷左子樹（遞歸）
訪問根結(jié)點
中序遍歷右子樹（遞歸）

二叉樹bt的中序遍歷結(jié)果：7425136

代碼如下：

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

后序遍歷

后序遍歷的操作如下：

后序遍歷左子樹（遞歸）
后序遍歷右子樹（遞歸）
訪問根結(jié)點

二叉樹bt的后序遍歷的結(jié)果：7452631

代碼如下：

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

小結(jié)：我們使用遞歸的方式遍歷了二叉樹，大家仔細觀察可以發(fā)現(xiàn)，先序遍歷就是先訪問根結(jié)點，再遞歸，中序遍歷是把訪問根結(jié)點放中間，后續(xù)遍歷是最后訪問。

總代碼：

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

struct node{
  int data;        // 結(jié)點數(shù)值
  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;
  }
}