Creación de un árbol con Representación de hijo izquierdo-hermano derecho

La representación del hijo izquierdo y el hermano derecho es una representación diferente de un árbol n-ario en el que, en lugar de contener una referencia a todos y cada uno de los Nodes secundarios, un Node contiene solo dos referencias, primero una referencia a su primer hijo y la otra a su hermano inmediato siguiente. Esta nueva transformación no solo elimina la necesidad de un conocimiento avanzado de la cantidad de elementos secundarios que tiene un Node, sino que también limita la cantidad de referencias a un máximo de dos, lo que facilita mucho la codificación. 

At each node, link children of same parent from left to right.
Parent should be linked with only first child.

Ejemplos: 

Left Child Right Sibling tree representation
      10
      |  
      2 -> 3 -> 4 -> 5
      |    |  
      6    7 -> 8 -> 9

Requisito previo: Representación del árbol del hijo izquierdo y hermano derecho 

A continuación se muestra la implementación. 

C++

// C++ program to create a tree with left child
// right sibling representation.
#include<bits/stdc++.h>
using namespace std;
 
struct Node
{
    int data;
    struct Node *next;
    struct Node *child;
};
 
// Creating new Node
Node* newNode(int data)
{
    Node *newNode = new Node;
    newNode->next = newNode->child = NULL;
    newNode->data = data;
    return newNode;
}
 
// Adds a sibling to a list with starting with n
Node *addSibling(Node *n, int data)
{
    if (n == NULL)
        return NULL;
 
    while (n->next)
        n = n->next;
 
    return (n->next = newNode(data));
}
 
// Add child Node to a Node
Node *addChild(Node * n, int data)
{
    if (n == NULL)
        return NULL;
 
    // Check if child list is not empty.
    if (n->child)
        return addSibling(n->child, data);
    else
        return (n->child = newNode(data));
}
 
// Traverses tree in depth first order
void traverseTree(Node * root)
{
    if (root == NULL)
        return;
 
    while (root)
    {
        cout << " " << root->data;
        if (root->child)
            traverseTree(root->child);
        root = root->next;
    }
}
 
//Driver code
 
int main()
{
    /*   Let us create below tree
    *           10
    *     /   /    \   \
    *    2  3      4   5
    *              |   /  | \
    *              6   7  8  9   */
 
    // Left child right sibling
    /*  10
    *    |
    *    2 -> 3 -> 4 -> 5
    *              |    |
    *              6    7 -> 8 -> 9  */
    Node *root = newNode(10);
    Node *n1  = addChild(root, 2);
    Node *n2  = addChild(root, 3);
    Node *n3  = addChild(root, 4);
    Node *n4  = addChild(n3, 6);
    Node *n5  = addChild(root, 5);
    Node *n6  = addChild(n5, 7);
    Node *n7  = addChild(n5, 8);
    Node *n8  = addChild(n5, 9);
    traverseTree(root);
    return 0;
}

Java

// Java program to create a tree with left child
// right sibling representation.
 
class GFG {
     
    static class NodeTemp
    {
        int data;
        NodeTemp next, child;
        public NodeTemp(int data)
        {
            this.data = data;
            next = child = null;
        }
    }
     
    // Adds a sibling to a list with starting with n
    static public NodeTemp addSibling(NodeTemp node, int data)
    {
        if(node == null)
            return null;
        while(node.next != null)
            node = node.next;
        return(node.next = new NodeTemp(data));
    }
         
    // Add child Node to a Node
    static public NodeTemp addChild(NodeTemp node,int data)
    {
        if(node == null)
            return null;
     
        // Check if child is not empty.
        if(node.child != null)
            return(addSibling(node.child,data));
        else
            return(node.child = new NodeTemp(data));
    }
 
    // Traverses tree in depth first order
    static public void traverseTree(NodeTemp root)
    {
        if(root == null)
            return;
        while(root != null)
        {
            System.out.print(root.data + " ");
            if(root.child != null)
                traverseTree(root.child);
            root = root.next;
        }
    }
 
