Recorrido diagonal iterativo del árbol binario

Considere líneas de pendiente -1 que pasan entre Nodes. Dado un árbol binario, imprima todos los elementos diagonales en un árbol binario que pertenezca a la misma línea.

Input : Root of below tree

C++

/* C++ program to construct string from binary tree*/
#include <bits/stdc++.h>
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, *right;
};
  
/* Helper function that allocates a new node */
Node* newNode(int data)
{
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
  
// Iterative function to print diagonal view
void diagonalPrint(Node* root)
{
    // base case
    if (root == NULL)
        return;
  
    // inbuilt queue of Treenode
    queue<Node*> q;
  
    // push root
    q.push(root);
  
    // push delimiter
    q.push(NULL);
  
    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
  
        // if current is delimiter then insert another
        // for next diagonal and cout nextline
        if (temp == NULL) {
  
            // if queue is empty return
            if (q.empty())
                return;
  
            // output nextline
            cout << endl;
  
            // push delimiter again
            q.push(NULL);
        }
        else {
            while (temp) {
                cout << temp->data << " ";
  
                // if left child is present 
                // push into queue
                if (temp->left)
                    q.push(temp->left);
  
                // current equals to right child
                temp = temp->right;
            }
        }
    }
}
  
// Driver Code
int main()
{
    Node* root = newNode(8);
    root->left = newNode(3);
    root->right = newNode(10);
    root->left->left = newNode(1);
    root->left->right = newNode(6);
    root->right->right = newNode(14);
    root->right->right->left = newNode(13);
    root->left->right->left = newNode(4);
    root->left->right->right = newNode(7);
    diagonalPrint(root);
}

Java

// Java program to con string from binary tree
import java.util.*;
class solution
{
  
    
// A binary tree node has data, pointer to left 
 //  child and a pointer to right child 
static class Node { 
    int data; 
    Node left, right; 
}; 
    
// Helper function that allocates a new node 
static Node newNode(int data) 
{ 
    Node node = new Node(); 
    node.data = data; 
    node.left = node.right = null; 
    return (node); 
} 
    
// Iterative function to print diagonal view 
static void diagonalPrint(Node root) 
{ 
    // base case 
    if (root == null) 
        return; 
    
    // inbuilt queue of Treenode 
    Queue<Node> q= new LinkedList<Node>(); 
    
    // add root 
    q.add(root); 
    
    // add delimiter 
    q.add(null); 
    
    while (q.size()>0) { 
        Node temp = q.peek(); 
        q.remove(); 
    
        // if current is delimiter then insert another 
        // for next diagonal and cout nextline 
        if (temp == null) { 
    
            // if queue is empty return 
            if (q.size()==0) 
                return; 
    
            // output nextline 
            System.out.println();
    
            // add delimiter again 
            q.add(null); 
        } 
        else { 
            while (temp!=null) { 
                System.out.print( temp.data + " "); 
    
                // if left child is present  
                // add into queue 
                if (temp.left!=null) 
                    q.add(temp.left); 
    
                // current equals to right child 
                temp = temp.right; 
            } 
        } 
    } 
} 
    
// Driver Code 
public static void main(String args[])
{ 
    Node root = newNode(8); 
    root.left = newNode(3); 
    root.right = newNode(10); 
    root.left.left = newNode(1); 
    root.left.right = newNode(6); 
    root.right.right = newNode(14); 
    root.right.right.left = newNode(13); 
    root.left.right.left = newNode(4); 
    root.left.right.right = newNode(7); 
    diagonalPrint(root); 
} 
}
//contributed by Arnab Kundu

Python3

# Python3 program to construct string from binary tree
class Node:
    def __init__(self,data):
        self.val = data
        self.left = None
        self.right = None
          
# Function to print diagonal view
def diagonalprint(root):
      
    # base case
    if root is None:
        return
          
    # queue of treenode
    q = []
      
    # Append root
    q.append(root)
      
    # Append delimiter
    q.append(None)
  
    while len(q) > 0:
        temp = q.pop(0)
          
        # If current is delimiter then insert another 
        # for next diagonal and cout nextline
        if not temp:
              
            # If queue is empty then return 
            if len(q) == 0:
                return
                  
            # Print output on nextline
            print(' ')
              
            # append delimiter again 
            q.append(None)
  
        else:
            while temp:
                print(temp.val, end = ' ')
                  
                # If left child is present
                # append into queue
                if temp.left:
                    q.append(temp.left)
                      
                # current equals to right child
                temp = temp.right
  
# Driver Code
root = Node(8) 
root.left = Node(3) 
root.right = Node(10) 
root.left.left = Node(1) 
root.left.right = Node(6) 
root.right.right = Node(14) 
root.right.right.left = Node(13) 
root.left.right.left = Node(4) 
root.left.right.right = Node(7) 
diagonalprint(root) 
  
