寫在前面：

本文前面部分介紹相關概念，后面部分是程序。

點擊下面鏈接查看更多！

點擊此處發現更多

一、二叉樹的概念

1.1 相關術語

①結點：包含一個數據元素及若干指向子樹分支的信息?。

②結點的度：一個結點擁有子樹的數目稱為結點的度。

③葉子結點：也稱為終端結點，沒有子樹的結點或者度為零的結點。

④分支結點：也稱為非終端結點，度不為零的結點稱為非終端結點。

⑤樹的度：樹中所有結點的度的最大值。

⑥結點的層次：從根結點開始，假設根結點為第1層，根結點的子節點為第2層，依此類推，如果某一個結點位于第L層，則其子節點位于第L+1層?。

⑦樹的深度：也稱為樹的高度，樹中所有結點的層次最大值稱為樹的深度?。

⑧有序樹：如果樹中各棵子樹的次序是有先后次序，則稱該樹為有序樹。

⑨無序樹：如果樹中各棵子樹的次序沒有先后次序，則稱該樹為無序樹?。

⑩森林：由m（m≥0）棵互不相交的樹構成一片森林。如果把一棵非空的樹的根結點刪除，則該樹就變成了一片森林，森林中的樹由原來根結點的各棵子樹構成?。

1.2 相關性質

性質1：二叉樹的第i層上至多有個節點?。

性質2：深度為h的二叉樹中至多含有個節點。

性質3：若在任意一棵二叉樹中，有n0個葉子節點，有n2個度為2的節點，則必有n0=n2+1。

性質4：具有n個節點的完全二叉樹深為（其中x表示不大于n的最大整數）。

性質5：若對一棵有n個節點的完全二叉樹進行順序編號（1≤i≤n），那么，對于編號為i（i≥1）的節點：

當i=1時，該節點為根，它無雙親節點?。

當i>1時，該節點的雙親節點的編號為i/2?。

若2i≤n，則有編號為2i的左節點，否則沒有左節點?。

若2i+1≤n，則有編號為2i+1的右節點，否則沒有右節點。

1.3 二叉樹類型

普通二叉樹、完全二叉樹、滿二叉樹、線索二叉樹、哈夫曼樹、二叉搜索樹（排序樹）、平衡二叉樹、AVL平衡二叉樹、紅黑樹、B樹、B+樹、堆

1.4 二叉樹存儲方式

存儲的方式有鏈表和數組兩種，用數組存訪問速度快，但插入、刪除節點操作就比較費時了。實際中更多的是用鏈來表示二叉樹的。

1.4.1 順序存儲結構

二叉樹的順序存儲結構就是使用一維數組存儲二叉樹中的結點，并且結點的存儲位置，就是數組的下標索引。

一棵完全二叉樹及其采用順序存儲方式的圖示如下：

可以看出，當二叉樹為完全二叉樹時，結點數剛好填滿數組。

當二叉樹不為完全二叉樹時，采用順序存儲形式的圖示如下：

其中，∧表示數組中此位置沒有存儲結點。此時可以發現，順序存儲結構中已經出現了空間浪費的情況。

1.4.2?鏈式存儲結構

由二叉樹定義可知，二叉樹的每個結點最多有兩個孩子。因此，可以將結點數據結構定義為一個數據和兩個指針域。表示方式如圖3.11所示：

一棵完全二叉樹及其采用鏈式存儲方式的圖示如下：

1.5 二叉樹遍歷方式

二叉樹的遍歷是指從二叉樹的根結點出發，按照某種次序依次訪問二叉樹中的所有結點，使得每個結點被訪問一次，且僅被訪問一次。
二叉樹的訪問次序可以分為四種：

前序遍歷、中序遍歷、后序遍歷、層序遍歷。

其實是什么排序，直接看根節點在排序中的位置就行了。比如前序遍歷，根節點就在第一個；中序遍歷，根節點就在左右子樹之間；后序遍歷，根節點在最后。

1.5.1 前序遍歷

前序遍歷通俗的說就是從二叉樹的根結點出發，當第一次到達結點時就輸出結點數據，按照先向左在向右的方向訪問。

該二叉樹的前序遍歷輸出為：
ABDHIEJCFG

1.5.2?中序遍歷

中序遍歷就是從二叉樹的根結點出發，當第二次到達結點時就輸出結點數據，按照先向左在向右的方向訪問。

該二叉樹的中序遍歷輸出為：
HDIBJEAFCG

1.5.3 后序遍歷

后序遍歷就是從二叉樹的根結點出發，當第三次到達結點時就輸出結點數據，按照先向左在向右的方向訪問。

該二叉樹的后序遍歷輸出為：
HIDJEBFGCA

1.5.4?層次遍歷

層次遍歷就是按照樹的層次自上而下的遍歷二叉樹。下圖二叉樹的層次遍歷結果為：

ABCDEFGHIJ

1.5.5 對于二叉樹的遍歷的典型題型

1）已知前序遍歷序列和中序遍歷序列，確定一棵二叉樹。
例題：若一棵二叉樹的前序遍歷為ABCDEF，中序遍歷為CBAEDF，請畫出這棵二叉樹。
分析：前序遍歷第一個輸出結點為根結點，故A為根結點。早中序遍歷中根結點處于左右子樹結點中間，故結點A的左子樹中結點有CB，右子樹中結點有EDF。

?

按照同樣的分析方法，對A的左右子樹進行劃分，最后得出二叉樹。

2）已知后序遍歷序列和中序遍歷序列，確定一棵二叉樹。
后序遍歷中最后訪問的為根結點，因此可以按照上述同樣的方法，找到根結點后分成兩棵子樹，進而繼續找到子樹的根結點，一步步確定二叉樹的形態。
注：已知前序遍歷序列和后序遍歷序列，不可以唯一確定一棵二叉樹。