    // Driver code
    public static void main(String args[])
    {
         
        /*   Let us create below tree
        *           10
        *     /   /    \   \
        *    2  3      4   5
        *              |   /  | \
        *              6   7  8  9   */
      
        // Left child right sibling
        /*  10
        *    |
        *    2 -> 3 -> 4 -> 5
        *              |    |
        *              6    7 -> 8 -> 9  */
 
        NodeTemp root = new NodeTemp(10);
        NodeTemp n1 = addChild(root,2);
        NodeTemp n2 = addChild(root,3);
        NodeTemp n3 = addChild(root,4);
        NodeTemp n4 = addChild(n3,6);
        NodeTemp n5 = addChild(root,5);
        NodeTemp n6 = addChild(n5,7);
        NodeTemp n7 = addChild(n5,8);
        NodeTemp n8 = addChild(n5,9);
         
        traverseTree(root);
    }
}
 
// This code is contributed by M.V.S.Surya Teja.

Python3

# Python3 program to create a tree with
# left child right sibling representation.
 
# Creating new Node
class newNode:
    def __init__(self, data):
        self.Next = self.child = None
        self.data = data
 
# Adds a sibling to a list with
# starting with n
def addSibling(n, data):
    if (n == None):
        return None
 
    while (n.Next):
        n = n.Next
    n.Next = newNode(data)
    return n.Next
 
# Add child Node to a Node
def addChild(n, data):
    if (n == None):
        return None
 
    # Check if child list is not empty.
    if (n.child):
        return addSibling(n.child, data)
    else:
        n.child = newNode(data)
        return n.child
 
# Traverses tree in depth first order
def traverseTree(root):
    if (root == None):
        return
 
    while (root):
        print(root.data, end = " ")
        if (root.child):
            traverseTree(root.child)
        root = root.Next
 
# Driver code
if __name__ == '__main__':
     
    # Let us create below tree
    #         10
    #     / / \ \
    # 2 3     4 5
    #             | / | \
    #             6 7 8 9
 
    # Left child right sibling
    # 10
    # |
    # 2 -> 3 -> 4 -> 5
    #             | |
    #             6 7 -> 8 -> 9
    root = newNode(10)
    n1 = addChild(root, 2)
    n2 = addChild(root, 3)
    n3 = addChild(root, 4)
    n4 = addChild(n3, 6)
    n5 = addChild(root, 5)
    n6 = addChild(n5, 7)
    n7 = addChild(n5, 8)
    n8 = addChild(n5, 9)
    traverseTree(root)
     
# This code is contributed by pranchalK

C#

// C# program to create a tree with left
// child right sibling representation.
using System;
 
class GFG
{
public class NodeTemp
{
    public int data;
    public NodeTemp next, child;
    public NodeTemp(int data)
    {
        this.data = data;
        next = child = null;
    }
}
 
// Adds a sibling to a list with
// starting with n
public static NodeTemp addSibling(NodeTemp node,
                                  int data)
{
    if (node == null)
    {
        return null;
    }
    while (node.next != null)
    {
        node = node.next;
    }
    return (node.next = new NodeTemp(data));
}
 
// Add child Node to a Node
public static NodeTemp addChild(NodeTemp node,
                                int data)
{
    if (node == null)
    {
        return null;
    }
 
    // Check if child is not empty.
    if (node.child != null)
    {
        return (addSibling(node.child,data));
    }
    else
    {
        return (node.child = new NodeTemp(data));
    }
}
 
// Traverses tree in depth first order
public static void traverseTree(NodeTemp root)
{
    if (root == null)
    {
        return;
    }
    while (root != null)
    {
        Console.Write(root.data + " ");
        if (root.child != null)
        {
            traverseTree(root.child);
        }
        root = root.next;
    }
}
 
// Driver code
public static void Main(string[] args)
{
 
    /* Let us create below tree
    *         10
    *     / / \ \
    * 2 3     4 5
    *             | / | \
    *             6 7 8 9 */
 
    // Left child right sibling
    /* 10
    * |
    * 2 -> 3 -> 4 -> 5
    *             | |
    *             6 7 -> 8 -> 9 */
 
    NodeTemp root = new NodeTemp(10);
    NodeTemp n1 = addChild(root, 2);
    NodeTemp n2 = addChild(root, 3);
    NodeTemp n3 = addChild(root, 4);
    NodeTemp n4 = addChild(n3, 6);
    NodeTemp n5 = addChild(root, 5);
    NodeTemp n6 = addChild(n5, 7);
    NodeTemp n7 = addChild(n5, 8);
    NodeTemp n8 = addChild(n5, 9);
 
    traverseTree(root);
}
}
 
