從給定的 N 個節點的非迴圈圖構建一棵素數二叉樹

介紹

在程式設計和資料結構領域，二叉樹被廣泛用於高效地儲存和檢索資料。本文將探討使用 C++ 程式碼從給定的由 N 個節點組成的非迴圈圖構建素數二叉樹的概念。二叉樹可以從非迴圈圖構建，此類圖的型別包括樹、有向無環圖等等。素數樹屬於二叉樹的一個分支，透過附加圖的兩個連續邊來返回素數。

從給定的非迴圈圖構建素數二叉樹

素數二叉樹是普通二叉搜尋樹 (BST) 的一個有趣變體。在 BST 中，每個節點有兩個子節點：一個位於其左側，值較小；另一個位於其右側，值較大。素數二叉樹採用了這個概念，但附加了一個約束條件：左子樹中的每個節點都必須小於右子樹中的任何節點。

示例

在上圖的二叉樹中，根節點選擇為節點 0，它有兩個子節點，左子節點為 1，右子節點為 2。左子節點進一步有兩個子節點，分別為節點 3 和節點 4。由此構建的素數二叉樹為 0 2 5。

方法 1：使用 C++ 程式碼從給定的 N 個節點的非迴圈圖構建素數二叉樹

我們首先包含必要的標準 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;
}

輸出

0 2 5

結論

本文探討了如何使用 C++ 程式碼從給定的 N 個節點的非迴圈圖構建素數二叉樹。透過遵循上述逐步方法，程式設計師可以有效地在各種應用中實現這種資料結構。程式碼使用遞迴函式返回素數二叉樹。

更新於: 2023-08-25

77 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

立即開始
廣告