資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中計算二叉樹中和等於給定值 x 的對數
給定一個整數值和一個變數 x，任務是構建二叉樹並找到和等於給定值 x 的對。
例如
輸入
int x = 5，輸入值後建立的樹如下所示：
輸出
Count of pairs in a binary tree whose sum is equal to a given value x are: 2
解釋
we are given with an array of integer values that is used to form a binary tree and we will check whether there is a pair present in a binary tree whose sum equals to the given value x which is 5. So, the pairs formed are (2, 3) and (1, 4).
輸入
int x = 8，輸入值後建立的樹如下所示：
輸出
Count of pairs in a binary tree whose sum is equal to a given value x are: 3
解釋
we are given with an array of integer values that is used to form a binary tree and we will check whether there is a pair present in a binary tree whose sum equals to the given value x which is 8. So, the pairs formed are (2, 6), (4, 4) and (5, 3).
以下程式中使用的方案如下：
建立一個節點結構，包含資料部分以及指向左子樹和右子樹的左指標和右指標。
輸入一個整數值，並使用它們透過左指標和右指標將資料輸入節點，從而建立二叉樹。
輸入 x 的值，該值將用於計算和值為 x 的對。
建立一個布林函式來檢查對的和是否為 x。
在函式內部，檢查根是否為 NULL，如果是則返回 False
檢查根是否不等於 ptr 並且根的資料 + ptr 的資料是否等於 x，如果是則返回 True。
透過傳遞根的左指標、ptr 和值 x 以及 x 的右指標、ptr 和 x 來遞迴呼叫 check 函式。現在檢查任何條件是否返回 true，如果是則返回 true。
否則，返回 false。
建立一個函式 total_pairs 來計算和為 x 的對的數量
在函式內部，檢查 ptr 是否為 NULL，如果是則返回 0。
透過傳遞根、ptr 和 x 作為引數來呼叫 check 函式。如果函式返回 true，則將總對數的值加 1
透過傳遞根、ptr 的左指標、x 和總計來遞迴呼叫函式 total_pairs，並且還傳遞根、ptr 的右指標、x 和總計。
將儲存在變數 total 中的整數值作為結果打印出來。
示例
#include <bits/stdc++.h>
using namespace std;
struct tree_node {
int data;
tree_node *left, *right;
};
tree_node* create_node(int data){
tree_node* newNode = (tree_node*)malloc(sizeof(tree_node));
newNode−>data = data;
newNode−>left = newNode−>right = NULL;
}
bool check(tree_node* root, tree_node* ptr, int x){
if(root==NULL){
return false;
}
if (root != ptr && ((root−>data + ptr−>data) == x)){
return true;
}
if (check(root−>left, ptr, x) || check(root−>right, ptr, x)){
return true;
}
return false;
}
void total_pairs(tree_node* root, tree_node* ptr, int x, int& total){
if(ptr == NULL){
return;
}
if(check(root, ptr, x) == true){
total++;
}
total_pairs(root, ptr−>left, x, total);
total_pairs(root, ptr−>right, x, total);
}
int main(){
int x = 5;
int total = 0;
tree_node* root = create_node(5);
root−>left = create_node(2);
root−>right = create_node(3);
root−>left−>left = create_node(1);
root−>left−>right = create_node(4);
root−>right−>left = create_node(6);
total_pairs(root, root, x, total);
total = total / 2;
cout<<"Count of pairs in a binary tree whose sum is equal to a given value x are: "<< total;
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Count of pairs in a binary tree whose sum is equal to a given value x are: 2
更新於：2021年1月7日
176 次檢視
廣告