🎈 作者：Linux猿

🎈 簡介：CSDN博客專家🏆，華為云享專家🏆，Linux、C/C++、面試、刷題、演算法盡管咨詢我，關注我，有問題私聊！

🎈 關注專欄：圖解資料結構和演算法（優質好文持續更新中……）🚀

🎈 歡迎小伙伴們點贊👍、收藏?、留言💬

🍓一、什么是二叉樹

🍓二、二叉樹特性

?2.1 概念

?2.2 定理

🍓三、二叉樹存盤

?3.1 鏈式存盤

?3.2 順序存盤

🍓四、二叉樹遍歷

?4.1 前序遍歷

🚩4.1.1 動圖演示

🚩4.1.2 代碼實作

?4.2 中序遍歷

🚩4.2.1 動圖演示

🚩4.2.2 代碼實作

?4.3 后續遍歷

🚩4.3.1 動圖演示

🚩4.3.2 代碼實作

?4.4 層次遍歷

🚩4.4.1 非遞回版本

🚩4.4.2 動圖演示

🍓五、特殊二叉樹

?5.1 滿二叉樹

?5.2 完全二叉樹

🍓六、實戰演練

?6.1 求二叉樹深度

🚩6.1.1 遞回版本

🚩6.1.2 非遞回版本

?6.2 翻轉二叉樹

🍓七、總結

二叉樹是資料結構和演算法中很重要的一部分，樹中最典型的就數二叉樹了，下面就來詳細講解下，

🍓一、什么是二叉樹

二叉樹（Binary tree）是一種每個節點最多有兩個孩子節點的樹，左右孩子節點不能隨意顛倒，如下圖所示：

搞錯了，重來，應該是這樣的，如下所示：

在上圖中，二叉樹每個節點最多有兩個孩子節點，可以為空，可以只有一個左孩子或右孩子，

🔶🔶🔶🔶🔶 我是分割線 🔶🔶🔶🔶🔶

🍓二、二叉樹特性

?2.1 概念

葉子節點：在一棵樹中，沒有孩子節點（節點度為 0）的節點稱為葉子節點；

樹的深度：樹的深度是從根節點到最下面一層的葉子節點的層數，根節點的深度為 0 （這里不同的教程可能有差異，這里以維基百科為準）；

樹的高度：樹的高度是從最下面一層的葉子節點到根節點的層數為高度，最下面一層的葉子節點高度為 0；

父節點/父親節點：如果一個節點有子節點，則當前節點為子節點的父節點，根節點沒有父節點；

子節點/孩子節點：與父節點相連的下一層節點為該父節點的子節點；

兄弟結點：具有相同父節點的節點，互為兄弟節點；

下面來看一張圖來理解下，如下所示：

?2.2 定理

（1）二叉樹第 i 層上的節點數目最多為 2^(i-1) （i >= 1）；

（2）深度為 k 的二叉樹至多有 (2^k) -1 個節點 (k ≥ 1)；

（3）包含 n 個節點的二叉樹的高度至少為 log2(n+1)；

（4）在任意一棵二叉樹中，若葉子結點的個數為 N0，度為 2 的節點數為 N2，則 N0 = N2+1；

其中，第 4 條經常在考試中考到，

🔶🔶🔶🔶🔶 我是分割線 🔶🔶🔶🔶🔶

🍓三、二叉樹存盤

?3.1 鏈式存盤

typedef struct BiTNode
{
    Type data;
    struct BiTNode *left;  // 指向左孩子
    struct BiTNode *right; // 指向右孩子
}BiTNode,*BiTree;

上面的結構體表示的二叉樹節點中的任意節點的存盤，其中：

（1）data : 表示節點存盤的資料；

（2）left ：指向當前節點的左孩子，如果沒有則為空（NULL/nullptr）；

（3）right：指向當前節點的右孩子，如果沒有則為空（NULL/nullptr）；

?3.2 順序存盤

#define SIZE 1000    // 節點數
typedef Type BiTree[SIZE];

上面表示的是二叉樹的順序存盤結構，其中：

（1）SIZE：表示節點總數；