// This code is contributed by Shrikant13

Javascript

<script>
 
// Javascript program to create a tree with left child
// right sibling representation.
     
    class NodeTemp
    {
        constructor(data)
        {
            this.data=data;
            this.next = this.child = null;
        }
    }
     
    // Adds a sibling to a list with starting with n
    function addSibling(node,data)
    {
        if(node == null)
            return null;
        while(node.next != null)
            node = node.next;
        return(node.next = new NodeTemp(data));
    }
     
    // Add child Node to a Node
    function addChild(node,data)
    {
        if(node == null)
            return null;
      
        // Check if child is not empty.
        if(node.child != null)
            return(addSibling(node.child,data));
        else
            return(node.child = new NodeTemp(data));
             
    }
     
    // Traverses tree in depth first order
    function traverseTree(root)
    {
        if(root == null)
            return;
        while(root != null)
        {
            document.write(root.data + " ");
            if(root.child != null)
                traverseTree(root.child);
            root = root.next;
        }
    }
     
    // Driver code
     
    /*   Let us create below tree
        *           10
        *     /   /    \   \
        *    2  3      4   5
        *              |   /  | \
        *              6   7  8  9   */
       
        // Left child right sibling
        /*  10
        *    |
        *    2 -> 3 -> 4 -> 5
        *              |    |
        *              6    7 -> 8 -> 9  */
  
        let root = new NodeTemp(10);
        let n1 = addChild(root,2);
        let n2 = addChild(root,3);
        let n3 = addChild(root,4);
        let n4 = addChild(n3,6);
        let n5 = addChild(root,5);
        let n6 = addChild(n5,7);
        let n7 = addChild(n5,8);
        let n8 = addChild(n5,9);
          
        traverseTree(root);
 
 
 
// This code is contributed by patel2127
 
</script>
Producción: 

10 2 3 4 6 5 7 8 9

 

Recorrido de orden de nivel: el código anterior habla sobre el recorrido de profundidad primero. También podemos hacer un recorrido por orden de nivel de dicha representación.

Implementación:

C++

// C++ program to create a tree with left child
// right sibling representation.
#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    int data;
    struct Node* next;
    struct Node* child;
};
 
// Creating new Node
Node* newNode(int data)
{
    Node* newNode = new Node;
    newNode->next = newNode->child = NULL;
    newNode->data = data;
    return newNode;
}
 
// Adds a sibling to a list with starting with n
Node* addSibling(Node* n, int data)
{
    if (n == NULL)
        return NULL;
 
    while (n->next)
        n = n->next;
 
    return (n->next = newNode(data));
}
 
// Add child Node to a Node
Node* addChild(Node* n, int data)
{
    if (n == NULL)
        return NULL;
 
    // Check if child list is not empty.
    if (n->child)
        return addSibling(n->child, data);
    else
        return (n->child = newNode(data));
}
 
// Traverses tree in level order
void traverseTree(Node* root)
{
    // Corner cases
    if (root == NULL)
        return;
 
    cout << root->data << " ";
 
    if (root->child == NULL)
        return;
 
    // Create a queue and enqueue root
    queue<Node*> q;
    Node* curr = root->child;
    q.push(curr);
 
    while (!q.empty()) {
 
        // Take out an item from the queue
        curr = q.front();
        q.pop();
 
        // Print next level of taken out item and enqueue
        // next level's children
        while (curr != NULL) {
            cout << curr->data << " ";
            if (curr->child != NULL) {
                q.push(curr->child);
            }
            curr = curr->next;
        }
    }
}
 
