資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中二叉樹的對角線之和？
考慮穿過斜率為 -1 的直線的節點。二叉樹的對角線之和將透過計算這些參考線之間存在的節點資料之和來計算。
首先，讓我們定義一個結構體，它將表示一個樹節點，其中包含資料及其左右子節點。如果這是第一個建立的節點，則它是根節點，否則是子節點。
struct Node {
int data;
struct Node *leftChild, *rightChild;
};接下來，我們建立 createNode(int data) 函式，該函式接收一個整數值並將其分配給建立新節點後節點的資料成員。該函式返回指向已建立節點的指標。
Node * createNode(int data){
Node * node = new Node;
node->data = data;
return node;
}接下來，diagonal_sum(Node *root, int depth, map<int, int> &diagonalSum) 透過引用接收根節點、當前深度和 diagonalSum 對映。如果 root 不為 NULL，則我們將當前根資料新增到 diagonalSum 對映中當前深度索引處，以獲得元素的總和。然後，我們在樹上執行遞迴中序遍歷，並在每次移動到左子節點時將深度加 1。
void diagonal_sum(Node *root, int depth, map<int, int> &diagonalSum){
if(root){
diagonalSum[depth]+=root->data;
diagonal_sum(root->leftChild, depth+1, diagonalSum);
diagonal_sum(root->rightChild, depth, diagonalSum);
}
}在我們的主函式內部，我們使用 createNode(data) 方法建立一個樹，並建立一個對映 SumMap。根節點、當前深度（為 1）和 sumMap 被髮送到 diagonal_sum，其中 sumMap 填充了鍵值對。接下來，我們建立迭代器 it 用於遍歷 sumMap 對映。
int main(){
Node *root = createNode(1);
root->rightChild = createNode(3);
root->rightChild->leftChild = createNode(4);
root->rightChild->leftChild->leftChild = createNode(12);
root->rightChild->leftChild->rightChild = createNode(7);
root->leftChild = createNode(2);
root->leftChild->leftChild = createNode(9);
root->leftChild->rightChild = createNode(6);
root->leftChild->leftChild->rightChild = createNode(10);
root->leftChild->rightChild->leftChild = createNode(11);
root->rightChild->rightChild = createNode(5);
map<int,int> sumMap;
diagonal_sum(root, 1, sumMap);
map<int,int>::iterator it;最後，我們使用 for 迴圈內部的迭代器 it 遍歷 SumMap 並列印對角線之和。
for(it=sumMap.begin(); it!=sumMap.end();++it){
int value = it->second;
cout<<value<<"\t";
}示例
讓我們看看以下查詢二叉樹的對角線之和的實現。
#include<iostream>
#include<map>
using namespace std;
struct Node{
int data;
struct Node* leftChild, *rightChild;
};
Node * createNode(int data){
Node * node = new Node;
node->data = data;
return node;
}
void diagonal_sum(Node *root, int depth, map<int, int> &diagonalSum){
if(root){
diagonalSum[depth]+=root->data;
diagonal_sum(root->leftChild, depth+1, diagonalSum);
diagonal_sum(root->rightChild, depth, diagonalSum);
}
}
int main(){
Node *root = createNode(1);
root->rightChild = createNode(3);
root->rightChild->leftChild = createNode(4);
root->rightChild->leftChild->leftChild = createNode(12);
root->rightChild->leftChild->rightChild = createNode(7);
root->leftChild = createNode(2);
root->leftChild->leftChild = createNode(9);
root->leftChild->rightChild = createNode(6);
root->leftChild->leftChild->rightChild = createNode(10);
root->leftChild->rightChild->leftChild = createNode(11);
root->rightChild->rightChild = createNode(5);
map<int,int> sumMap;
diagonal_sum(root, 1, sumMap);
map<int,int>::iterator it;
for(it=sumMap.begin(); it!=sumMap.end();++it){
int value = it->second;
cout<<value<<"\t";
}
return 0;
}輸出
以上程式碼將產生以下輸出：
91942
更新於: 2021-01-16
99 次檢視
廣告