（2）BiTree[SIZE] ：表示存盤節點的陣列，使用下標標識節點，一般根節點存盤在下標為 1 的結點（便于計算父節點和子節點），假設父節點的下標為 i，左孩子節點則為 i*2，右孩子節點為 i*2 + 1，如下圖所示：

🔶🔶🔶🔶🔶 我是分割線 🔶🔶🔶🔶🔶

🍓四、二叉樹遍歷

二叉樹有四種遍歷方法，分別是：前序遍歷、中序遍歷、后續遍歷、層次遍歷，遍歷是將樹的所有節點訪問且僅訪問一次，其中，前序遍歷、中序遍歷、后續遍歷是按照訪問根節點順序的不同來區分的，

層次遍歷是從上到下從左往右進行遍歷，

?4.1 前序遍歷

前序遍歷先訪問根節點，然后，再以同樣的方式訪問左子樹和右子樹，直到遍歷完所有節點，具體步驟如下所示：

（1）訪問根節點；

（2）遍歷左子樹；

（3）遍歷右子樹；

🚩4.1.1 動圖演示

下面來看一下動圖演示，如下所示：

上圖中，序號表示前序遍歷訪問的節點順序，顏色也是按照這個順序依次變化的，一定要記住：根->左->右，

🚩4.1.2 代碼實作

這里列出前序遍歷的兩種實作，分別是遞回版本和非遞回版本，遞回版本代碼簡潔，更好理解一些，非遞回版本需要使用一個堆疊來模擬遞回程序，原理都是一樣的，

（1）遞回版本

// 存盤樹的單個節點
struct Node {
    int data; // 存盤節點資料
    struct Node *left;  // 左孩子節點
    struct Node *right; // 右孩子節點
};

// 前序遍歷
void preOrder(Node *root){
    if(root != NULL){ // 節點非空
        cout<<root->data<<endl; //1.訪問根節點
        preOrder(root->left);  //2.遍歷左子樹
        preOrder(root->right); //3.遍歷右子樹
    }
}

（2）非遞回版本

// 樹的單個節點
struct Node {
    int data; // 存盤節點資料
    struct Node *left;  // 左孩子節點
    struct Node *right; // 右孩子節點
};

// 前序遍歷 非遞回版本
void preOrder(Node *root)
{
    stack<Node*> s; // 堆疊，用來模擬遞回
    if(root != NULL) { // 判斷根節點是否為空
        s.push(root);
    }
    while (!s.empty()) {
        Node *p = s.top(); // 從堆疊里取出下一個要訪問的節點
        s.pop();           // 從堆疊中洗掉
        if (p != NULL) {
            cout << p->data <<endl;
            if(p->right != NULL)
                s.push(p->right);   //先放右子樹，因為是堆疊，先放進去的后訪問
            if(p->left != NULL)
                s.push(p->left);
       }
    }
}

如果有不理解堆疊的同學，可以看這篇講解堆疊和佇列的文章：

動圖+萬字，詳解堆疊和佇列（實體講解）【建議收藏】

?4.2 中序遍歷

中序遍歷先訪問左子樹，然后，訪問根節點，最后，遍歷右子樹，直到遍歷完所有節點，具體步驟如下所示：

（1）遍歷左子樹；

（2）訪問根節點；

（3）遍歷右子樹；

🚩4.2.1 動圖演示

下面來看一下動圖演示如下所示：

同樣，上圖中的序號即是中序遍歷訪問順序，顏色也會相應變化，一定要記住：左->根->右，

🚩4.2.2 代碼實作

這里同樣也列出中序遍歷的兩種實作，分別是遞回版本和非遞回版本，

（1）遞回版本

// 樹的單個節點
struct Node {
    int data; // 存盤節點資料
    struct Node *left;  // 左孩子節點
    struct Node *right; // 右孩子節點
};

// 中序遍歷 遞回版本
void inOrder(Node *root)
{
    if(root != NULL) { // 判斷是否為空
        inOrder(root->left); // 遞回遍歷左子樹
        cout << root->data <<endl;   // 訪問節點
        inOrder(root->right); // 遞回遍歷右子樹
    }
}

