當(dāng)前位置：首頁(yè) > news >正文

深圳電子商務(wù)網(wǎng)站建設(shè)百度關(guān)鍵詞優(yōu)化快速排名軟件

news 2025/7/3 16:21:31

深圳電子商務(wù)網(wǎng)站建設(shè),百度關(guān)鍵詞優(yōu)化快速排名軟件,深圳高端網(wǎng)站設(shè)計(jì)建設(shè),網(wǎng)站開(kāi)發(fā)房源崗位目錄😋 任務(wù)描述相關(guān)知識(shí) 1. 二叉樹(shù)的基本概念與結(jié)構(gòu)定義 2. 建立二叉樹(shù) 3. 先序遍歷 4. 中序遍歷 5. 后序遍歷 6. 層次遍歷測(cè)試說(shuō)明通關(guān)代碼測(cè)試結(jié)果任務(wù)描述本關(guān)任務(wù)：實(shí)現(xiàn)二叉樹(shù)的遍歷相關(guān)知識(shí) 為了完成本關(guān)任務(wù)，你需要掌…

目錄😋

任務(wù)描述

相關(guān)知識(shí)

1. 二叉樹(shù)的基本概念與結(jié)構(gòu)定義

2. 建立二叉樹(shù)

3. 先序遍歷

4. 中序遍歷

5. 后序遍歷

6. 層次遍歷

測(cè)試說(shuō)明

通關(guān)代碼

測(cè)試結(jié)果

任務(wù)描述

本關(guān)任務(wù)：實(shí)現(xiàn)二叉樹(shù)的遍歷

相關(guān)知識(shí)

為了完成本關(guān)任務(wù)，你需要掌握：

二叉樹(shù)的基本概念與結(jié)構(gòu)定義
建立二叉樹(shù)
先序遍歷
中序遍歷
后序遍歷
層次遍歷

1. 二叉樹(shù)的基本概念與結(jié)構(gòu)定義

二叉樹(shù)是樹(shù)形結(jié)構(gòu)的一種特殊形式，它的每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)，對(duì)應(yīng)的子樹(shù)就是左子樹(shù)和右子樹(shù)。二叉樹(shù)可以為空（即沒(méi)有節(jié)點(diǎn)），也可以由根節(jié)點(diǎn)、左子樹(shù)和右子樹(shù)組成復(fù)雜的樹(shù)形結(jié)構(gòu)，這種結(jié)構(gòu)在很多數(shù)據(jù)處理場(chǎng)景中有著重要應(yīng)用，例如表達(dá)式解析、文件系統(tǒng)目錄結(jié)構(gòu)模擬、搜索算法實(shí)現(xiàn)等。
?
在 C++ 中，我們通常使用結(jié)構(gòu)體（struct）或者類（class）來(lái)定義二叉樹(shù)的節(jié)點(diǎn)結(jié)構(gòu)，下面以結(jié)構(gòu)體為例：
#include <iostream>
using namespace std;// 定義二叉樹(shù)節(jié)點(diǎn)結(jié)構(gòu)體
struct TreeNode {int val;  // 節(jié)點(diǎn)存儲(chǔ)的值，可以根據(jù)實(shí)際需求修改類型，比如存儲(chǔ)字符、結(jié)構(gòu)體等其他復(fù)雜類型TreeNode* left;  // 指向左子樹(shù)的指針TreeNode* right; // 指向右子樹(shù)的指針TreeNode(int x) : val(x), left(NULL), right(NULL) {}  // 構(gòu)造函數(shù)，用于方便地初始化節(jié)點(diǎn)
};
在上述代碼中：

val?成員變量用于存儲(chǔ)節(jié)點(diǎn)所包含的數(shù)據(jù)，比如數(shù)字、字符等，這里定義為?int?類型只是一個(gè)示例，實(shí)際應(yīng)用中可按需調(diào)整。
left?和?right?是指針類型，分別用于指向該節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的根節(jié)點(diǎn)，如果相應(yīng)子樹(shù)不存在，則指針為?NULL。
自定義的構(gòu)造函數(shù)?TreeNode(int x)?接受一個(gè)參數(shù)，用于初始化節(jié)點(diǎn)的值，并將左、右子樹(shù)指針初始化為?NULL，這樣在創(chuàng)建節(jié)點(diǎn)時(shí)能更方便地進(jìn)行初始化操作。