?

二、二叉樹的遍歷實現

2.1 前序遍歷

函數的方法：

void PreOrder(Node *root, vector<int> &ans)//形參為結構體類型的指針 {if(root==nullptr) return;//遞歸調用的結束條件ans.push_back(root->val);//訪問根結點的val值,其實這里就是對該節點的值進行操作，具體怎樣操作可以在PreOrder里進行傳參實現PreOrder(root->left);//前序遞歸遍歷root左子樹PreOrder(root->right);//前序遞歸遍歷root右子樹 }

類的方法：

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class Solution {void Traverse(TreeNode* root, vector<int> &ans){if(root == nullptr) return;ans.push_back(root->val); //此時對該節點進行處理(這里是記錄它)Traverse(root->left, ans); //一直遍歷左子樹，直到遍歷到最后一個左子樹為空的左節點，然后回退一步的root就是最后一個左節點Traverse(root->right, ans); //如果這個節點有右節點，把該右節點當做根節點遍歷右子樹，注意這里最后退出的其實是更上一個左節點的遍歷過程} public:vector<int> inorderTraversal(TreeNode* root) {vector<int> ans;Traverse(root,ans);return ans;} };

2.2 中序遍歷

函數的方法：

void InOrder(Node *root,vector<int> &ans)//形參為結構體類型的指針 {if(root==nullptr) return;//遞歸調用的結束條件InOrder(root->left);//前序遞歸遍歷root左子樹ans.push_back(root->val);//訪問根結點的val值,其實這里就是對該節點的值進行操作，具體怎樣操作可以在InOrder里進行傳參實現InOrder(root->right);//前序遞歸遍歷root右子樹 }

類的方法：

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class Solution {void Traverse(TreeNode* root, vector<int> &ans){if(root == nullptr) return;Traverse(root->left, ans); //一直遍歷左子樹，直到遍歷到最后一個左子樹為空的左節點，然后回退一步的root就是最后一個左節點ans.push_back(root->val); //此時對該節點進行處理(這里是記錄它)Traverse(root->right, ans); //如果這個節點有右節點，把該右節點當做根節點遍歷右子樹，注意這里最后退出的其實是更上一個左節點的遍歷過程} public:vector<int> inorderTraversal(TreeNode* root) {vector<int> ans;Traverse(root,ans);return ans;} };

2.3 后序遍歷

函數的方法：

void PostOrder(Node *root,vector<int> &ans)//形參為結構體類型的指針 {if(root==nullptr) return;//遞歸調用的結束條件PostOrder(root->left);//前序遞歸遍歷root左子樹PostOrder(root->right);//前序遞歸遍歷root右子樹ans.push_back(root->val);//訪問根結點的val值,其實這里就是對該節點的值進行操作，具體怎樣操作可以在PostOrder里進行傳參實現 }

類的方法：

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class Solution {void Traverse(TreeNode* root, vector<int> &ans){if(root == nullptr) return;Traverse(root->left, ans); //一直遍歷左子樹，直到遍歷到最后一個左子樹為空的左節點，然后回退一步的root就是最后一個左節點Traverse(root->right, ans); //如果這個節點有右節點，把該右節點當做根節點遍歷右子樹，注意這里最后退出的其實是更上一個左節點的遍歷過程ans.push_back(root->val); //此時對該節點進行處理(這里是記錄它)} public:vector<int> inorderTraversal(TreeNode* root) {vector<int> ans;Traverse(root,ans);return ans;} };

2.4 層序遍歷

以力扣上的一道題為例：

有兩種方法：

第一種：直接使用前序遍歷，只不過每次記錄一下元素應該存在那一個數組，具體看代碼

//因為是每一層存一個數組，且從上到下，于是可以使用前序遍歷來完成，只不過將每次存的數用一個記錄了深度的外層vector來存儲 //利用depth變量記錄當前在第幾層（從0開始），進入下層時depth?+?1； //如果depth?>=?vector.size()說明這一層還沒來過，這是第一次來，所以得擴容咯； //因為是前序遍歷，中-左-右，對于每一層來說，左邊的肯定比右邊先被遍歷到，實際上后序中序都是一樣的。。。 class?Solution?{ public:vector<vector<int>>?levelOrder(TreeNode*?root)?{vector<vector<int>>?ans;pre(root,?0,?ans);return?ans;}void?pre(TreeNode?*root,?int?depth,?vector<vector<int>>?&ans)?{if?(!root)?return?;if?(depth?>=?ans.size())ans.push_back(vector<int>?{});ans[depth].push_back(root->val);pre(root->left,?depth?+?1,?ans);pre(root->right,?depth?+?1,?ans);} };

第二種：廣度優先搜索，使用隊列來完成。

class?Solution?{ public:vector<vector<int>>?levelOrder(TreeNode*?root)?{vector?<vector?<int>>?ret;if?(!root)?{return?ret;}queue?<TreeNode*>?q;q.push(root);while?(!q.empty())?{int?currentLevelSize?=?q.size();ret.push_back(vector?<int>?());for?(int?i?=?1;?i?<=?currentLevelSize;?++i)?{auto?node?=?q.front();?q.pop();ret.back().push_back(node->val);if?(node->left)?q.push(node->left);if?(node->right)?q.push(node->right);}}return?ret;} };

三、拓展

關于遍歷還有很多種形式，包括結合了某特定的一類二叉樹，要結合其性質來進行解答。也有一些是改變了遍歷方式，比如：

103. 二叉樹的鋸齒形層序遍歷

總結

以上是生活随笔為你收集整理的二叉树的相关性质及其前中后层序遍历实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。