数据结构
网络
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 次浏览
广告