具有最多M個連續節點且值為K的從根到葉子的路徑數量

簡介

二元樹是一種令人著迷的資料結構，在電腦科學和程式設計中有著廣泛的應用。一個有趣的問題是從給定的由父節點及其子節點組成的樹中尋找計數。二元樹由節點組成，根節點決定，根節點可以根據使用者需求給出子節點。 K值決定，移動方式由M值選擇。

根到葉路徑的計數

該圖是使用各種節點創建的，這些節點保存整數形式的值。本文主要關注從起始節點或根節點到葉節點或子節點的計數。

範例

該圖是從具有各種節點的二元樹創建的。

• #在上面的二元樹中，根節點選擇為「8」。

• 接著建立兩個節點，一個值為 3，另一個值為 10，佔據根節點的左右位置。

• 以值為 2 的節點為根，建立另一個子節點，其值分別為 2 和 1 作為左節點和右節點。

• 最後，值為 1 的子節點建立值為 -4 的子節點。

方法 1：使用遞迴函數計算由最多 M 個具有 K 值的連續節點組成的根到葉路徑的 C 程式碼

為了有效地解決這個問題，我們將利用樹遍歷演算法和遞歸等基本概念。

演算法

第 1 步：建立一個用於表示樹節點的結構，其中包括兩個指標（左子節點和右子節點）以及用於儲存節點值的整數欄位。

第2 步：設計一個遞歸函數，從根開始遍歷二元樹，同時追蹤當前路徑長度（初始化為0）、連續出現次數（初始設定為0）、目標值K，允許的最大連續出現次數M。

第 3 步：在每個左子樹和右子樹上遞歸呼叫函數，並傳遞更新的參數，例如遞增的路徑長度和連續出現次數（如果適用）。

第4步：對於遍歷過程中每個訪問過的非空節點：

a) 如果其值等於 K，則將兩個變數都加一。

b) 如果其值與 K 不符或超過迄今為止在路徑中已遇到的 M 連續出現次數，則將變數重設為零。

第5步：在遍歷樹時，如果子節點在左和右兩種情況下的值都為零 - 我們可以用兩種方式處理，即

a) 檢查變數是否不超過M。

b) 如果是，則將滿足條件的路徑總數增加 1。

範例

//including the all in one header
#include<bits/stdc++.h>
using namespace std;
//creating structure with two pointers as up and down
struct Vertex {
   int data;
   struct Vertex* up;
   struct Vertex* down;
};
//countPaths function declared with five arguments ; with root = end; Node= vertex; left = up; right = down
int countPaths(Vertex* end, int K, int M, int currCount, int 
consCount) {
//To check the condition when the root is equal to 1 and greater than the maximum value, the values is incremented
   if (end == NULL || consCount > M) {
      return 0;
   }
//To check when the root is equal to the K value, increment by 1
   if (end->data == K) {
      currCount++;
      consCount++;
   } else {
//If it is not equal, it will return 0
      currCount = 0;
   }
   if (end->up == NULL && end->down == NULL) {
      if (currCount <= M) {
         return 1;
      } else {
         return 0;
      }
   }
   return countPaths(end->up, K, M, currCount, consCount) + countPaths(end->down, K, M, currCount, consCount);
}
//Main function to test the implementation
int main() {
   Vertex* end = new Vertex();
   end->data = 8;
   end->up = new Vertex();
   end->up->data = 3;
   end->down = new Vertex();
   end->down->data = 10;
   end->up->up = new Vertex();
   end->up->up->data = 2;
   end->up->down = new Vertex();
   end->up->down->data = 1;
   end->up->down->up = new Vertex();
   end->up->down->up->data = -4;

   int K = 1; // Value of node
   int M = 2; // Maximum consecutive nodes
   int currCount = -1; // Current count
   int consCount = -1; // Consecutive count

   cout << "The number of paths obtained from the given graph of" << M << "nodes with a value of " << K << " is " << countPaths(end, K, M, currCount, consCount) << endl;

   return 0;
} 

輸出

The number of paths obtained from the given graph of 2 nodes with a value of 1 is 3

結論

在本文中，我們探討了計算從頂部（即葉）到末端或根的路徑數的問題。透過使用 C 中的樹遍歷演算法和遞歸技術，可以有效地解決此類問題。遍歷二元樹的過程看起來很困難，但透過範例就變得簡單了。

以上是具有最多M個連續節點且值為K的從根到葉子的路徑數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！