Dado un árbol binario (cada Node tiene como máximo 2 hijos) donde cada Node tiene un valor de 0 o 1. Convierta un árbol binario dado en un árbol que tenga la propiedad Y lógico, es decir, cada valor de Node debe ser el Y lógico entre sus hijos. .
Ejemplos:
C++
// C++ code to convert a given binary tree
// to a tree that holds logical AND property.
#include<bits/stdc++.h>
using namespace std;
// Structure of binary tree
struct Node
{
int data;
struct Node* left;
struct Node* right;
};
// function to create a new node
struct Node* newNode(int key)
{
struct Node* node = new Node;
node->data= key;
node->left = node->right = NULL;
return node;
}
// Convert the given tree to a tree where
// each node is logical AND of its children
// The main idea is to do Postorder traversal
void convertTree(Node *root)
{
if (root == NULL)
return;
/* first recur on left child */
convertTree(root->left);
/* then recur on right child */
convertTree(root->right);
if (root->left != NULL && root->right != NULL)
root->data = (root->left->data) &
(root->right->data);
}
void printInorder(Node* root)
{
if (root == NULL)
return;
/* first recur on left child */
printInorder(root->left);
/* then print the data of node */
printf("%d ", root->data);
/* now recur on right child */
printInorder(root->right);
}
// main function
int main()
{
/* Create following Binary Tree
1
/ \
1 0
/ \ / \
0 1 1 1
*/
Node *root=newNode(0);
root->left=newNode(1);
root->right=newNode(0);
root->left->left=newNode(0);
root->left->right=newNode(1);
root->right->left=newNode(1);
root->right->right=newNode(1);
printf("\n Inorder traversal before conversion ");
printInorder(root);
convertTree(root);
printf("\n Inorder traversal after conversion ");
printInorder(root);
return 0;
}
Java
// Java code to convert a given binary tree
// to a tree that holds logical AND property.
class GfG {
// Structure of binary tree
static class Node
{
int data;
Node left;
Node right;
}
// function to create a new node
static Node newNode(int key)
{
Node node = new Node();
node.data= key;
node.left = null;
node.right = null;
return node;
}
// Convert the given tree to a tree where
// each node is logical AND of its children
// The main idea is to do Postorder traversal
static void convertTree(Node root)
{
if (root == null)
return;
/* first recur on left child */
convertTree(root.left);
/* then recur on right child */
convertTree(root.right);
if (root.left != null && root.right != null)
root.data = (root.left.data) & (root.right.data);
}
static void printInorder(Node root)
{
if (root == null)
return;
/* first recur on left child */
printInorder(root.left);
/* then print the data of node */
System.out.print(root.data + " ");
/* now recur on right child */
printInorder(root.right);
}
// main function
public static void main(String[] args)
{
/* Create following Binary Tree
1
/ \
1 0
/ \ / \
0 1 1 1
*/
Node root=newNode(0);
root.left=newNode(1);
root.right=newNode(0);
root.left.left=newNode(0);
root.left.right=newNode(1);
root.right.left=newNode(1);
root.right.right=newNode(1);
System.out.print("Inorder traversal before conversion ");
printInorder(root);
convertTree(root);
System.out.println();
System.out.print("Inorder traversal after conversion ");
printInorder(root);
}}
Python3
# Program to convert an aribitary binary tree
# to a tree that holds children sum property
# Helper function that allocates a new
# node with the given data and None
# left and right pointers.
class newNode:
# Construct to create a new node
def __init__(self, key):
self.data = key
self.left = None
self.right = None
# Convert the given tree to a tree where
# each node is logical AND of its children
# The main idea is to do Postorder traversal
def convertTree(root) :
if (root == None) :
return
""" first recur on left child """
convertTree(root.left)
""" then recur on right child """
convertTree(root.right)
if (root.left != None and root.right != None):
root.data = ((root.left.data) &
(root.right.data))
def printInorder(root) :
if (root == None) :
return
""" first recur on left child """
printInorder(root.left)
""" then print the data of node """
print( root.data, end = " ")
""" now recur on right child """
printInorder(root.right)
# Driver Code
if __name__ == '__main__':
""" Create following Binary Tree
1
/ \
1 0
/ \ / \
0 1 1 1
"""
root = newNode(0)
root.left = newNode(1)
root.right = newNode(0)
root.left.left = newNode(0)
root.left.right = newNode(1)
root.right.left = newNode(1)
root.right.right = newNode(1)
print("Inorder traversal before conversion",
end = " ")
printInorder(root)
convertTree(root)
print("\nInorder traversal after conversion ",
end = " ")
printInorder(root)
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# code to convert a given binary tree
// to a tree that holds logical AND property.
using System;
class GfG
{
// Structure of binary tree
class Node
{
public int data;
public Node left;
public Node right;
}
// function to create a new node
static Node newNode(int key)
{
Node node = new Node();
node.data= key;
node.left = null;
node.right = null;
return node;
}
// Convert the given tree to a tree where
// each node is logical AND of its children
// The main idea is to do Postorder traversal
static void convertTree(Node root)
{
if (root == null)
return;
/* first recur on left child */
convertTree(root.left);
/* then recur on right child */
convertTree(root.right);
if (root.left != null && root.right != null)
root.data = (root.left.data) & (root.right.data);
}
static void printInorder(Node root)
{
if (root == null)
return;
/* first recur on left child */
printInorder(root.left);
/* then print the data of node */
Console.Write(root.data + " ");
/* now recur on right child */
printInorder(root.right);
}
// Driver code
public static void Main()
{
/* Create following Binary Tree
1
/ \
1 0
/ \ / \
0 1 1 1
*/
Node root=newNode(0);
root.left=newNode(1);
root.right=newNode(0);
root.left.left=newNode(0);
root.left.right=newNode(1);
root.right.left=newNode(1);
root.right.right=newNode(1);
Console.Write("Inorder traversal before conversion ");
printInorder(root);
convertTree(root);
Console.WriteLine();
Console.Write("Inorder traversal after conversion ");
printInorder(root);
}
}
/* This code is contributed by Rajput-Ji*/
Javascript
<script>
// Javascript code to convert a given binary tree
// to a tree that holds logical AND property.
// Structure of binary tree
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
}
// Function to create a new node
function newNode(key)
{
var node = new Node();
node.data = key;
node.left = null;
node.right = null;
return node;
}
// Convert the given tree to a tree where
// each node is logical AND of its children
// The main idea is to do Postorder traversal
function convertTree(root)
{
if (root == null)
return;
/* First recur on left child */
convertTree(root.left);
/* Then recur on right child */
convertTree(root.right);
if (root.left != null && root.right != null)
root.data = (root.left.data) & (root.right.data);
}
function printInorder(root)
{
if (root == null)
return;
/* First recur on left child */
printInorder(root.left);
/* then print the data of node */
document.write(root.data + " ");
/* Now recur on right child */
printInorder(root.right);
}
// Driver code
/* Create following Binary Tree
1
/ \
1 0
/ \ / \
0 1 1 1
*/
var root = newNode(0);
root.left = newNode(1);
root.right = newNode(0);
root.left.left = newNode(0);
root.left.right = newNode(1);
root.right.left = newNode(1);
root.right.right = newNode(1);
document.write("Inorder traversal before conversion ");
printInorder(root);
convertTree(root);
document.write("<br>");
document.write("Inorder traversal after conversion ");
printInorder(root);
// This code is contributed by noob2000
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA