資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究二叉樹中等腰三角形的數量
二叉樹是一種資料結構，其中每個節點最多可以有兩個子節點。這兩個子節點分別稱為左子節點和右子節點。假設我們給定一個父節點陣列表示，使用該陣列可以建立一個二叉樹。二叉樹可能包含多個等腰三角形。我們必須找到該二叉樹中所有可能的等腰三角形的總數。
在本文中，我們將探討在 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
結論
我們討論瞭如何在給定父節點陣列的情況下找到二叉樹中等腰三角形的總數。我們可以透過使用深度優先搜尋來做到這一點，深度優先搜尋允許我們遍歷二叉樹。
105 次檢視
