C++ 二叉树的顺时针三角形遍历

在这个问题中，我们将创建一棵完全二叉树并以顺时针的方向遍历它。

对于顺时针遍历，我们可以将其视为遍历树的边界。例如，我们可以首先遍历树的外边界。然后，我们可以移除已经访问的节点并遍历树的内边界。通过这种方式，我们需要进行min(height/2, width/2)次遍历给定的二叉树。

问题陈述

我们已经给定了一棵包含N个节点的完全二叉树，需要以顺时针的方向遍历它。

示例示范

输入

输出

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 - 如果 2p 小于等于 n，添加一个边连接 p 和 2p 节点。在这里，我们使用向量列表来创建二叉树。所以，在 2p 的位置插入 p，以添加 p 和 2p 之间的边。同时，将 isChild 设置为 true。
步骤 1.4 - 如果 2p + 1 小于等于 n，插入一个边连接 p 和 2p + 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 − Finally, print the value of the root node.

将周期值递增1，并使用周期+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[]) {
   // 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;
}