2. 建立二叉樹(shù)

(1) 手動(dòng)輸入構(gòu)建二叉樹(shù)示例
下面是一種簡(jiǎn)單的通過(guò)手動(dòng)輸入節(jié)點(diǎn)值來(lái)構(gòu)建二叉樹(shù)的方式，采用遞歸的思想：
#include <iostream>
using namespace std;// 定義二叉樹(shù)節(jié)點(diǎn)結(jié)構(gòu)體
struct TreeNode {int val;  // 節(jié)點(diǎn)存儲(chǔ)的值，可以根據(jù)實(shí)際需求修改類型TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};// 構(gòu)建二叉樹(shù)的函數(shù)（簡(jiǎn)單示例，這里采用手動(dòng)輸入的方式構(gòu)建，實(shí)際可按具體需求從文件等讀取數(shù)據(jù)構(gòu)建）
TreeNode* buildTree() {int data;cin >> data;if (data == -1) {  // 用 -1 表示空節(jié)點(diǎn)return NULL;}TreeNode* root = new TreeNode(data);root->left = buildTree();root->right = buildTree();return root;
}
代碼的詳細(xì)解釋如下：

首先，程序從標(biāo)準(zhǔn)輸入讀取一個(gè)整數(shù)值到變量?data?中，這個(gè)值將作為當(dāng)前節(jié)點(diǎn)要存儲(chǔ)的值。
接著，通過(guò)判斷?data?的值來(lái)確定是否創(chuàng)建節(jié)點(diǎn)。如果?data?的值為?-1，按照我們的約定，這表示當(dāng)前節(jié)點(diǎn)為空，直接返回?NULL，意味著這個(gè)位置在二叉樹(shù)中不存在實(shí)際節(jié)點(diǎn)。
若?data?不為?-1，則創(chuàng)建一個(gè)新的?TreeNode?類型的節(jié)點(diǎn)，使用剛才讀取到的值通過(guò)構(gòu)造函數(shù)進(jìn)行初始化，也就是?root = new TreeNode(data)?這一步，此時(shí)新節(jié)點(diǎn)的?left?和?right?指針初始化為?NULL。
然后，遞歸地調(diào)用?buildTree?函數(shù)來(lái)構(gòu)建當(dāng)前節(jié)點(diǎn)的左子樹(shù)，將返回的左子樹(shù)的根節(jié)點(diǎn)指針賦值給?root->left；同樣地，再次遞歸調(diào)用?buildTree?函數(shù)來(lái)構(gòu)建右子樹(shù)，并將右子樹(shù)的根節(jié)點(diǎn)指針賦值給?root->right。
最后，返回構(gòu)建好的以?root?為根節(jié)點(diǎn)的二叉樹(shù)的根節(jié)點(diǎn)指針，這樣就完成了整個(gè)二叉樹(shù)的構(gòu)建過(guò)程。

例如，按照以下輸入順序（假設(shè)輸入順序是先根節(jié)點(diǎn)，再左子樹(shù)節(jié)點(diǎn)，然后右子樹(shù)節(jié)點(diǎn)，空節(jié)點(diǎn)用?-1?表示）來(lái)構(gòu)建一棵二叉樹(shù)：
1
2
-1
-1
3
-1
-1
它將構(gòu)建出這樣一棵簡(jiǎn)單的二叉樹(shù)：
    1/ \2   3
(2) 從數(shù)組構(gòu)建二叉樹(shù)示例
除了手動(dòng)輸入的方式，還可以從給定的數(shù)組來(lái)構(gòu)建二叉樹(shù)，以下是一個(gè)示例代碼，假設(shè)數(shù)組按照完全二叉樹(shù)的層次遍歷順序存儲(chǔ)節(jié)點(diǎn)值（空節(jié)點(diǎn)用特定值表示，這里同樣用?-1）：
TreeNode* buildTreeFromArray(int arr[], int index, int n) {if (index >= n || arr[index] == -1) {return NULL;}TreeNode* root = new TreeNode(arr[index]);root->left = buildTreeFromArray(arr, 2 * index + 1, n);root->left = buildTreeFromArray(arr, 2 * index + 2, n);return root;
}

3. 先序遍歷

先序遍歷的順序是根節(jié)點(diǎn) -> 左子樹(shù) -> 右子樹(shù)。可以通過(guò)遞歸方式很方便地實(shí)現(xiàn)。

遞歸實(shí)現(xiàn)先序遍歷的代碼如下：
// 先序遍歷二叉樹(shù)
void preorderTraversal(TreeNode* root) {if (root == NULL) {return;}cout << root->val << " ";  // 訪問(wèn)根節(jié)點(diǎn)preorderTraversal(root->left);  // 遍歷左子樹(shù)preorderTraversal(root->right);  // 遍歷右子樹(shù)
}
代碼邏輯詳細(xì)解釋如下：

首先進(jìn)行邊界判斷，當(dāng)傳入的根節(jié)點(diǎn)指針?root?為?NULL?時(shí)，說(shuō)明已經(jīng)遍歷到了空子樹(shù)或者二叉樹(shù)本身為空，此時(shí)直接返回，不需要進(jìn)行后續(xù)操作。
如果根節(jié)點(diǎn)不為?NULL，那么按照先序遍歷的順序，首先要訪問(wèn)根節(jié)點(diǎn)。這里通過(guò)?cout << root->val << " ";?語(yǔ)句將根節(jié)點(diǎn)的值輸出顯示，這只是一種簡(jiǎn)單的訪問(wèn)方式示例，在實(shí)際應(yīng)用中，比如要將遍歷結(jié)果存儲(chǔ)起來(lái)用于后續(xù)處理，可以把節(jié)點(diǎn)值存儲(chǔ)到一個(gè)數(shù)組或者其他合適的數(shù)據(jù)結(jié)構(gòu)中。
接著，遞歸調(diào)用?preorderTraversal?函數(shù)去遍歷左子樹(shù)，這一步會(huì)以同樣的邏輯去訪問(wèn)左子樹(shù)的根節(jié)點(diǎn)、左子樹(shù)的左子樹(shù)、左子樹(shù)的右子樹(shù)等，直到左子樹(shù)遍歷完，也就是遇到葉子節(jié)點(diǎn)（其左子樹(shù)和右子樹(shù)都為?NULL）。
最后，再遞歸調(diào)用?preorderTraversal?函數(shù)去遍歷右子樹(shù)，同樣會(huì)按照先序遍歷的規(guī)則去訪問(wèn)右子樹(shù)中的各個(gè)節(jié)點(diǎn)，直至整個(gè)二叉樹(shù)的所有節(jié)點(diǎn)都被訪問(wèn)完。

例如，對(duì)于前面構(gòu)建的二叉樹(shù)：
    1/ \2   3
先序遍歷的輸出結(jié)果將是：1 2 3。

4. 中序遍歷

中序遍歷的順序是左子樹(shù) -> 根節(jié)點(diǎn) -> 右子樹(shù)。

其遞歸實(shí)現(xiàn)代碼如下：
// 中序遍歷二叉樹(shù)
void inorderTraversal(TreeNode* root) {if (root == NULL) {return;}inorderTraversal(root->left);  // 遍歷左子樹(shù)cout << root->val << " ";  // 訪問(wèn)根節(jié)點(diǎn)inorderTraversal(root->right);  // 遍歷右子樹(shù)
}
具體的代碼邏輯解釋如下：

同樣先進(jìn)行邊界判斷，若根節(jié)點(diǎn)指針?root?為?NULL，說(shuō)明已經(jīng)遍歷完或者二叉樹(shù)本身為空，直接返回，避免后續(xù)無(wú)效操作。
當(dāng)根節(jié)點(diǎn)不為?NULL?時(shí)，按照中序遍歷的規(guī)則，首先要遞歸地遍歷左子樹(shù)，也就是從最底層的左子樹(shù)節(jié)點(diǎn)開(kāi)始訪問(wèn)，一直向上到根節(jié)點(diǎn)的左子節(jié)點(diǎn)，這個(gè)過(guò)程中會(huì)依次訪問(wèn)左子樹(shù)中的各個(gè)節(jié)點(diǎn)，直到左子樹(shù)遍歷完畢。
然后，訪問(wèn)當(dāng)前的根節(jié)點(diǎn)，通過(guò)?cout << root->val << " ";?輸出根節(jié)點(diǎn)的值（同樣這只是簡(jiǎn)單訪問(wèn)示例，可按需改變操作）。
最后，遞歸遍歷右子樹(shù)，以同樣的中序遍歷規(guī)則去訪問(wèn)右子樹(shù)中的各個(gè)節(jié)點(diǎn)，直到整個(gè)二叉樹(shù)的所有節(jié)點(diǎn)都被訪問(wèn)到。

對(duì)于上述示例二叉樹(shù)：
    1/ \2   3
中序遍歷的輸出結(jié)果是：2 1 3。

5. 后序遍歷

后序遍歷的順序是左子樹(shù) -> 右子樹(shù) -> 根節(jié)點(diǎn)。

其遞歸實(shí)現(xiàn)如下：
// 后序遍歷二叉樹(shù)
void postorderTraversal(TreeNode* root) {if (root == NULL) {return;}postorderTraversal(root->left);  // 遍歷左子樹(shù)postorderTraversal(root->right);  // 遍歷右子樹(shù)cout << root->val << " ";  // 訪問(wèn)根節(jié)點(diǎn)
}
詳細(xì)的代碼邏輯說(shuō)明如下：

開(kāi)始先判斷根節(jié)點(diǎn)是否為?NULL，若是則直接返回，因?yàn)橐呀?jīng)遍歷完或者二叉樹(shù)為空。
若根節(jié)點(diǎn)不為?NULL，首先遞歸地遍歷左子樹(shù)，按照后序遍歷的要求，從左子樹(shù)的最底層葉子節(jié)點(diǎn)開(kāi)始，依次訪問(wèn)左子樹(shù)中的各個(gè)節(jié)點(diǎn)，直到左子樹(shù)全部遍歷完成。
接著，遞歸遍歷右子樹(shù)，同樣以左子樹(shù)的遍歷方式，從右子樹(shù)的底層開(kāi)始，逐步向上訪問(wèn)右子樹(shù)的各個(gè)節(jié)點(diǎn)，直至右子樹(shù)遍歷完畢。
最后，訪問(wèn)當(dāng)前的根節(jié)點(diǎn)，輸出根節(jié)點(diǎn)的值（示例中是簡(jiǎn)單打印，實(shí)際可根據(jù)具體需求進(jìn)行其他處理），這樣就按照后序遍歷的順序訪問(wèn)了整個(gè)二叉樹(shù)的所有節(jié)點(diǎn)。

