Respuesta :
Using the knowledge of computational language in C++ it is possible to write a code that binary tree written as a sequence of parent child pairs you need to detect any errors
Writting the code:
#include <bits/stdc++.h>
using namespace std;
// Helper class that allocates a new
// node with the given key and None
// left and right pointer.
class newNode{
public:
int key;
newNode*right,*left;
newNode(int k){
this->key = k;
this->right = this->left = NULL;
}
};
// This functions gets the size of binary tree
// Basically, the number of nodes this binary tree has
int getLength(newNode* root){
if(root == NULL)
return 0;
return 1 + getLength(root->left) + getLength(root->right);
}
// Returns True if length of binary tree is a power of 2 else False
bool isPerfect(newNode* root){
int length = getLength(root);
return length & (length+1) == 0;
}
int main()
{
newNode* root = new newNode(10);
root->left = new newNode(20);
root->right = new newNode(30);
root->left->left = new newNode(40);
root->left->right = new newNode(50);
root->right->left = new newNode(60);
root->right->right = new newNode(70);
if (isPerfect(root))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
Finding the lexicographically smallest diameter in a binary tree
/ C++ program
#include <bits/stdc++.h>
using namespace std;
// Binary Tree Node
struct node {
char data;
node *left, *right;
};
// Utility function to create a new node
node* newNode(char data)
{
node* c = new node;
c->data = data;
c->left = c->right = NULL;
return c;
}
// Function to compare and return
// lexicographically smallest vector
vector<node*> compare(vector<node*> a, vector<node*> b)
{
for (int i = 0; i < a.size() && i < b.size(); i++) {
if (a[i]->data < b[i]->data) {
return a;
}
if (a[i]->data > b[i]->data) {
return b;
}
}
return a;
}
// Function to find diameter
int diameter(node* root, int& height, vector<node*>& dia,
vector<node*>& heightv)
{
// If root is null
if (!root) {
height = 0;
return 0;
}
// Left height and right height
// respectively
int lh = 0, rh = 0;
// Left tree diameter and
// right tree diameter
int ld, rd;
vector<node*> leftdia;
vector<node*> rightdia;
vector<node*> leftheight;
vector<node*> rightheight;
// Left subtree diameter
ld = diameter(root->left, lh, leftdia, leftheight);
// Right subtree diameter
rd = diameter(root->right, rh, rightdia, rightheight);
// If left height is more
// than right tree height
if (lh > rh) {
// Add current root so lh + 1
height = lh + 1;
// Change vector heightv to leftheight
heightv = leftheight;
// Insert current root in the path
heightv.push_back(root);
}
// If right height is
// more than left tree height
else if (rh > lh) {
// Add current root so rh + 1
height = rh + 1;
// Change vector heightv to rightheight
heightv = rightheight;
// Insert current root in the path
heightv.push_back(root);
}
//Both height same compare
// lexicographically now
else {
// Add current root so rh + 1
height = rh + 1;
// Lexicographical comparison between two vectors
heightv = compare(leftheight, rightheight);
// Insert current root in the path
heightv.push_back(root);
}
// If distance of one leaf node to another leaf
// containing the root is more than the left
// diameter and right diameter
if (lh + rh + 1 > max(ld, rd)) {
// Make dia equal to leftheight
dia = leftheight;
// Add current root into it
dia.push_back(root);
for (int j = rightheight.size() - 1; j >= 0; j--) {
// Add right tree (right to root) nodes
dia.push_back(rightheight[j]);
}
}
// If either leftdiameter containing the left
// subtree and root or rightdiameter containing
// the right subtree and root is more than
// above lh+rh+1
else {
// If diameter of left tree is
// greater our answer vector i.e
// dia is equal to leftdia then
if (ld > rd) {
dia = leftdia;
}
// If both diameter
// same check lexicographically
else if (ld == rd) {
dia = compare(leftdia, rightdia);
}
// If diameter of right tree
// is greater our answer vector
// i.e dia is equal to rightdia then
else {
dia = rightdia;
}
}
return dia.size();
}
// Driver code
int main()
{
node* root = newNode('a');
root->left = newNode('b');
root->right = newNode('c');
root->left->left = newNode('d');
root->left->right = newNode('e');
root->right->left = newNode('f');
root->right->right = newNode('g');
int height = 0;
vector<node *> dia, heigh;
cout << "Diameter is: " << diameter(root, height,
dia, heigh)
<< endl;
// Printing the lexicographically smallest diameter
cout << "Lexicographically smallest diameter:" << endl;
for (int j = 0; j < dia.size(); j++) {
cout << dia[j]->data << " ";
}
return 0;
}
See more about C++ code at brainly.com/question/12975450
#SPJ1
