資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學二叉樹的順時針三角遍歷
在這個問題中，我們將建立一個完整的二叉樹並以順時針方向遍歷它。
對於順時針遍歷，我們可以考慮遍歷樹的邊界。例如，我們可以先遍歷樹的外邊界。之後，我們可以移除已訪問的節點並遍歷樹的內邊界。這樣，我們需要對給定的二叉樹進行 min(height/2, width/2) 次遍歷。
問題陳述
我們給定一個包含 N 個節點的完整二叉樹，需要以順時針方向遍歷它。
示例
輸入
n = 3 1 / \ 2 3
輸出
1, 3, 2
解釋
順時針遍歷結果為 1、3 和 2。
輸入
n = 7
1
/ \
2 3
/ \ / \
4 5 6 7
輸出
1, 3, 7, 6, 5, 4, 2
解釋
首先，我們遍歷了右邊界，然後是底邊界，最後是左邊界。
輸入
n = 11
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \
8 9 10 11
輸出
1, 3, 7, 11, 10, 9, 8, 4, 2, 6, 5
解釋
它以順時針迴圈的方式進行遍歷。我們需要不斷遍歷內部節點。
方法 1
在這種方法中，我們將使用列表來建立一個完整的二叉樹。之後，我們將建立一個二維列表並使用它來分別儲存每一層包含的節點列表。同時，我們將找到二叉樹的高度。
之後，我們將遍歷樹的右、下和左邊界。此外，我們將進行 totalLevels/2 次迴圈迭代以迴圈遍歷所有層。
演算法
步驟 1 − 執行 createBinaryTree() 函式以建立具有 n 個節點的完整二叉樹。
步驟 1.2 − 在 createBinaryTree() 函式中，使用 for 迴圈進行遍歷，並在迴圈內部將 'isChild' 定義為 false 值。
步驟 1.3 − 如果 2*p 小於或等於 n，則在 p 和 2*p 節點之間新增一條邊。在這裡，我們使用向量列表來建立二叉樹。因此，將 p 插入到 2*p 位置以在 p 和 2*p 之間新增一條邊。同時，將 isChild 設定為 true。
步驟 1.4 − 如果 2*p + 1 小於或等於 n，則在 p 和 2*p + 1 節點之間插入一條邊。同時，將 isChild 更新為 true。
步驟 1.5 − 如果 isChild 為 false，則中斷迴圈。
步驟 2 − 現在，呼叫 executeBFS() 函式以獲取列表中每一層的節點。
步驟 2.1 − 定義佇列以儲存單個節點及其父節點對。同時，將頭節點插入佇列中。同時，使用 nodes[][] 列表儲存每一層的節點。visited[] 列表用於用 true 布林值標記已訪問的節點。level[] 列表儲存每個節點的層號。
步驟 2.2 − 遍歷佇列。
步驟 2.3 − 從佇列中彈出第一對，並標記該節點已訪問。
步驟 2.4 − 遍歷當前節點的所有相鄰節點。
步驟 2.4.1 − 如果相鄰節點未被訪問，則將其與父節點一起插入佇列中。同時，將子節點的層級儲存在 level[] 列表中。
步驟 2.4.2 − 如果 max_level 小於 level[child]，則更新 max_level 值。
步驟 2.4.3 − 將當前節點推入 nodes[level[child]] 列表中。
現在，我們根據其層級在 nodes[][] 列表中獲得了樹的每個節點。
步驟 3 − 呼叫 showClockWise() 函式以順時針方向遍歷樹。
步驟 3.1 − 定義 levelNo 和 cycle 變數，並將它們初始化為 0。
步驟 3.2 − 當 cycle - 1 <= max_level / 2 條件為真時進行迭代。
步驟 3.3 − 接下來，我們需要遍歷右邊界。因此，使用迴圈進行迭代，直到 levelNo 小於 maxLevel − cycle。同時，從 nodes[levelNo] 列表中獲取最後一個節點，列印其值，並將 levelNo 加 1。
步驟 3.4 − 現在，我們需要遍歷樹的底部。
步驟 3.5 − 如果 levelNo == max_level − cycle 條件為真，則遍歷底部節點。
步驟 3.6 − 遍歷樹的左邊界。根據 'cycle' 變數的值，它可以是內邊界或外邊界。
步驟 3.7 − 將 cycle 值加 1，並將 levelNo 更新為 cycle + 1。
示例
#include <bits/stdc++.h>
using namespace std;
void insertEdge(int start, int end, vector<int> tree[]) {
tree[start].push_back(end);
tree[end].push_back(start);
}
void createBinaryTree(int n, vector<int> tree[]) {
// Create a complete binary tree
for (int p = 1;; p++) {
// Add edges to the tree
bool isChild = false;
if (2 * p <= n) {
insertEdge(p, 2 * p, tree);
isChild = true;
}
if (2 * p + 1 <= n) {
insertEdge(p, 2 * p + 1, tree);
isChild = true;
}
if (!isChild)
break;
}
}
void executeBFS(int root, vector<int> tree[], bool visited[], int level[], vector<int> nodes[], int &max_level) {
queue<pair<int, int>> que;
// Inserting the root node in the queue and mark it as visited
que.push({root, 0});
nodes[0].push_back(root);
visited[root] = true;
level[1] = 0;
while (!que.empty()) {
pair<int, int> temp = que.front();
que.pop();
visited[temp.first] = true;
// Get adjacent vertices
for (int child : tree[temp.first]) {
if (!visited[child]) {
que.push({child, temp.first});
level[child] = level[temp.first] + 1;
// Updating the max level
max_level = max(max_level, level[child]);
// Store nodes according to level wise
nodes[level[child]].push_back(child);
}
}
}
}
void showClockWise(vector<int> nodes[], int max_level) {
int levelNo = 0, cycle = 0;
while (cycle - 1 <= max_level / 2) {
// Traverse right nodes
while (levelNo < max_level - cycle) {
int q = nodes[levelNo].size() - 1;
cout << nodes[levelNo][q - cycle] << " ";
levelNo++;
}
// Traverse bottom nodes from right -> left
if (levelNo == max_level - cycle) {
int q = nodes[levelNo].size() - 1;
for (q -= cycle; q >= cycle; q--)
cout << nodes[levelNo][q] << " ";
}
levelNo--;
// Traverse left nodes
while (levelNo > cycle) {
cout << nodes[levelNo][cycle] << " ";
levelNo--;
}
// Increment cycle
cycle++;
// Update next level to start from
levelNo = cycle + 1;
}
}
int main() {
// Number of vertices
int n = 7;
const int size = 1e5;
int max_level = 0;
vector<int> tree[size + 1];
bool visited[size + 1];
int level[size + 1];
vector<int> nodes[size + 1];
createBinaryTree(n, tree);
executeBFS(1, tree, visited, level, nodes, max_level);
showClockWise(nodes, max_level);
return 0;
}
輸出
1 3 7 6 5 4 2
時間複雜度 − O(N)
空間複雜度 − O(N)
結論
程式設計師可能會嘗試以逆時針方向遍歷二叉樹。為此，他們可以先遍歷左邊界，然後是底邊界，最後是右邊界。此外，他們可以像我們在這個問題中所做的那樣，一個接一個地遍歷內邊界。
瀏覽量 156
