資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++實現完全二叉樹中序遍歷映象節點之和
在這個問題中，我們得到一棵完全二叉樹。我們的任務是建立一個程式來查詢完全二叉樹中映象節點的中序遍歷之和。
在這裡，我們必須找到左子樹的中序遍歷，然後為每個節點新增其映象節點的值。這意味著如果我們正在遍歷左葉子節點，我們將把右葉子節點的值加到它上面，因為它就是映象節點。
一些重要的定義
完全二叉樹是二叉樹，其中除最後一層外，所有層都具有最大數量的節點。
中序遍歷是一種樹遍歷技術，其中首先訪問左子樹，然後訪問根節點，最後訪問右子樹。
讓我們舉個例子來理解這個問題：
輸入
輸出 − 9 9 17 2
解釋 − 左子樹的中序遍歷是 5-7-8-1。
將所有節點與其映象節點的值相加。
5 + 4 = 9 7 + 2 = 9 8 + 9 = 17 1 + 1 = 2
為了解決這個問題，我們將使用中序遍歷來遍歷二叉樹。我們將使用兩個節點，一個用於遍歷左子樹，另一個用於訪問節點的映象。例如，我們有左子樹的根節點，我們將有一個映象根節點來遍歷它的映象。
示例
程式演示解決方案的工作原理：
#include <iostream>
using namespace std;
typedef struct node {
int data;
struct node* left;
struct node* right;
node(int d){
data = d;
left = NULL;
right = NULL;
}
} Node;
void printMirrorSum(Node* root, Node* rootMirror){
if (root->left == NULL && rootMirror->right == NULL)
return;
printMirrorSum(root->left, rootMirror->right);
cout<<(root->left->data + rootMirror->right->data)<<endl;
printMirrorSum(root->right, rootMirror->left);
}
int main(){
Node* root = new Node(1);
root->left = new Node(7);
root->right = new Node(2);
root->left->left = new Node(5);
root->left->right = new Node(8);
root->right->left = new Node(9);
root->right->right = new Node(4);
cout<<"Sum of node and mirror image nodes are :\n";
printMirrorSum(root, root);
if (root)
cout<<(root->data + root->data);
return 0;
}輸出
Sum of node and mirror image nodes are : 9 9 17 2
更新於: 2020年8月6日
瀏覽量 131
廣告