# This code is contributed by Praveen kumar

C#

// C# program to con string from binary tree
using System; 
using System.Collections;
  
class GFG
{
  
// A binary tree node has data, 
// pointer to left child and
// a pointer to right child 
public class Node
{ 
    public int data; 
    public Node left, right; 
}; 
      
// Helper function that
// allocates a new node 
static Node newNode(int data) 
{ 
    Node node = new Node(); 
    node.data = data; 
    node.left = node.right = null; 
    return (node); 
} 
      
// Iterative function to print diagonal view 
static void diagonalPrint(Node root) 
{ 
    // base case 
    if (root == null) 
        return; 
      
    // inbuilt queue of Treenode 
    Queue q = new Queue(); 
      
    // Enqueue root 
    q.Enqueue(root); 
      
    // Enqueue delimiter 
    q.Enqueue(null); 
      
    while (q.Count > 0) 
    { 
        Node temp = (Node) q.Peek(); 
        q.Dequeue(); 
      
        // if current is delimiter then insert another 
        // for next diagonal and cout nextline 
        if (temp == null) 
        { 
      
            // if queue is empty return 
            if (q.Count == 0) 
                return; 
      
            // output nextline 
            Console.WriteLine();
      
            // Enqueue delimiter again 
            q.Enqueue(null); 
        } 
        else 
        { 
            while (temp != null)
            { 
                Console.Write( temp.data + " "); 
      
                // if left child is present 
                // Enqueue into queue 
                if (temp.left != null) 
                    q.Enqueue(temp.left); 
      
                // current equals to right child 
                temp = temp.right; 
            } 
        } 
    } 
} 
      
// Driver Code 
public static void Main(String []args)
{ 
    Node root = newNode(8); 
    root.left = newNode(3); 
    root.right = newNode(10); 
    root.left.left = newNode(1); 
    root.left.right = newNode(6); 
    root.right.right = newNode(14); 
    root.right.right.left = newNode(13); 
    root.left.right.left = newNode(4); 
    root.left.right.right = newNode(7); 
    diagonalPrint(root); 
} 
}
  
// This code is contributed by Arnab Kundu

Javascript

<script>
  
    // JavaScript program to con string from binary tree
      
    class Node
    {
        constructor(data) {
           this.left = null;
           this.right = null;
           this.data = data;
        }
    }
  
    // Helper function that allocates a new node
    function newNode(data)
    {
        let node = new Node(data);
        return (node);
    }
  
    // Iterative function to print diagonal view
    function diagonalPrint(root)
    {
        // base case
        if (root == null)
            return;
  
        // inbuilt queue of Treenode
        let q= [];
  
        // add root
        q.push(root);
  
        // add delimiter
        q.push(null);
  
        while (q.length>0) {
            let temp = q[0];
            q.shift();
  
            // if current is delimiter then insert another
            // for next diagonal and cout nextline
            if (temp == null) {
  
                // if queue is empty return
                if (q.length==0)
                    return;
  
                // output nextline
                document.write("</br>");
  
                // add delimiter again
                q.push(null);
            }
            else {
                while (temp!=null) {
                    document.write( temp.data + " ");
  
                    // if left child is present 
                    // add into queue
                    if (temp.left!=null)
                        q.push(temp.left);
  
                    // current equals to right child
                    temp = temp.right;
                }
            }
        }
    }
      
    let root = newNode(8);
    root.left = newNode(3);
    root.right = newNode(10);
    root.left.left = newNode(1);
    root.left.right = newNode(6);
    root.right.right = newNode(14);
    root.right.right.left = newNode(13);
    root.left.right.left = newNode(4);
    root.left.right.right = newNode(7);
    diagonalPrint(root);
  
</script>

Java

import java.util.Queue;
import java.util.LinkedList;
  
//Node
class Node{
    int data;
    Node left;
    Node right;
      
    //Constructor for initializing the value of the node along with
    //left and right pointers
    Node(int data){
        this.data = data;
        left = right = null;
    }
}
  
public class DiagonalTraversal {
    //root node 
    Node root = null;
      
    //function to print in diagonal order
    void traverse() {
        //if the tree is empty, do not have to print
        //anything
        if(root == null)
            return;
          
        //if root is not empty, point curr node to the 
        //root node
        Node curr = root;
          
        //Maintain a queue to store left child
        Queue<Node> q = new LinkedList<>();
          
        //continue till the queue is empty and curr is null
        while(!q.isEmpty()  ||  curr!=null) {
            //if curr is null
            //1. print the data of the curr node
            //2. if left child is present, add it to the queue
            //3. Move curr pointer to the right 
            if(curr != null) {
                System.out.print(curr.data+" ");
                  
                if(curr.left != null)
                    q.add(curr.left);
                curr = curr.right;
            }
            //if curr is null, remove a node from the queue
            //and point it to curr node
            else {
                curr = q.remove();
            }
        }
    }
      
