二元樹中等腰三角形的數量

二元樹是一種資料結構，其中每個節點最多可以有兩個子節點。這些孩子分別稱為左孩子和右孩子。假設我們得到了一個父數組表示，您必須使用它來建立一棵二元樹。二元樹可能有幾個等腰三角形。我們必須找到該二元樹中可能的等腰三角形的總數。

在本文中，我們將探討幾種在C 中解決這個問題的技術。

理解問題

給你一個父數組。您必須以二元樹的形式表示它，以便數組索引形成樹節點的值，而數組中的值給出該特定索引的父節點。

請注意，-1 總是根父節點。下面給出的是一個數組及其二元樹表示。

Parent array = [0, -1, 3, 1, 1, 2, 2, 3, 4, 4]

二元樹 -

##在任何二元樹中，我們都可以三種類型的等腰三角形 -

• 左等腰三角形 − 在這個三角形中，頂點是一個左邊的父節點的子節點，而形成底邊（等腰三角形的兩邊）的頂點是頂點的左子節點。子節點可以是直接的或間接的。在上面的樹中，我們有兩個這樣的等腰三角形-（2, 6, 3），（3, 7, 1）。

• #直角等腰三角形 − 在此三角形中，頂點是右父級的子級，而形成基部的頂點是頂點的右子級。孩子可以是直接的或間接的。在上面的樹中，我們只有一個這樣的等腰三角形 (4, 1, 8)。

• #平衡等腰三角形 − 在此三角形中，形成底邊的頂點是頂點節點的左子節點和右子節點。在上面的樹中，我們有五個這樣的等腰三角形(1, 3, 4), (3, 2, 7), (4, 8, 9), (2, 5, 6), (1, 2, 9)

#因此，對於上述二元樹，我們共有8個等腰三角形。

使用深度優先搜尋遍歷

深度優先搜尋（DFS）是一種以深度方式遍歷樹的所有節點的方法。它從根節點開始，移動到每個分支，然後回溯。

• 首先，我們使用DFS遍歷二元樹的每個節點，並將其轉換為圖，以便每個節點表示為彼此相鄰。這使得遍歷更加容易。

• 對於每個節點，我們檢查它是否有子節點。在檢查完後，我們使用 sort(node[x].begin(), node[x].end()) 函數對它們進行排序。

• 接下來，我們檢查目前節點是否是其對應父節點的左或右後繼節點。我們對二元樹的所有節點遞歸使用DFS函數。

• 如果目前節點有兩個子節點（直接或間接），我們透過計算它們之間的邊來檢查存在等腰三角形的可能性。我們將透過下面程式碼中給出的 graph 函數找到它們之間的邊。

• 最後，我們透過將不同位置的所有可能的三角形相加來計算等腰三角形的總數。

範例

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAX int(1e5)
vector < int > * node;
int right_down[MAX];
int right_up[MAX];
int left_down[MAX];
int left_up[MAX];

// DFS traversal over a node
void DFS(int x, int * parent) {
   // Check if adjacent nodes are present for node x
   if (node[x].size() != 0)
      sort(node[x].begin(), node[x].end());

   // Check whether the node has a parent node
   if (parent[x] != -1) {
      int indexOfParent = parent[x];
      int childrenCount = node[indexOfParent].size();

      if (childrenCount > 1) {
         int parentFirstChild = node[indexOfParent][0];

         // Check if current node is left node of the parent
         if (x == parentFirstChild) {
            right_up[x] += right_up[indexOfParent] + 1;
            // Check if current node is right node of the parent  
         } else {
            left_up[x] += left_up[indexOfParent] + 1;
         }
      } else {
         right_up[x] += right_up[indexOfParent] + 1;
      }
   }

   // Iterate over children of current node  
   for (int i = 0; i < node[x].size(); ++i) {
      int y = node[x][i];
      DFS(y, parent);

      // left child of current node
      if (i == 0) {
         left_down[x] += left_down[y] + 1;
      }
      // right child of current node
      else {
         right_down[x] += right_down[y] + 1;
      }
   }
}

int graph(int * parent, int N) {
   int rootNode;
   node = new vector < int > [N];

   for (int i = 0; i < N; ++i) {
      if (parent[i] != -1) {
         node[parent[i]].push_back(i);
      } else {
         rootNode = i;
      }

      left_up[i] = 0;
      right_up[i] = 0;
      left_down[i] = 0;
      right_down[i] = 0;
   }
   return rootNode;
}

int main() {
   int N = 10;
   int parent[] = { 0, -1, 3, 1, 1, 2, 2, 3, 4, 4 };
   int rootNode = graph(parent, N);
   DFS(rootNode, parent);
   int count = 0;
   // Counting the total isosceles triangles
   for (int i = 0; i < N; ++i) {
      count += min(right_down[i], right_up[i]);
      count += min(left_down[i], left_up[i]);
      count += min(left_down[i], right_down[i]);
   }
   cout << "Number of isosceles triangles in the binary tree are " <<
      count;
   return 0;
}

輸出

Number of isosceles triangles in the binary tree are 8

結論

我們已經討論了當給定父數組時如何找到二元樹中等腰三角形的總數。我們可以透過使用深度優先搜尋來實現這一點，它允許我們遍歷二元樹。

以上是二元樹中等腰三角形的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！