（2）非遞回版本

// 中序遍歷 非遞回版本
void inOrder(Node *root)
{
    stack<Node *> s; // 堆疊，模擬遞回
    while (root != NULL || !s.empty()) {
        if (root != NULL) {   //1.遍歷左子樹
            s.push(root);
            root = root->left;
        } else {
            root = s.top();
            cout << root->data <<endl; //2.訪問節點
            s.pop();            // 將訪問過的節點從堆疊中洗掉
            root = root->right; //3.遍歷右子樹
        }
    }
}

?4.3 后續遍歷

前序遍歷先訪問根節點，然后，再以同樣的方式訪問左子樹和右子樹，直到遍歷完所有節點，具體步驟如下所示：

（1）訪問根節點；

（2）遍歷左子樹；

（3）遍歷右子樹；

🚩4.3.1 動圖演示

下面來看一下動圖演示，如下所示：

后序遍歷相對于前序和中序而言，更難理解一些，一定要記住：左->右->根，

🚩4.3.2 代碼實作

（1）遞回版本

// 樹的單個節點
struct Node {
    int data; // 存盤節點資料
    struct Node *left;  // 左孩子節點
    struct Node *right; // 右孩子節點
};

// 后續遍歷 遞回版本
void postOrder(Node *root)
{
    if(root != NULL) { // 判斷是否為空
        postOrder(root->left);  // 遍歷左子樹
        postOrder(root->right); // 遍歷右子樹
        cout << root->data <<endl; // 訪問節點
    }
}

（2）非遞回版本

// 樹的單個節點
struct Node {
    int data; // 存盤節點資料
    struct Node *left;  // 左孩子節點
    struct Node *right; // 右孩子節點
};

// 后序遍歷 非遞回版本
void postOrder(Node* root){
    Node* curt = root;
    Node* pos = NULL;
    stack<Node*> s; // 堆疊，用于模擬遞回
    while (curt || !s.empty()) {
        while (curt) {
            s.push(curt);
            curt = curt->left;
        }
        Node* top = s.top();
        if(top->right == NULL || top->right == pos) {
            cout<<top->data<<endl;
            pos = top;
            s.pop();
        } else {
            curt = top->right;
        }
    }
}

?4.4 層次遍歷

二叉樹層次遍歷的順序是按照樹的深度，從上到下，從左到右進行遍歷的，

🚩4.4.1 非遞回版本

// 樹的單個節點
struct Node {
    int data; // 存盤節點資料
    struct Node *left;  // 左孩子節點
    struct Node *right; // 右孩子節點
};

// 層次遍歷 非遞回版本
void levelTraversal(Node* root)
{
	queue<Node*> q; // 佇列
	q.push(root);
	while (!q.empty()) { // 非空才回圈
		Node* curt = q.front();  // 取出最前面的元素
		q.pop();                 // 洗掉訪問的元素
		cout<<curt->data<<endl;  // 訪問當前元素
		if (curt->left)          // 判斷左孩子
			q.push(curt->left);
		if(curt->right)
			q.push(curt->right);  // 判斷右孩子
	}
}

🚩4.4.2 動圖演示

下面來看一下層次遍歷的動圖演示，如下所示：

層次遍歷是按照由上到下，由左到右進行遍歷，正好符合廣度優先搜索的思路，

🍓五、特殊二叉樹

在眾多的二叉樹中，有寫二叉樹具有一些獨特的特性，這樣的二叉樹有：滿二叉樹和完全二叉樹，下面就來看一下，

?5.1 滿二叉樹

滿二叉樹除了葉子節點外，非葉子節點都有兩個孩子節點，如下所示：

上圖是一個深度為 3 的滿二叉樹，可以看到，除葉子節點外，非葉子節點都有兩個孩子，

?5.2 完全二叉樹

完全二叉樹是除了最后一層外，其它層的節點數都有兩個孩子節點，如下圖所示：

🍓六、實戰演練

?6.1 求二叉樹深度

假設有一二叉樹，如下所示：

🚩6.1.1 遞回版本

代碼實作（遞回版本）

