C++ 从给定的非循环图N个索引构造一个质数二叉树

介绍

在编程和数据结构领域，二叉树被广泛用于高效地存储和检索数据。在本文中，我们将探讨使用C++代码从给定的非循环图中构造一个质数二叉树的概念。二叉树可以由非循环图构造而成，该图类型为树、有向无环图等。质数树属于二叉树的一种，通过将图的两个连续边附加在一起返回质数。

从给定的非循环图构造一个质数二叉树

质数二叉树是常规二叉搜索树（BST）的一种有趣变体。在BST中，每个节点有两个子节点：左子节点值较小，右子节点值较大。质数二叉树采用了这个概念，但是增加了一个额外的约束条件：左子树中的每个节点都必须小于右子树中的任何节点。

示例

C++ 从给定的非循环图N个索引构造一个质数二叉树

在上面的二叉树中，根节点选择为节点0，它有两个子节点：左子节点1和右子节点2。左子节点进一步有两个子节点：节点3和节点4。从中构造的质数二叉树为0 2 5。

方法1：构造一个从给定非循环图中的N个索引构造质数二叉树的C++代码

我们首先包含必要的标准C++库，比如iostream。然后创建节点和图的类来高效地表示结构。

算法

步骤 1 - 创建一个类 Node，包含三个成员 – index、leftChild 和 rightChild。
步骤 2 - 创建一个函数 createNode，它接受一个整数参数并返回一个具有给定索引和空左右子节点的新节点。
步骤 3 - 创建一个函数 isprime()，用于检查节点是否为质数。
步骤 4 - 创建一个函数 printTree，它接受指向二叉树根节点的指针，并打印树的前序遍历。
步骤 5 - 创建一个函数 constructPrimeBinaryTree，它接受三个参数：图的邻接表的引用、访问数组的引用和当前节点的指针。该函数使用邻接表和访问数组递归地构建具有质数的二叉树。对于当前节点的每个未被访问且与当前节点的索引之和为质数的邻居，如果当前节点的左子节点为空，则创建一个具有邻居索引的新节点并将其作为左子节点，否则将其作为右子节点。然后在新节点上递归地调用 constructPrimeBinaryTree()。
步骤 6 - 在 main 函数中：
- 将变量 n 初始化为6，即树中的节点数。
- 将变量 adjList 初始化为表示图的邻接表的向量。
- 为 adjList 的每个元素添加邻居。
- 将变量 visited 初始化为表示节点是否已访问的向量。
- 设置 visited[0] 为 true，因为节点 0 是根节点。
- 创建变量 root，它是使用函数 createNode(0) 创建的根节点的指针。
- 调用函数 constructPrimeBinaryTree(adjList, visited, root) 使用邻接表和访问数组构建具有质数的二叉树。
- 调用函数 printTree(root) 以前序遍历打印树。

示例

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Node {
   public:
      int index;
      Node* leftChild;
      Node* rightChild;

      Node(int idx) : index(idx), leftChild(nullptr), rightChild(nullptr) {}
};

Node* createNode(int idx) {
   return new Node(idx);
}

bool isPrime(int n) {
   if (n <= 1)
      return false;
   for (int i = 2; i * i <= n; i++)
      if (n % i == 0)
         return false;
      return true;
}

void printTree(Node* root) {
   if (root == nullptr)
      return;

   cout << root->index << " ";
   printTree(root->leftChild);
   printTree(root->rightChild);
}

void constructPrimeBinaryTree(vector<vector<int>>& adjList, vector<bool>& visited, Node* curr) {
   for (int neighbor : adjList[curr->index]) {
      if (!visited[neighbor] && isPrime(curr->index + neighbor)) {
         visited[neighbor] = true;
         Node* newNode = createNode(neighbor);
         if (curr->leftChild == nullptr)
            curr->leftChild = newNode;
         else
            curr->rightChild = newNode;
            constructPrimeBinaryTree(adjList, visited, newNode);
      }
   }
}
int main() {
   int n = 6;

   vector<vector<int>> adjList(n);
   adjList[0].push_back(1);
   adjList[0].push_back(2);
   adjList[1].push_back(3);
   adjList[1].push_back(4);
   adjList[2].push_back(5);

   vector<bool> visited(n, false);
   visited[0] = true;
   Node* root = createNode(0);

   constructPrimeBinaryTree(adjList, visited, root);

   printTree(root);

   return 0;
}