    //Driver function
    public static void main(String args[]) {
        DiagonalTraversal tree = new DiagonalTraversal();
/*                 8
               /  \
              3    10
             / \    \
            1   6     14
               / \    /
              4   7  13            */
          
        //construction of the tree
        tree.root = new Node(8); 
        tree.root.left = new Node(3); 
        tree.root.right = new Node(10); 
        tree.root.left.left = new Node(1); 
        tree.root.left.right = new Node(6); 
        tree.root.right.right = new Node(14); 
        tree.root.right.right.left = new Node(13); 
        tree.root.left.right.left = new Node(4); 
        tree.root.left.right.right = new Node(7);
          
        //function call
        tree.traverse();
    }
}
  
//This method is contributed by Likhita AVL

C#

using System;
using System.Collections.Generic;
  
// Node
public class Node
{
    public int data;
    public Node left;
    public Node right;
       
    // Constructor for initializing the value
    // of the node along with left and right pointers
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}
  
public class DiagonalTraversal{
  
// Root node
Node root = null;
   
// Function to print in diagonal order
void traverse() 
{
      
    // If the tree is empty, do not have to print
    // anything
    if (root == null)
        return;
       
    // If root is not empty, point curr node to the
    // root node
    Node curr = root;
       
    // Maintain a queue to store left child
    Queue<Node> q = new Queue<Node>();
       
    // Continue till the queue is empty 
    // and curr is null
    while (q.Count != 0 || curr != null)
    {
          
        // If curr is null
        // 1. print the data of the curr node
        // 2. if left child is present, add it to the queue
        // 3. Move curr pointer to the right
        if (curr != null) 
        {
            Console.Write(curr.data + " ");
               
            if (curr.left != null)
                q.Enqueue(curr.left);
                  
            curr = curr.right;
        }
          
        // If curr is null, remove a node from 
        // the queue and point it to curr node
        else
        {
            curr = q.Dequeue();
        }
    }
}
  
// Driver code
static public void Main()
{
      
    DiagonalTraversal tree = new DiagonalTraversal();
    /*       8
           /  \
          3    10
         / \    \
        1   6     14
           / \    /
          4   7  13            */
       
    // Construction of the tree
    tree.root = new Node(8);
    tree.root.left = new Node(3);
    tree.root.right = new Node(10);
    tree.root.left.left = new Node(1);
    tree.root.left.right = new Node(6);
    tree.root.right.right = new Node(14);
    tree.root.right.right.left = new Node(13);
    tree.root.left.right.left = new Node(4);
    tree.root.left.right.right = new Node(7);
       
    // Function call
    tree.traverse();
}
}
  
// This code is contributed by rag2127

Javascript

<script>
  
//Node
class Node
{
    // Constructor for initializing the value of the node along with
    // left and right pointers
    constructor(data)
    {
        this.data = data;
        this.left = this.right = null;
    }
}
  
// root node
let root = null;
  
// function to print in diagonal order
function traverse() 
{
    // if the tree is empty, do not have to print
        // anything
        if(root == null)
            return;
           
        // if root is not empty, point curr node to the
        // root node
        let curr = root;
           
        // Maintain a queue to store left child
        let q = [];
           
        // continue till the queue is empty and curr is null
        while(q.length!=0  ||  curr!=null) {
            // if curr is null
            // 1. print the data of the curr node
            // 2. if left child is present, add it to the queue
            // 3. Move curr pointer to the right
            if(curr != null) {
                document.write(curr.data+" ");
                   
                if(curr.left != null)
                    q.push(curr.left);
                curr = curr.right;
            }
            // if curr is null, remove a node from the queue
            // and point it to curr node
            else {
                curr = q.shift();
            }
       }
}
  
// Driver function
  
/*               8
               /  \
              3    10
             / \    \
            1   6     14
               / \    /
              4   7  13            */
  
//construction of the tree
root = new Node(8);
root.left = new Node(3);
root.right = new Node(10);
root.left.left = new Node(1);
root.left.right = new Node(6);
root.right.right = new Node(14);
root.right.right.left = new Node(13);
root.left.right.left = new Node(4);
root.left.right.right = new Node(7);
  
// function call
traverse();
  
  
// This code is contributed by avanitrachhadiya2155
  
</script>

Publicación traducida automáticamente

Artículo escrito por chhavi saini 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 *