對(duì)于前面給出的示例二叉樹(shù)：
    1/ \2   3
后序遍歷的輸出結(jié)果是：2 3 1。

6. 層次遍歷

層次遍歷是按照二叉樹(shù)的層次，從根節(jié)點(diǎn)開(kāi)始，逐層向下訪問(wèn)各個(gè)節(jié)點(diǎn)，通常借助隊(duì)列（queue）數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。

以下是使用 C++ 標(biāo)準(zhǔn)庫(kù)中的?queue?實(shí)現(xiàn)層次遍歷的詳細(xì)示例代碼：
#include <iostream>
#include <queue>
using namespace std;// 層次遍歷二叉樹(shù)
void levelOrderTraversal(TreeNode* root) {if (root == NULL) {return;}queue<TreeNode*> q;  // 創(chuàng)建一個(gè)存儲(chǔ) TreeNode* 類型的隊(duì)列，用于存放節(jié)點(diǎn)指針q.push(root);  // 首先將根節(jié)點(diǎn)入隊(duì)while (!q.empty()) {  // 只要隊(duì)列不為空，就繼續(xù)循環(huán)進(jìn)行遍歷操作TreeNode* node = q.front();  // 獲取隊(duì)列頭部的節(jié)點(diǎn)q.pop();  // 將隊(duì)列頭部的節(jié)點(diǎn)出隊(duì)cout << node->val << " ";  // 訪問(wèn)當(dāng)前節(jié)點(diǎn)，這里同樣是簡(jiǎn)單輸出節(jié)點(diǎn)值，可按需改變操作if (node->left!= NULL) {  // 判斷當(dāng)前節(jié)點(diǎn)的左子樹(shù)是否存在q.push(node->left);  // 如果存在，將左子樹(shù)節(jié)點(diǎn)入隊(duì)}if (node->right!= NULL) {  // 判斷當(dāng)前節(jié)點(diǎn)的右子樹(shù)是否存在q.push(node->right);  // 如果存在，將右子樹(shù)節(jié)點(diǎn)入隊(duì)}}
}
代碼的詳細(xì)邏輯解釋如下：

