資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中將任意二叉樹轉換為持有子節點和屬性的樹
本教程，我們將討論一個程式，該程式將任意二叉樹轉換為樹，保留子節點和屬性。
為此，我們將提供一個二叉樹。我們的任務是將其轉換為遵循子節點和屬性的二叉樹。但限制是，我們只能增加節點中的值，既不能改變樹的結構也不能降低節點中的值。
示例
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
//node structure for binary tree
class node{
public:
int data;
node* left;
node* right;
//creation of new node
node(int data){
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
//incrementing left subtree
void increment(node* node, int diff);
//main function converting the tree
void convert_Btree(node* node){
int left_data = 0, right_data = 0, diff;
//returning true in case of root
//or leaf node
if (node == NULL || (node->left == NULL &&
node->right == NULL))
return;
else {
//converting left and right subtrees
convert_Btree(node->left);
convert_Btree(node->right);
if (node->left != NULL)
left_data = node->left->data;
if (node->right != NULL)
right_data = node->right->data;
//getting children sum
diff = left_data + right_data - node->data;
//if children sum is greater than node data
if (diff > 0)
node->data = node->data + diff;
if (diff > 0)
increment(node, -diff);
}
}
//incrementing the node value
void increment(node* node, int diff){
if(node->left != NULL) {
node->left->data = node->left->data + diff;
//moving recursively in the tree
increment(node->left, diff);
}
else if (node->right != NULL) {
node->right->data = node->right->data + diff;
increment(node->right, diff);
}
}
//printing inorder traversal
void printInorder(node* node){
if (node == NULL)
return;
printInorder(node->left);
cout<<node->data<<" ";
printInorder(node->right);
}
int main(){
node *root = new node(50);
root->left = new node(7);
root->right = new node(2);
root->left->left = new node(3);
root->left->right = new node(5);
root->right->left = new node(1);
root->right->right = new node(30);
cout << "Before conversion: " << endl;
printInorder(root);
convert_Btree(root);
cout << "\nAfter conversion: " << endl;
printInorder(root);
return 0;
}輸出
Before conversion: 3 7 5 50 1 2 30 After conversion: 14 19 5 50 1 31 30
更新於:2020 年 1 月 16 日
154 次瀏覽
廣告