数据结构
网络
关系数据库管理系统 (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