首先進(jìn)行根節(jié)點(diǎn)是否為空的判斷，若為空則直接返回，因?yàn)榭斩鏄?shù)不需要進(jìn)行遍歷操作。
創(chuàng)建一個(gè)?queue<TreeNode*>?類型的隊(duì)列，用于存儲(chǔ)二叉樹(shù)的節(jié)點(diǎn)指針，然后將根節(jié)點(diǎn)指針?root?通過(guò)?q.push(root)?操作入隊(duì)，這是層次遍歷的起始點(diǎn)。
進(jìn)入?while?循環(huán)，只要隊(duì)列不為空，就表示還有節(jié)點(diǎn)需要遍歷。在循環(huán)中：
首先通過(guò)?q.front()?獲取隊(duì)列頭部的節(jié)點(diǎn)指針，并將其賦值給?node，然后通過(guò)?q.pop()?將隊(duì)列頭部的節(jié)點(diǎn)出隊(duì)，這一步是按照先進(jìn)先出的原則處理隊(duì)列中的節(jié)點(diǎn)。
接著訪問(wèn)當(dāng)前節(jié)點(diǎn)，示例中通過(guò)?cout << node->val << " ";?輸出節(jié)點(diǎn)的值，實(shí)際應(yīng)用中可以根據(jù)需求進(jìn)行更復(fù)雜的操作，比如將節(jié)點(diǎn)值存儲(chǔ)到二維數(shù)組中，按照層次結(jié)構(gòu)來(lái)存儲(chǔ)，便于后續(xù)的處理和展示等。
之后，判斷當(dāng)前節(jié)點(diǎn)的左子樹(shù)是否存在，如果左子樹(shù)節(jié)點(diǎn)指針不為?NULL，則通過(guò)?q.push(node->left)?將左子樹(shù)節(jié)點(diǎn)入隊(duì)，以便后續(xù)按照層次順序訪問(wèn)它。
同樣地，判斷當(dāng)前節(jié)點(diǎn)的右子樹(shù)是否存在，若右子樹(shù)節(jié)點(diǎn)指針不為?NULL，則通過(guò)?q.push(node->right)?將右子樹(shù)節(jié)點(diǎn)入隊(duì)。