// Driver code
int main()
{
    Node* root = newNode(10);
    Node* n1 = addChild(root, 2);
    Node* n2 = addChild(root, 3);
    Node* n3 = addChild(root, 4);
    Node* n4 = addChild(n3, 6);
    Node* n5 = addChild(root, 5);
    Node* n6 = addChild(n5, 7);
    Node* n7 = addChild(n5, 8);
    Node* n8 = addChild(n5, 9);
    traverseTree(root);
    return 0;
}

Java

// Java program to create a tree with left child
// right sibling representation.
import java.util.*;
class GFG
{
  static class Node
  {
    int data;
    Node next;
    Node child;
  };
 
  // Creating new Node
  static Node newNode(int data)
  {
    Node newNode = new Node();
    newNode.next = newNode.child = null;
    newNode.data = data;
    return newNode;
  }
 
  // Adds a sibling to a list with starting with n
  static Node addSibling(Node n, int data)
  {
    if (n == null)
      return null;
    while (n.next != null)
      n = n.next;
    return (n.next = newNode(data));
  }
 
  // Add child Node to a Node
  static Node addChild(Node n, int data)
  {
    if (n == null)
      return null;
 
    // Check if child list is not empty.
    if (n.child != null)
      return addSibling(n.child, data);
    else
      return (n.child = newNode(data));
  }
 
  // Traverses tree in level order
  static void traverseTree(Node root)
  {
    // Corner cases
    if (root == null)
      return;
    System.out.print(root.data+ " ");
    if (root.child == null)
      return;
 
    // Create a queue and enqueue root
    Queue<Node> q = new LinkedList<>();
    Node curr = root.child;
    q.add(curr);
 
    while (!q.isEmpty())
    {
 
      // Take out an item from the queue
      curr = q.peek();
      q.remove();
 
      // Print next level of taken out item and enqueue
      // next level's children
      while (curr != null)
      {
        System.out.print(curr.data + " ");
        if (curr.child != null)
        {
          q.add(curr.child);
        }
        curr = curr.next;
      }
    }
  }
 
  // Driver code
  public static void main(String[] args)
  {
    Node root = newNode(10);
    Node n1 = addChild(root, 2);
    Node n2 = addChild(root, 3);
    Node n3 = addChild(root, 4);
    Node n4 = addChild(n3, 6);
    Node n5 = addChild(root, 5);
    Node n6 = addChild(n5, 7);
    Node n7 = addChild(n5, 8);
    Node n8 = addChild(n5, 9);
    traverseTree(root);
  }
}
 
// This code is contributed by aashish1995

Python3

# Python3 program to create a tree with
# left child right sibling representation
from collections import deque
 
class Node:
     
    def __init__(self, x):
         
        self.data = x
        self.next = None
        self.child = None
 
# Adds a sibling to a list with
# starting with n
def addSibling(n, data):
     
    if (n == None):
        return None
 
    while (n.next):
        n = n.next
 
    n.next = Node(data)
    return n
 
# Add child Node to a Node
def addChild(n, data):
     
    if (n == None):
        return None
         
    # Check if child list is not empty
    if (n.child):
        return addSibling(n.child, data)
    else:
        n.child = Node(data)
        return n
 
# Traverses tree in level order
def traverseTree(root):
     
    # Corner cases
    if (root == None):
        return
 
    print(root.data, end = " ")
 
    if (root.child == None):
        return
 
    # Create a queue and enqueue root
    q = deque()
    curr = root.child
    q.append(curr)
 
    while (len(q) > 0):
         
        # Take out an item from the queue
        curr = q.popleft()
        #q.pop()
 
        # Print next level of taken out
        # item and enqueue next level's children
        while (curr != None):
            print(curr.data, end = " ")
             
            if (curr.child != None):
                q.append(curr.child)
                 
            curr = curr.next
 
# Driver code
if __name__ == '__main__':
 
    root = Node(10)
    n1 = addChild(root, 2)
    n2 = addChild(root, 3)
    n3 = addChild(root, 4)
    n4 = addChild(n3, 6)
    n5 = addChild(root, 5)
    n6 = addChild(n5, 7)
    n7 = addChild(n5, 8)
    n8 = addChild(n5, 9)
     
    traverseTree(root)
 
