Escriba un programa que convierta un árbol dado en su árbol doble. Para crear un árbol doble del árbol dado, cree un nuevo duplicado para cada Node e inserte el duplicado como el hijo izquierdo del Node original.
Entonces el árbol…
2 / \ 1 3
se cambia a…
C++
// C++ program to convert binary tree to double tree
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data,
pointer to left child and a
pointer to right child */
class node
{
public:
int data;
node* left;
node* right;
};
/* function to create a new
node of tree and returns pointer */
node* newNode(int data);
/* Function to convert a tree to double tree */
void doubleTree(node* Node)
{
node* oldLeft;
if (Node == NULL) return;
/* do the subtrees */
doubleTree(Node->left);
doubleTree(Node->right);
/* duplicate this node to its left */
oldLeft = Node->left;
Node->left = newNode(Node->data);
Node->left->left = oldLeft;
}
/* UTILITY FUNCTIONS TO TEST doubleTree() FUNCTION */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
node* newNode(int data)
{
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
/* Given a binary tree, print its nodes in inorder*/
void printInorder(node* node)
{
if (node == NULL)
return;
printInorder(node->left);
cout << node->data << " ";
printInorder(node->right);
}
/* Driver code*/
int main()
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout << "Inorder traversal of the original tree is \n";
printInorder(root);
doubleTree(root);
cout << "\nInorder traversal of the double tree is \n";
printInorder(root);
return 0;
}
// This code is contributed by rathbhupendra
C
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* function to create a new node of tree and returns pointer */
struct node* newNode(int data);
/* Function to convert a tree to double tree */
void doubleTree(struct node* node)
{
struct node* oldLeft;
if (node==NULL) return;
/* do the subtrees */
doubleTree(node->left);
doubleTree(node->right);
/* duplicate this node to its left */
oldLeft = node->left;
node->left = newNode(node->data);
node->left->left = oldLeft;
}
/* UTILITY FUNCTIONS TO TEST doubleTree() FUNCTION */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
/* Driver program to test above functions*/
int main()
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Inorder traversal of the original tree is \n");
printInorder(root);
doubleTree(root);
printf("\n Inorder traversal of the double tree is \n");
printInorder(root);
getchar();
return 0;
}
Java
// Java program to convert binary tree to double tree
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree
{
Node root;
/* Function to convert a tree to double tree */
void doubleTree(Node node)
{
Node oldleft;
if (node == null)
return;
/* do the subtrees */
doubleTree(node.left);
doubleTree(node.right);
/* duplicate this node to its left */
oldleft = node.left;
node.left = new Node(node.data);
node.left.left = oldleft;
}
/* Given a binary tree, print its nodes in inorder*/
void printInorder(Node node)
{
if (node == null)
return;
printInorder(node.left);
System.out.print(node.data + " ");
printInorder(node.right);
}
/* Driver program to test the above functions */
public static void main(String args[])
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("Original tree is : ");
tree.printInorder(tree.root);
tree.doubleTree(tree.root);
System.out.println("");
System.out.println("Inorder traversal of double tree is : ");
tree.printInorder(tree.root);
}
}
// This code has been contributed by Mayank Jaiswal(mayank_24)
Python3
# Python3 program to convert
# binary tree to double tree
# A binary tree node has data,
# pointer to left child and a
# pointer to right child
class Node:
def __init__(self, d):
self.data = d
self.left = None
self.right = None
# Function to convert a tree to var tree
def doubleTree(node) :
if node == None :
return
# do the subtrees
doubleTree(node.left)
doubleTree(node.right)
# duplicate this node to its left
oldleft = node.left
node.left = Node(node.data)
node.left.left = oldleft
# Given a binary tree, print its nodes in inorder
def printInorder(node) :
if node == None :
return
printInorder(node.left)
print(node.data,end=' ')
printInorder(node.right)
# Driver Code
if __name__ == '__main__':
'''
Driver program to test the above functions */
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
'''
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Original tree is : ")
printInorder(root)
doubleTree(root)
print()
print("Inorder traversal of double tree is : ")
printInorder(root)
# This code is contributed by jana_sayantan.
C#
// C# program to convert binary tree
// to double tree
/* A binary tree node has data,
pointer to left child and
a pointer to right child */
using System;
class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class BinaryTree
{
Node root;
/* Function to convert a tree to double tree */
void doubleTree(Node node)
{
Node oldleft;
if (node == null)
return;
/* do the subtrees */
doubleTree(node.left);
doubleTree(node.right);
/* duplicate this node to its left */
oldleft = node.left;
node.left = new Node(node.data);
node.left.left = oldleft;
}
/* Given a binary tree, print its nodes in inorder*/
void printInorder(Node node)
{
if (node == null)
return;
printInorder(node.left);
Console.Write(node.data + " ");
printInorder(node.right);
}
// Driver Code
public static void Main(String []args)
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
Console.WriteLine("Original tree is : ");
tree.printInorder(tree.root);
tree.doubleTree(tree.root);
Console.WriteLine("");
Console.WriteLine("Inorder traversal of " +
"double tree is : ");
tree.printInorder(tree.root);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to convert binary tree to var tree
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class Node {
constructor(val) {
this.data = val;
this.left = null;
this.right = null;
}
}
var root;
/* Function to convert a tree to var tree */
function doubleTree(node)
{
var oldleft;
if (node == null)
return;
/* do the subtrees */
doubleTree(node.left);
doubleTree(node.right);
/* duplicate this node to its left */
oldleft = node.left;
node.left = new Node(node.data);
node.left.left = oldleft;
}
/* Given a binary tree, print its nodes in inorder*/
function printInorder(node)
{
if (node == null)
return;
printInorder(node.left);
document.write(node.data + " ");
printInorder(node.right);
}
/* Driver program to test the above functions */
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
document.write("Original tree is :<br/> ");
printInorder(root);
doubleTree(root);
document.write("<br/>");
document.write("Inorder traversal of double tree is : <br/>");
printInorder(root);
// This code is contributed by todaysgaurav
</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