#include <iostream>
using namespace std;

// 二叉樹節點存盤
typedef struct BiTNode
{
    int data;
    struct BiTNode *left;  // 指向左孩子
    struct BiTNode *right; // 指向右孩子
}BiTNode,*BiTree;

// 求二叉樹深度
int binaryTreeDepth(BiTree root)
{
    if(root == nullptr) // 空的話回傳 0
        return 0;
    else {
        int leftDepth = binaryTreeDepth(root->left); // 求左子樹的深度
        int rightDepth = binaryTreeDepth(root->right); // 求右子樹的深度
        return max(leftDepth, rightDepth) + 1;
    }  
}


int main() {

    // 創建一個二叉樹
    BiTNode * root = new(BiTNode);
    BiTNode * node1 = new(BiTNode);
    BiTNode * node2 = new(BiTNode);
    BiTNode * node3 = new(BiTNode);
    BiTNode * node4 = new(BiTNode);
    BiTNode * node5 = new(BiTNode);

    root->left = node1;
    root->right = node2;

    node1->left = node3;
    node1->right = node4;
    node4->left = nullptr;
    node4->right = node5;

    node2->left = nullptr;
    node2->right = nullptr;

    node3->left = nullptr;
    node3->right = nullptr;

    node5->left = nullptr;
    node5->right = nullptr;

    // 呼叫求二叉樹深度
    cout<<"Binary Tree Depth = "<<binaryTreeDepth(root)-1<<endl; // 減 1 是因為從 0 開始計算的深度

}

🚩6.1.2 非遞回版本

代碼實作（非遞回）

#include <iostream>
#include <queue>
using namespace std;

// 二叉樹節點存盤
typedef struct BiTNode
{
    int data;
    struct BiTNode *left;  // 指向左孩子
    struct BiTNode *right; // 指向右孩子
}BiTNode,*BiTree;

// 求二叉樹深度 遞回版本
int binaryTreeDepth(BiTree root)
{
    if(root == nullptr) // 空的話回傳 0
        return 0;
    else {
        int leftDepth = binaryTreeDepth(root->left); // 求左子樹的深度
        int rightDepth = binaryTreeDepth(root->right); // 求右子樹的深度
        return max(leftDepth, rightDepth) + 1;
    }  
}

//求二叉樹深度 非遞回版本
int binaryTreeDepth(BiTree root)
{
    queue<BiTree> q;
    if(!root) return 0;
    q.push(root);
    int depth = 0;
    while(!q.empty()) {
        int num = q.size();
        depth++;
        while(num--) {
            BiTree curt = q.front();
            q.pop();
            if(curt->left) q.push(curt->left);
            if(curt->right) q.push(curt->right);
        }
    }
    return depth;
} 


int main() {

    // 創建一個二叉樹
    BiTNode * root = new(BiTNode);
    BiTNode * node1 = new(BiTNode);
    BiTNode * node2 = new(BiTNode);
    BiTNode * node3 = new(BiTNode);
    BiTNode * node4 = new(BiTNode);
    BiTNode * node5 = new(BiTNode);

    root->left = node1;
    root->right = node2;

    node1->left = node3;
    node1->right = node4;
    node4->left = nullptr;
    node4->right = node5;

    node2->left = nullptr;
    node2->right = nullptr;

    node3->left = nullptr;
    node3->right = nullptr;

    node5->left = nullptr;
    node5->right = nullptr;

    // 呼叫求二叉樹深度
    cout<<"Binary Tree Depth = "<<binaryTreeDepth(root)-1<<endl; // 減 1 是因為從 0 開始計算的深度，如果從1開始計算，則不用減 1 操作

}

?6.2 翻轉二叉樹

假設有一棵二叉樹，如下所示：

上圖中，使用大寫字母來標識每一個節點，翻轉上圖的二叉樹后，如下所示：

在圖中，實作了二叉樹的翻轉，所謂 “翻轉”，實質上是將每個節點的左右孩子節點交換，下面就來看下代碼實作，如下所示：

#include <iostream>

using namespace std;

// 二叉樹節點存盤
typedef struct BiTNode
{
    char data;
    struct BiTNode *left;  // 指向左孩子
    struct BiTNode *right; // 指向右孩子
}BiTNode,*BiTree;

class Solution {
public:
    BiTNode* invertTree(BiTNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        BiTNode* left = invertTree(root->left); // 遞回處理左子樹
        BiTNode* right = invertTree(root->right); // 遞回處理右子樹
        root->left = right; // 交換當前節點的左右子樹
        root->right = left;
        return root;
    }
};

// 前序遍歷輸出二叉樹
void printTree(BiTNode* root)
{
    if(root == nullptr)
        return;
    cout<<root->data<<" ";
    if(root->left)
        printTree(root->left);
    if(root->right)
        printTree(root->right);
}

int main()
{
    // 創建二叉樹
    BiTNode* rootA = new(BiTNode);
    BiTNode* nodeB = new(BiTNode);
    BiTNode* nodeC = new(BiTNode);
    BiTNode* nodeD = new(BiTNode);
    BiTNode* nodeE = new(BiTNode);
    BiTNode* nodeF = new(BiTNode);
    BiTNode* nodeG = new(BiTNode);

    rootA->left = nodeB;
    rootA->right = nodeC;
    rootA->data = 'A';

    nodeB->left = nodeD;
    nodeB->right = nodeE;
    nodeB->data = 'B';

    nodeC->left = nodeF;
    nodeC->right = nodeG;
    nodeC->data = 'C';

    nodeD->left = nullptr;
    nodeD->right = nullptr;
    nodeD->data = 'D';

    nodeE->left = nullptr;
    nodeE->right = nullptr;
    nodeE->data = 'E';

    nodeF->left = nullptr;
    nodeF->right = nullptr;
    nodeF->data = 'F';

    nodeG->left = nullptr;
    nodeG->right = nullptr;
    nodeG->data = 'G';
    // 翻轉前輸出
    cout<<"翻轉前 ";
    printTree(rootA);
    cout<<endl;
    Solution obj;
    obj.invertTree(rootA);

    // 翻轉后輸出
    cout<<"翻轉后 ";
    printTree(rootA);
    cout<<endl;
    return 0;
}

輸出結果為：

linuxy@linuxy:~$ ./inverBinary 
翻轉前 A B D E C F G 
翻轉后 A C G F B E D 
linuxy@linuxy:~$

輸出的遍歷結果是前序遍歷的結果，可以看到，將二叉樹每個節點的左右子樹都翻轉了，

🔶🔶🔶🔶🔶 我是分割線 🔶🔶🔶🔶🔶

🍓七、總結

好了，上面就是所有二叉樹講解的所有內容了，在掌味訓本的二叉樹概念后，還需要多實戰，多練習，

關注👇👇👇👇👇👇，獲取更多優質內容🤞（比心）！

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/328001.html

標籤：其他

上一篇：Linux程式崩潰分析（一）

下一篇：【歷史上的今天】10 月 20 日：微軟黑屏事件；Ubuntu Linux 作業系統發布；Apple Pay 正式上線

【資料結構和演算法】二叉樹詳解，動圖+實體

🍓一、什么是二叉樹

🍓二、二叉樹特性

?2.1 概念

?2.2 定理

🍓三、二叉樹存盤

?3.1 鏈式存盤

?3.2 順序存盤

🍓四、二叉樹遍歷

?4.1 前序遍歷

🚩4.1.1 動圖演示

🚩4.1.2 代碼實作

?4.2 中序遍歷

🚩4.2.1 動圖演示

🚩4.2.2 代碼實作

?4.3 后續遍歷

🚩4.3.1 動圖演示

🚩4.3.2 代碼實作

?4.4 層次遍歷

🚩4.4.1 非遞回版本

🚩4.4.2 動圖演示

🍓五、特殊二叉樹

?5.1 滿二叉樹

?5.2 完全二叉樹

🍓六、實戰演練

?6.1 求二叉樹深度

🚩6.1.1 遞回版本

🚩6.1.2 非遞回版本

?6.2 翻轉二叉樹

🍓七、總結