通過(guò)不斷地循環(huán)上述操作，隊(duì)列會(huì)依次存儲(chǔ)和取出每一層的節(jié)點(diǎn)，從而實(shí)現(xiàn)按照層次順序遍歷整個(gè)二叉樹(shù)的所有節(jié)點(diǎn)。

例如，對(duì)于以下稍微復(fù)雜一點(diǎn)的二叉樹(shù)：
        1/   \2     3/ \   / \4   5 6   7
層次遍歷的輸出結(jié)果將是：1 2 3 4 5 6 7。

測(cè)試說(shuō)明

平臺(tái)會(huì)對(duì)你編寫的代碼進(jìn)行測(cè)試：

測(cè)試輸入：

A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))

預(yù)期輸出：

二叉樹(shù)b:A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
層次遍歷序列:A B C D E F G H I J K L M N
先序遍歷序列:A B D E H J K L M N C F G I
中序遍歷序列:D B J H L K M N E A F C G I
后序遍歷序列:D J L N M K H E B F I G C A

開(kāi)始你的任務(wù)吧，祝你成功！

通關(guān)代碼

// 請(qǐng)?jiān)贐egin-End之間添加你的代碼，
//實(shí)現(xiàn)二叉樹(shù)遍歷的基本運(yùn)算//
//對(duì)括號(hào)表示串的二叉樹(shù)進(jìn)行遍歷，由用戶輸入括號(hào)表示串//
//實(shí)現(xiàn)二叉樹(shù)的先序遍歷、中序遍歷、后序遍歷、層次遍歷//
/********** Begin *********/
#include <bits/stdc++.h>
using namespace std;
#define MaxSize 100
typedef char ElemType;
typedef struct node {ElemType data;struct node *lchild;struct node *rchild;
} BTNode;
typedef struct {BTNode *data[MaxSize];int front, rear;
} SqQueue;
void CreateBTree(BTNode *&b, char *str) {BTNode *St[MaxSize], *p;int top = -1, k, j = 0;char ch;b = nullptr;ch = str[j];while (ch != '\0') {switch (ch) {case '(':top++;St[top] = p;k = 1;break;case ')':top--;break;case ',':k = 2;break;default:p = (BTNode *)malloc(sizeof(BTNode));p->data = ch;p->lchild = p->rchild = nullptr;if (b == nullptr)b = p;else {switch (k) {case 1:St[top]->lchild = p;break;case 2:St[top]->rchild = p;break;}}}j++;ch = str[j];}
}
void DispBTree(BTNode *b) {if (b != nullptr) {printf("%c", b->data);if (b->lchild != nullptr || b->rchild != nullptr) {printf("(");DispBTree(b->lchild);if (b->rchild != nullptr)printf(",");DispBTree(b->rchild);printf(")");}}
}
void InitQueue(SqQueue *&q) {q = (SqQueue *)malloc(sizeof(SqQueue));q->front = q->rear = 0;
}
void DestroyQueue(SqQueue *&q) { free(q); }
bool QueueEmpty(SqQueue *q) { return (q->front == q->rear); }
bool enQueue(SqQueue *&q, BTNode *e) {if ((q->rear + 1) % MaxSize == q->front) {return false;}q->rear = (q->rear + 1) % MaxSize;q->data[q->rear] = e;return true;
}
bool deQueue(SqQueue *&q, BTNode *&e) {if (q->front == q->rear)return false;q->front = (q->front + 1) % MaxSize;e = q->data[q->front];return true;
}
void LevelOrder(BTNode *b) {BTNode *p;SqQueue *qu;InitQueue(qu);enQueue(qu, b);while (!QueueEmpty(qu)) {deQueue(qu, p);printf("%c ", p->data);if (p->lchild != nullptr)enQueue(qu, p->lchild);if (p->rchild != nullptr)enQueue(qu, p->rchild);}DestroyQueue(qu);
}
void PreOrder(BTNode *b) {if (b != nullptr) {printf("%c ", b->data);PreOrder(b->lchild);PreOrder(b->rchild);}
}
void InOrder(BTNode *b) {if (b != nullptr) {InOrder(b->lchild);printf("%c ", b->data);InOrder(b->rchild);}
}
void PostOrder(BTNode *b) {if (b != nullptr) {PostOrder(b->lchild);PostOrder(b->rchild);printf("%c ", b->data);}
}
int main() {char str[100];cin >> str;BTNode *b;CreateBTree(b, str);cout << "二叉樹(shù)b:";DispBTree(b);cout << endl;cout << "層次遍歷序列:";LevelOrder(b);cout << endl;cout << "先序遍歷序列:";PreOrder(b);cout << endl;cout << "中序遍歷序列:";InOrder(b);cout << endl;cout << "后序遍歷序列:";PostOrder(b);return 0;
}/********** End **********/