二叉树的顺时针三角遍历
在本问题中，我们将创建一个完全二叉树并以顺时针方向循环遍历它。
对于顺时针遍历，我们可以考虑遍历树的边界。例如，我们可以先遍历树的外边界。然后，我们可以删除访问过的节点并遍历树的内边界。这样，我们需要对给定的二叉树进行 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 循环进行遍历，并在循环内使用 false 值定义 'isChild'。
步骤 1.3 - 如果 2*p 小于或等于 n，则在 p 和 2*p 节点之间添加一条边。在这里，我们使用向量列表来创建二叉树。因此，在 2*p 位置插入 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 条件满足时进行迭代true。
步骤 3.3 - 接下来，我们需要遍历右边界。因此，使用循环进行迭代，直到 levelNo 小于 maxLevel - cycle。此外，从 nodes[levelNo] 列表中获取最后一个节点，打印其值，并将 levelNo 增加 1。
步骤 3.4 - 现在，我们需要遍历树的底部。
步骤 3.5 - 如果 levelNo == max_level - cycle 条件为真，则遍历底部节点。
步骤 3.6 - 遍历树的左边界。根据"cycle"变量的值，它可以是内边界或外边界。
步骤 3.7 - 将 cycle 值增加 1，并使用 cycle + 1 更新 levelNo。
示例
#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[]) {
// 创建一棵完全二叉树
for (int p = 1;; p++) {
// 向树添加边
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;
// 将根节点插入队列并将其标记为已访问
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;
// 获取相邻顶点
for (int child : tree[temp.first]) {
if (!visited[child]) {
que.push({child, temp.first});
level[child] = level[temp.first] + 1;
// 更新最大级别
max_level = max(max_level, level[child]);
// 按级别存储节点
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) {
// 遍历右侧节点
while (levelNo < max_level - cycle) {
int q = nodes[levelNo].size() - 1;
cout << nodes[levelNo][q - cycle] << " ";
levelNo++;
}
// 从右侧 -> 左侧遍历底部节点
if (levelNo == max_level - cycle) {
int q = nodes[levelNo].size() - 1;
for (q -= cycle; q >= cycle; q--)
cout << nodes[levelNo][q] << " ";
}
levelNo--;
// 遍历左侧节点
while (levelNo > cycle) {
cout << nodes[levelNo][cycle] << " ";
levelNo--;
}
// 增加 cycle
cycle++;
// 更新下一个级别以从其开始
levelNo = cycle + 1;
}
}
int main() {
// 顶点数
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)
结论
程序员可能会尝试以逆时针方向遍历二叉树。为此，他们可以先遍历左边界，然后遍历底部边界，最后遍历右边界。此外，他们可以逐一遍历内部边界，就像我们在这个问题中所做的那样。