# This code is contributed by mohit kumar 29

C#

// C# program to create a tree with left child
// right sibling representation.
using System;
using System.Collections.Generic;
class GFG
{
  public
    class Node
    {
      public
        int data;
      public
        Node next;
      public
        Node child;
    };
 
  // Creating new Node
  static Node newNode(int data)
  {
    Node newNode = new Node();
    newNode.next = newNode.child = null;
    newNode.data = data;
    return newNode;
  }
 
  // Adds a sibling to a list with starting with n
  static Node addSibling(Node n, int data)
  {
    if (n == null)
      return null;
    while (n.next != null)
      n = n.next;
    return (n.next = newNode(data));
  }
 
  // Add child Node to a Node
  static Node addChild(Node n, int data)
  {
    if (n == null)
      return null;
 
    // Check if child list is not empty.
    if (n.child != null)
      return addSibling(n.child, data);
    else
      return (n.child = newNode(data));
  }
 
  // Traverses tree in level order
  static void traverseTree(Node root)
  {
 
    // Corner cases
    if (root == null)
      return;
    Console.Write(root.data + " ");
    if (root.child == null)
      return;
 
    // Create a queue and enqueue root
    Queue<Node> q = new Queue<Node>();
    Node curr = root.child;
    q.Enqueue(curr);
    while (q.Count != 0)
    {
 
      // Take out an item from the queue
      curr = q.Peek();
      q.Dequeue();
 
      // Print next level of taken out item and enqueue
      // next level's children
      while (curr != null)
      {
        Console.Write(curr.data + " ");
        if (curr.child != null)
        {
          q.Enqueue(curr.child);
        }
        curr = curr.next;
      }
    }
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    Node root = newNode(10);
    Node n1 = addChild(root, 2);
    Node n2 = addChild(root, 3);
    Node n3 = addChild(root, 4);
    Node n4 = addChild(n3, 6);
    Node n5 = addChild(root, 5);
    Node n6 = addChild(n5, 7);
    Node n7 = addChild(n5, 8);
    Node n8 = addChild(n5, 9);
    traverseTree(root);
  }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program to create a
// tree with left child
// right sibling representation.
     
    class Node
    {
    // Creating new Node
        constructor(data)
        {
            this.data=data;
            this.next = this.child = null;
        }
    }
 
// Adds a sibling to a list with starting with n
function addSibling(n,data)
{
    if (n == null)
      return null;
    while (n.next != null)
      n = n.next;
    return (n.next = new Node(data));
}
 
// Add child Node to a Node
function addChild(n,data)
{
    if (n == null)
      return null;
  
    // Check if child list is not empty.
    if (n.child != null)
      return addSibling(n.child, data);
    else
      return (n.child = new Node(data));
}
 
// Traverses tree in level order
function traverseTree(root)
{
    // Corner cases
    if (root == null)
      return;
    document.write(root.data+ " ");
    if (root.child == null)
      return;
  
    // Create a queue and enqueue root
    let q = [];
    let curr = root.child;
    q.push(curr);
  
    while (q.length!=0)
    {
  
      // Take out an item from the queue
      curr = q[0];
      q.shift();
  
      // Print next level of taken out item and enqueue
      // next level's children
      while (curr != null)
      {
        document.write(curr.data + " ");
        if (curr.child != null)
        {
          q.push(curr.child);
        }
        curr = curr.next;
      }
    }
}
 
// Driver code
let root = new Node(10);
let n1 = addChild(root, 2);
let n2 = addChild(root, 3);
let n3 = addChild(root, 4);
let n4 = addChild(n3, 6);
let n5 = addChild(root, 5);
let n6 = addChild(n5, 7);
let n7 = addChild(n5, 8);
let n8 = addChild(n5, 9);
traverseTree(root);
 
 
// This code is contributed by unknown2108
 
</script>
Producción: 

10 2 3 4 5 6 7 8 9

 

Este artículo es una contribución de SAKSHI TIWARI . Si te gusta GeeksforGeeks (¡sabemos que te gusta!) y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *