Recorrido de orden de nivel específico de árbol binario perfecto

Posted on by Rudeus Greyrat

Dado un árbol binario perfecto como el siguiente: 

image(4)

C++

/* C++ program for special order traversal */
#include <iostream>
#include <queue>
using namespace std;
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct Node
{
    int data;
    Node *left;
    Node *right;
};
 
/* 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->right = node->left = NULL;
    return node;
}
 
/* Given a perfect binary tree, print its nodes in specific
   level order */
void printSpecificLevelOrder(Node *root)
{
    if (root == NULL)
        return;
 
    // Let us print root and next level first
    cout << root->data;
 
    // / Since it is perfect Binary Tree, right is not checked
    if (root->left != NULL)
      cout << " " << root->left->data << " " << root->right->data;
 
    // Do anything more if there are nodes at next level in
    // given perfect Binary Tree
    if (root->left->left == NULL)
        return;
 
    // Create a queue and enqueue left and right children of root
    queue <Node *> q;
    q.push(root->left);
    q.push(root->right);
 
    // We process two nodes at a time, so we need two variables
    // to store two front items of queue
    Node *first = NULL, *second = NULL;
 
    // traversal loop
    while (!q.empty())
    {
       // Pop two items from queue
       first = q.front();
       q.pop();
       second = q.front();
       q.pop();
 
       // Print children of first and second in reverse order
       cout << " " << first->left->data << " " << second->right->data;
       cout << " " << first->right->data << " " << second->left->data;
 
       // If first and second have grandchildren, enqueue them
       // in reverse order
       if (first->left->left != NULL)
       {
           q.push(first->left);
           q.push(second->right);
           q.push(first->right);
           q.push(second->left);
       }
    }
}
 
/* Driver program to test above functions*/
int main()
{
    //Perfect Binary Tree of Height 4
    Node *root = newNode(1);
 
    root->left        = newNode(2);
    root->right       = newNode(3);
 
    root->left->left  = newNode(4);
    root->left->right = newNode(5);
    root->right->left  = newNode(6);
    root->right->right = newNode(7);
 
    root->left->left->left  = newNode(8);
    root->left->left->right  = newNode(9);
    root->left->right->left  = newNode(10);
    root->left->right->right  = newNode(11);
    root->right->left->left  = newNode(12);
    root->right->left->right  = newNode(13);
    root->right->right->left  = newNode(14);
    root->right->right->right  = newNode(15);
 
    root->left->left->left->left  = newNode(16);
    root->left->left->left->right  = newNode(17);
    root->left->left->right->left  = newNode(18);
    root->left->left->right->right  = newNode(19);
    root->left->right->left->left  = newNode(20);
    root->left->right->left->right  = newNode(21);
    root->left->right->right->left  = newNode(22);
    root->left->right->right->right  = newNode(23);
    root->right->left->left->left  = newNode(24);
    root->right->left->left->right  = newNode(25);
    root->right->left->right->left  = newNode(26);
    root->right->left->right->right  = newNode(27);
    root->right->right->left->left  = newNode(28);
    root->right->right->left->right  = newNode(29);
    root->right->right->right->left  = newNode(30);
    root->right->right->right->right  = newNode(31);
 
    cout << "Specific Level Order traversal of binary tree is \n";
    printSpecificLevelOrder(root);
 
    return 0;
}

Java

// Java program for special level order traversal
  
import java.util.LinkedList;
import java.util.Queue;
  
/* Class containing left and right child of current
   node and key value*/
class Node
{
    int data;
    Node left, right;
  
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
  
class BinaryTree
{
    Node root;
  
    /* Given a perfect binary tree, print its nodes in specific
       level order */
    void printSpecificLevelOrder(Node node)
    {
        if (node == null)
            return;
  
        // Let us print root and next level first
        System.out.print(node.data);
  
        //  Since it is perfect Binary Tree, right is not checked
        if (node.left != null)
            System.out.print(" " + node.left.data + " " + node.right.data);
  
        // Do anything more if there are nodes at next level in
        // given perfect Binary Tree
        if (node.left.left == null)
            return;
  
        // Create a queue and enqueue left and right children of root
        Queue<Node> q = new LinkedList<Node>();
        q.add(node.left);
        q.add(node.right);
  
        // We process two nodes at a time, so we need two variables
        // to store two front items of queue
        Node first = null, second = null;
  
        // traversal loop
        while (!q.isEmpty())
        {
            // Pop two items from queue
            first = q.peek();
            q.remove();
            second = q.peek();
            q.remove();
  
            // Print children of first and second in reverse order
            System.out.print(" " + first.left.data + " " +second.right.data);
            System.out.print(" " + first.right.data + " " +second.left.data);
  
            // If first and second have grandchildren, enqueue them
            // in reverse order
            if (first.left.left != null)
            {
                q.add(first.left);
                q.add(second.right);
                q.add(first.right);
                q.add(second.left);
            }
        }
    }
  
    // Driver program to test for above functions
    public static void main(String args[])
    {
        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);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
  
        tree.root.left.left.left = new Node(8);
        tree.root.left.left.right = new Node(9);
        tree.root.left.right.left = new Node(10);
        tree.root.left.right.right = new Node(11);
        tree.root.right.left.left = new Node(12);
        tree.root.right.left.right = new Node(13);
        tree.root.right.right.left = new Node(14);
        tree.root.right.right.right = new Node(15);
  
        tree.root.left.left.left.left = new Node(16);
        tree.root.left.left.left.right = new Node(17);
        tree.root.left.left.right.left = new Node(18);
        tree.root.left.left.right.right = new Node(19);
        tree.root.left.right.left.left = new Node(20);
        tree.root.left.right.left.right = new Node(21);
        tree.root.left.right.right.left = new Node(22);
        tree.root.left.right.right.right = new Node(23);
        tree.root.right.left.left.left = new Node(24);
        tree.root.right.left.left.right = new Node(25);
        tree.root.right.left.right.left = new Node(26);
        tree.root.right.left.right.right = new Node(27);
        tree.root.right.right.left.left = new Node(28);
        tree.root.right.right.left.right = new Node(29);
        tree.root.right.right.right.left = new Node(30);
        tree.root.right.right.right.right = new Node(31);
  
        System.out.println("Specific Level Order traversal of binary"
                                                            +"tree is ");
        tree.printSpecificLevelOrder(tree.root);
    }
}
  
// This code has been contributed by Mayank Jaiswal

Python3

# Python program for special order traversal
 
# A binary tree node
class Node:
    # A constructor for making a new node
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None
 
# Given a perfect binary tree print its node in
# specific order
def printSpecificLevelOrder(root):
    if root is None:
        return
     
    # Let us print root and next level first
    print (root.data,end=" ")
     
    # Since it is perfect Binary tree,
    # one of the node is needed to be checked
    if root.left is not None :
        print (root.left.data,end=" ")
        print (root.right.data,end=" ")
     
    # Do anything more if there are nodes at next level
    # in given perfect Binary Tree
    if root.left.left is None:
        return
 
    # Create a queue and enqueue left and right
    # children of root
    q = []
    q.append(root.left)
    q.append(root.right)
     
    # We process two nodes at a time, so we need
    # two variables to store two front items of queue
    first = None
    second = None
    
    # Traversal loop
    while(len(q) > 0):
 
        # Pop two items from queue
        first = q.pop(0)
        second = q.pop(0)
 
        # Print children of first and second in reverse order
        print (first.left.data,end=" ")
        print (second.right.data,end=" ")
        print (first.right.data,end=" ")
        print (second.left.data,end=" ")
         
        # If first and second have grandchildren,
        # enqueue them in reverse order
        if first.left.left is not None:
            q.append(first.left)
            q.append(second.right)
            q.append(first.right)
            q.append(second.left)
 
# Driver program to test above function
 
# Perfect Binary Tree of Height 4
root = Node(1)
  
root.left= Node(2)
root.right   = Node(3)
  
root.left.left  = Node(4)
root.left.right = Node(5)
root.right.left  = Node(6)
root.right.right = Node(7)
  
root.left.left.left  = Node(8)
root.left.left.right  = Node(9)
root.left.right.left  = Node(10)
root.left.right.right  = Node(11)
root.right.left.left  = Node(12)
root.right.left.right  = Node(13)
root.right.right.left  = Node(14)
root.right.right.right  = Node(15)
  
root.left.left.left.left  = Node(16)
root.left.left.left.right  = Node(17)
root.left.left.right.left  = Node(18)
root.left.left.right.right  = Node(19)
root.left.right.left.left  = Node(20)
root.left.right.left.right  = Node(21)
root.left.right.right.left  = Node(22)
root.left.right.right.right  = Node(23)
root.right.left.left.left  = Node(24)
root.right.left.left.right  = Node(25)
root.right.left.right.left  = Node(26)
root.right.left.right.right  = Node(27)
root.right.right.left.left  = Node(28)
root.right.right.left.right  = Node(29)
root.right.right.right.left  = Node(30)
root.right.right.right.right  = Node(31)
  
print ("Specific Level Order traversal of binary tree is")
printSpecificLevelOrder(root);
  
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program for special level
// order traversal
using System;
using System.Collections.Generic;
 
/* Class containing left and right
child of current node and key value*/
public class Node
{
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class GFG
{
public Node root;
 
/* Given a perfect binary tree,
print its nodes in specific
level order */
public virtual void printSpecificLevelOrder(Node node)
{
    if (node == null)
    {
        return;
    }
 
    // Let us print root and next level first
    Console.Write(node.data);
 
    // Since it is perfect Binary Tree,
    // right is not checked
    if (node.left != null)
    {
        Console.Write(" " + node.left.data +
                      " " + node.right.data);
    }
 
    // Do anything more if there
    // are nodes at next level in
    // given perfect Binary Tree
    if (node.left.left == null)
    {
        return;
    }
 
    // Create a queue and enqueue left
    // and right children of root
    LinkedList<Node> q = new LinkedList<Node>();
    q.AddLast(node.left);
    q.AddLast(node.right);
 
    // We process two nodes at a time,
    // so we need two variables to
    // store two front items of queue
    Node first = null, second = null;
 
    // traversal loop
    while (q.Count > 0)
    {
        // Pop two items from queue
        first = q.First.Value;
        q.RemoveFirst();
        second = q.First.Value;
        q.RemoveFirst();
 
        // Print children of first and
        // second in reverse order
        Console.Write(" " + first.left.data +
                      " " + second.right.data);
        Console.Write(" " + first.right.data +
                      " " + second.left.data);
 
        // If first and second have grandchildren,
        // enqueue them in reverse order
        if (first.left.left != null)
        {
            q.AddLast(first.left);
            q.AddLast(second.right);
            q.AddLast(first.right);
            q.AddLast(second.left);
        }
    }
}
 
// Driver Code
public static void Main(string[] args)
{
    GFG tree = new GFG();
    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);
    tree.root.right.left = new Node(6);
    tree.root.right.right = new Node(7);
 
    tree.root.left.left.left = new Node(8);
    tree.root.left.left.right = new Node(9);
    tree.root.left.right.left = new Node(10);
    tree.root.left.right.right = new Node(11);
    tree.root.right.left.left = new Node(12);
    tree.root.right.left.right = new Node(13);
    tree.root.right.right.left = new Node(14);
    tree.root.right.right.right = new Node(15);
 
    tree.root.left.left.left.left = new Node(16);
    tree.root.left.left.left.right = new Node(17);
    tree.root.left.left.right.left = new Node(18);
    tree.root.left.left.right.right = new Node(19);
    tree.root.left.right.left.left = new Node(20);
    tree.root.left.right.left.right = new Node(21);
    tree.root.left.right.right.left = new Node(22);
    tree.root.left.right.right.right = new Node(23);
    tree.root.right.left.left.left = new Node(24);
    tree.root.right.left.left.right = new Node(25);
    tree.root.right.left.right.left = new Node(26);
    tree.root.right.left.right.right = new Node(27);
    tree.root.right.right.left.left = new Node(28);
    tree.root.right.right.left.right = new Node(29);
    tree.root.right.right.right.left = new Node(30);
    tree.root.right.right.right.right = new Node(31);
 
    Console.WriteLine("Specific Level Order " +
                      "traversal of binary" + "tree is ");
    tree.printSpecificLevelOrder(tree.root);
}
}
 
// This code is contributed by Shrikant13

Javascript

<script>
  
// JavaScript program for special level
// order traversal
 
/* Class containing left and right
child of current node and key value*/
class Node
{
  constructor(item)
  {
    this.data = item;
    this.left = null;
    this.right = null;
  }
}
 
 
var root = null;
 
/* Given a perfect binary tree,
print its nodes in specific
level order */
function printSpecificLevelOrder(node)
{
    if (node == null)
    {
        return;
    }
 
    // Let us print root and next level first
    document.write(node.data);
 
    // Since it is perfect Binary Tree,
    // right is not checked
    if (node.left != null)
    {
        document.write(" " + node.left.data +
                      " " + node.right.data);
    }
 
    // Do anything more if there
    // are nodes at next level in
    // given perfect Binary Tree
    if (node.left.left == null)
    {
        return;
    }
 
    // Create a queue and enqueue left
    // and right children of root
    var q = [];
    q.push(node.left);
    q.push(node.right);
 
    // We process two nodes at a time,
    // so we need two variables to
    // store two front items of queue
    var first = null, second = null;
 
    // traversal loop
    while (q.length > 0)
    {
        // Pop two items from queue
        first = q[0];
        q.shift();
        second = q[0];
        q.shift();
 
        // Print children of first and
        // second in reverse order
        document.write(" " + first.left.data +
                      " " + second.right.data);
        document.write(" " + first.right.data +
                      " " + second.left.data);
 
        // If first and second have grandchildren,
        // enqueue them in reverse order
        if (first.left.left != null)
        {
            q.push(first.left);
            q.push(second.right);
            q.push(first.right);
            q.push(second.left);
        }
    }
}
 
// Driver Code
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);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.left.right = new Node(9);
root.left.right.left = new Node(10);
root.left.right.right = new Node(11);
root.right.left.left = new Node(12);
root.right.left.right = new Node(13);
root.right.right.left = new Node(14);
root.right.right.right = new Node(15);
root.left.left.left.left = new Node(16);
root.left.left.left.right = new Node(17);
root.left.left.right.left = new Node(18);
root.left.left.right.right = new Node(19);
root.left.right.left.left = new Node(20);
root.left.right.left.right = new Node(21);
root.left.right.right.left = new Node(22);
root.left.right.right.right = new Node(23);
root.right.left.left.left = new Node(24);
root.right.left.left.right = new Node(25);
root.right.left.right.left = new Node(26);
root.right.left.right.right = new Node(27);
root.right.right.left.left = new Node(28);
root.right.right.left.right = new Node(29);
root.right.right.right.left = new Node(30);
root.right.right.right.right = new Node(31);
document.write("Specific Level Order " +
                  "traversal of binary" + "tree is <br>");
printSpecificLevelOrder(root);
 
</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

Deja una respuesta

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