Recorrido de la frontera del árbol binario

Dado un árbol binario, imprima los Nodes límite del árbol binario en el sentido contrario a las agujas del reloj comenzando desde la raíz. El límite incluye el límite izquierdo, las hojas y el límite derecho en orden sin Nodes duplicados. (Los valores de los Nodes aún pueden estar duplicados).
El límite izquierdo se define como la ruta desde la raíz hasta el Node más a la izquierda . El límite derecho se define como el camino desde la raíz hasta el Node más a la derecha . Si la raíz no tiene un subárbol izquierdo o un subárbol derecho, entonces la raíz en sí es un límite izquierdo o un límite derecho. Tenga en cuenta que esta definición solo se aplica al árbol binario de entrada y no se aplica a ningún subárbol.
El Node más a la izquierda se define como una hoja .Node al que podría llegar cuando siempre viaja primero al subárbol izquierdo si existe. Si no, viaja al subárbol derecho. Repita hasta llegar a un Node hoja.
El Node más a la derecha también se define de la misma manera con el intercambio de izquierda y derecha. 
Por ejemplo, el cruce de límites del siguiente árbol es «20 8 4 10 14 25 22»
 

Dividimos el problema en 3 partes: 

1. Imprima el límite izquierdo de arriba hacia abajo. 
2. Imprima todos los Nodes de hoja de izquierda a derecha, que nuevamente se pueden subdividir en dos subpartes: 
….. 2.1 Imprima todos los Nodes de hoja del subárbol izquierdo de izquierda a derecha. 
….. 2.2 Imprime todos los Nodes hoja del subárbol derecho de izquierda a derecha. 
3. Imprima el límite derecho de abajo hacia arriba.
Necesitamos encargarnos de una cosa: los Nodes no se vuelven a imprimir. por ejemplo, el Node más a la izquierda es también el Node hoja del árbol.
En base a los casos anteriores, a continuación se muestra la implementación:
 

Implementación:

#include <iostream>
using namespace std;
 
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node {
    int data;
    struct Node *left, *right;
};
 
// Utility function to create a new tree node
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = nullptr;
    return temp;
}
 
// A simple function to print leaf nodes of a binary tree
void printLeaves(Node* root)
{
    if (root == nullptr)
        return;
 
    printLeaves(root->left);
 
    // Print it if it is a leaf node
    if (!(root->left) && !(root->right))
        cout << root->data << " ";
 
    printLeaves(root->right);
}
 
// A function to print all left boundary nodes, except a
// leaf node. Print the nodes in TOP DOWN manner
void printBoundaryLeft(Node* root)
{
    if (root == nullptr)
        return;
 
    if (root->left) {
 
        // to ensure top down order, print the node
        // before calling itself for left subtree
        cout << root->data << " ";
        printBoundaryLeft(root->left);
    }
    else if (root->right) {
        cout << root->data << " ";
        printBoundaryLeft(root->right);
    }
    // do nothing if it is a leaf node, this way we avoid
    // duplicates in output
}
 
// A function to print all right boundary nodes, except a
// leaf node Print the nodes in BOTTOM UP manner
void printBoundaryRight(Node* root)
{
    if (root == nullptr)
        return;
 
    if (root->right) {
        // to ensure bottom up order, first call for right
        // subtree, then print this node
        printBoundaryRight(root->right);
        cout << root->data << " ";
    }
    else if (root->left) {
        printBoundaryRight(root->left);
        cout << root->data << " ";
    }
    // do nothing if it is a leaf node, this way we avoid
    // duplicates in output
}
 
// A function to do boundary traversal of a given binary
// tree
void printBoundary(Node* root)
{
    if (root == nullptr)
        return;
 
    cout << root->data << " ";
 
    // Print the left boundary in top-down manner.
    printBoundaryLeft(root->left);
 
    // Print all leaf nodes
    printLeaves(root->left);
    printLeaves(root->right);
 
    // Print the right boundary in bottom-up manner
    printBoundaryRight(root->right);
}
 
// Driver program to test above functions
int main()
{
    // Let us construct the tree given in the above diagram
    Node* root = newNode(20);
    root->left = newNode(8);
    root->left->left = newNode(4);
    root->left->right = newNode(12);
    root->left->right->left = newNode(10);
    root->left->right->right = newNode(14);
    root->right = newNode(22);
    root->right->right = newNode(25);
 
    printBoundary(root);
 
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

/* C program for boundary traversal
of a binary tree */
 
#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, *right;
};
 
// A simple function to print leaf nodes of a binary tree
void printLeaves(struct node* root)
{
    if (root == NULL)
        return;
 
    printLeaves(root->left);
 
    // Print it if it is a leaf node
    if (!(root->left) && !(root->right))
        printf("%d ", root->data);
 
    printLeaves(root->right);
}
 
// A function to print all left boundary nodes, except a leaf node.
// Print the nodes in TOP DOWN manner
void printBoundaryLeft(struct node* root)
{
    if (root == NULL)
        return;
 
    if (root->left) {
 
        // to ensure top down order, print the node
        // before calling itself for left subtree
        printf("%d ", root->data);
        printBoundaryLeft(root->left);
    }
    else if (root->right) {
        printf("%d ", root->data);
        printBoundaryLeft(root->right);
    }
    // do nothing if it is a leaf node, this way we avoid
    // duplicates in output
}
 
// A function to print all right boundary nodes, except a leaf node
// Print the nodes in BOTTOM UP manner
void printBoundaryRight(struct node* root)
{
    if (root == NULL)
        return;
 
    if (root->right) {
        // to ensure bottom up order, first call for right
        // subtree, then print this node
        printBoundaryRight(root->right);
        printf("%d ", root->data);
    }
    else if (root->left) {
        printBoundaryRight(root->left);
        printf("%d ", root->data);
    }
    // do nothing if it is a leaf node, this way we avoid
    // duplicates in output
}
 
// A function to do boundary traversal of a given binary tree
void printBoundary(struct node* root)
{
    if (root == NULL)
        return;
 
    printf("%d ", root->data);
 
    // Print the left boundary in top-down manner.
    printBoundaryLeft(root->left);
 
    // Print all leaf nodes
    printLeaves(root->left);
    printLeaves(root->right);
 
    // Print the right boundary in bottom-up manner
    printBoundaryRight(root->right);
}
 
// A utility function to create a node
struct node* newNode(int data)
{
    struct node* temp = (struct node*)malloc(sizeof(struct node));
 
    temp->data = data;
    temp->left = temp->right = NULL;
 
    return temp;
}
 
// Driver program to test above functions
int main()
{
    // Let us construct the tree given in the above diagram
    struct node* root = newNode(20);
    root->left = newNode(8);
    root->left->left = newNode(4);
    root->left->right = newNode(12);
    root->left->right->left = newNode(10);
    root->left->right->right = newNode(14);
    root->right = newNode(22);
    root->right->right = newNode(25);
 
    printBoundary(root);
    return 0;
}
// This code has been contributed by Aditya Kumar (adityakumar129)

// Java program to print boundary traversal of binary 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;
 
    // A simple function to print leaf nodes of a binary tree
    void printLeaves(Node node)
    {
        if (node == null)
            return;
 
        printLeaves(node.left);
        // Print it if it is a leaf node
        if (node.left == null && node.right == null)
            System.out.print(node.data + " ");
        printLeaves(node.right);
    }
 
    // A function to print all left boundary nodes, except a leaf node.
    // Print the nodes in TOP DOWN manner
    void printBoundaryLeft(Node node)
    {
        if (node == null)
            return;
 
        if (node.left != null) {
            // to ensure top down order, print the node
            // before calling itself for left subtree
            System.out.print(node.data + " ");
            printBoundaryLeft(node.left);
        }
        else if (node.right != null) {
            System.out.print(node.data + " ");
            printBoundaryLeft(node.right);
        }
 
        // do nothing if it is a leaf node, this way we avoid
        // duplicates in output
    }
 
    // A function to print all right boundary nodes, except a leaf node
    // Print the nodes in BOTTOM UP manner
    void printBoundaryRight(Node node)
    {
        if (node == null)
            return;
 
        if (node.right != null) {
            // to ensure bottom up order, first call for right
            // subtree, then print this node
            printBoundaryRight(node.right);
            System.out.print(node.data + " ");
        }
        else if (node.left != null) {
            printBoundaryRight(node.left);
            System.out.print(node.data + " ");
        }
        // do nothing if it is a leaf node, this way we avoid
        // duplicates in output
    }
 
    // A function to do boundary traversal of a given binary tree
    void printBoundary(Node node)
    {
        if (node == null)
            return;
 
        System.out.print(node.data + " ");
 
        // Print the left boundary in top-down manner.
        printBoundaryLeft(node.left);
 
        // Print all leaf nodes
        printLeaves(node.left);
        printLeaves(node.right);
 
        // Print the right boundary in bottom-up manner
        printBoundaryRight(node.right);
    }
 
    // Driver program to test above functions
    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(20);
        tree.root.left = new Node(8);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(12);
        tree.root.left.right.left = new Node(10);
        tree.root.left.right.right = new Node(14);
        tree.root.right = new Node(22);
        tree.root.right.right = new Node(25);
        tree.printBoundary(tree.root);
    }
}

# Python3 program for binary traversal of binary tree
 
# A binary tree node
class Node:
 
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# A simple function to print leaf nodes of a Binary Tree
def printLeaves(root):
    if(root):
        printLeaves(root.left)
         
        # Print it if it is a leaf node
        if root.left is None and root.right is None:
            print(root.data),
 
        printLeaves(root.right)
 
# A function to print all left boundary nodes, except a
# leaf node. Print the nodes in TOP DOWN manner
def printBoundaryLeft(root):
     
    if(root):
        if (root.left):
             
            # to ensure top down order, print the node
            # before calling itself for left subtree
            print(root.data)
            printBoundaryLeft(root.left)
         
        elif(root.right):
            print (root.data)
            printBoundaryLeft(root.right)
         
        # do nothing if it is a leaf node, this way we
        # avoid duplicates in output
 
 
# A function to print all right boundary nodes, except
# a leaf node. Print the nodes in BOTTOM UP manner
def printBoundaryRight(root):
     
    if(root):
        if (root.right):
            # to ensure bottom up order, first call for
            # right subtree, then print this node
            printBoundaryRight(root.right)
            print(root.data)
         
        elif(root.left):
            printBoundaryRight(root.left)
            print(root.data)
 
        # do nothing if it is a leaf node, this way we
        # avoid duplicates in output
 
 
# A function to do boundary traversal of a given binary tree
def printBoundary(root):
    if (root):
        print(root.data)
         
        # Print the left boundary in top-down manner
        printBoundaryLeft(root.left)
 
        # Print all leaf nodes
        printLeaves(root.left)
        printLeaves(root.right)
 
        # Print the right boundary in bottom-up manner
        printBoundaryRight(root.right)
 
 
# Driver program to test above function
root = Node(20)
root.left = Node(8)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
root.right = Node(22)
root.right.right = Node(25)
printBoundary(root)
 
# This code is contributed by
# Nikhil Kumar Singh(nickzuck_007)

// C# program to print boundary traversal
// of binary tree
using System;
 
/* 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;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class GFG {
    public Node root;
 
    // A simple function to print leaf
    // nodes of a binary tree
    public virtual void printLeaves(Node node)
    {
        if (node == null)
            return;
 
        printLeaves(node.left);
 
        // Print it if it is a leaf node
        if (node.left == null && node.right == null) {
            Console.Write(node.data + " ");
        }
        printLeaves(node.right);
    }
 
    // A function to print all left boundary
    // nodes, except a leaf node. Print the
    // nodes in TOP DOWN manner
    public virtual void printBoundaryLeft(Node node)
    {
        if (node == null)
            return;
 
        if (node.left != null) {
 
            // to ensure top down order, print the node
            // before calling itself for left subtree
            Console.Write(node.data + " ");
            printBoundaryLeft(node.left);
        }
        else if (node.right != null) {
            Console.Write(node.data + " ");
            printBoundaryLeft(node.right);
        }
 
        // do nothing if it is a leaf node,
        // this way we avoid duplicates in output
    }
 
    // A function to print all right boundary
    // nodes, except a leaf node. Print the
    // nodes in BOTTOM UP manner
    public virtual void printBoundaryRight(Node node)
    {
        if (node == null)
            return;
 
        if (node.right != null) {
            // to ensure bottom up order,
            // first call for right subtree,
            // then print this node
            printBoundaryRight(node.right);
            Console.Write(node.data + " ");
        }
        else if (node.left != null) {
            printBoundaryRight(node.left);
            Console.Write(node.data + " ");
        }
        // do nothing if it is a leaf node,
        // this way we avoid duplicates in output
    }
 
    // A function to do boundary traversal
    // of a given binary tree
    public virtual void printBoundary(Node node)
    {
        if (node == null)
            return;
 
        Console.Write(node.data + " ");
 
        // Print the left boundary in
        // top-down manner.
        printBoundaryLeft(node.left);
 
        // Print all leaf nodes
        printLeaves(node.left);
        printLeaves(node.right);
 
        // Print the right boundary in
        // bottom-up manner
        printBoundaryRight(node.right);
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        GFG tree = new GFG();
        tree.root = new Node(20);
        tree.root.left = new Node(8);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(12);
        tree.root.left.right.left = new Node(10);
        tree.root.left.right.right = new Node(14);
        tree.root.right = new Node(22);
        tree.root.right.right = new Node(25);
        tree.printBoundary(tree.root);
    }
}
 
// This code is contributed by Shrikant13

<script>
     
    // JavaScript program to print boundary
    // traversal of binary tree
     
    class Node
    {
        constructor(item) {
           this.left = null;
           this.right = null;
           this.data = item;
        }
    }
     
    let root;
   
    // A simple function to print leaf nodes of a binary tree
    function printLeaves(node)
    {
        if (node == null)
            return;
   
        printLeaves(node.left);
        // Print it if it is a leaf node
        if (node.left == null && node.right == null)
            document.write(node.data + " ");
        printLeaves(node.right);
    }
   
    // A function to print all left boundary nodes,
    // except a leaf node.
    // Print the nodes in TOP DOWN manner
    function printBoundaryLeft(node)
    {
        if (node == null)
            return;
   
        if (node.left != null) {
            // to ensure top down order, print the node
            // before calling itself for left subtree
            document.write(node.data + " ");
            printBoundaryLeft(node.left);
        }
        else if (node.right != null) {
            document.write(node.data + " ");
            printBoundaryLeft(node.right);
        }
   
        // do nothing if it is a leaf node, this way we avoid
        // duplicates in output
    }
   
    // A function to print all right boundary nodes,
    // except a leaf node
    // Print the nodes in BOTTOM UP manner
    function printBoundaryRight(node)
    {
        if (node == null)
            return;
   
        if (node.right != null) {
            // to ensure bottom up order, first call for right
            // subtree, then print this node
            printBoundaryRight(node.right);
            document.write(node.data + " ");
        }
        else if (node.left != null) {
            printBoundaryRight(node.left);
            document.write(node.data + " ");
        }
        // do nothing if it is a leaf node, this way we avoid
        // duplicates in output
    }
   
    // A function to do boundary traversal of a given binary tree
    function printBoundary(node)
    {
        if (node == null)
            return;
   
        document.write(node.data + " ");
   
        // Print the left boundary in top-down manner.
        printBoundaryLeft(node.left);
   
        // Print all leaf nodes
        printLeaves(node.left);
        printLeaves(node.right);
   
        // Print the right boundary in bottom-up manner
        printBoundaryRight(node.right);
    }
     
    root = new Node(20);
    root.left = new Node(8);
    root.left.left = new Node(4);
    root.left.right = new Node(12);
    root.left.right.left = new Node(10);
    root.left.right.right = new Node(14);
    root.right = new Node(22);
    root.right.right = new Node(25);
    printBoundary(root);
   
</script>

20 8 4 10 14 25 22 

Complejidad de tiempo: O(n) donde n es el número de Nodes en el árbol binario.
Espacio Auxiliar: O(n)

Limpie el código con la devolución del recorrido:

[Sin impresión directa + Versión iterativa del código]

Algoritmo:

1. Límite derecho: vaya a la derecha a la derecha hasta que no haya derecha. No incluya Nodes hoja. (ya que conduce a la duplicación)
2. Límite izquierdo: vaya a la izquierda a la izquierda hasta que no haya izquierda. No incluya Nodes hoja. (ya que conduce a la duplicación)
3. Límite de hoja: hágalo en orden, si el Node de hoja se agrega a la Lista.
4. Pasamos la array como referencia, por lo que es la misma ubicación de memoria utilizada por todas las funciones, para coordinar el resultado en un lugar.

CÓDIGO:

#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;
    struct Node *left, *right;
};
  
// Utility function to create a new tree node
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = nullptr;
    return temp;
}
 
bool isLeaf(Node* node){
  if(node->left == NULL && node->right==NULL){
    return true;
  }
  return false;
}
 
void addLeftBound(Node * root, vector<int>& ans){
  //Go left left and no left then right but again check from left
  root = root->left;
  while(root!=NULL){
    if(!isLeaf(root)) ans.push_back(root->data);
    if(root->left !=NULL) root = root->left;
    else root = root->right;
  }
}
 
void addRightBound(Node * root, vector<int>& ans){
  //Go right right and no right then left but again check from right
  root = root->right;
  //As we need the reverse of this for Anticlockwise
  stack<int> stk;
  while(root!=NULL){
    if(!isLeaf(root)) stk.push(root->data);
    if(root->right !=NULL) root = root->right;
    else root = root->left;
  }
  while(!stk.empty()){
    ans.push_back(stk.top());
    stk.pop();
  }
}
 
//its kind of inorder
void addLeaves(Node * root, vector<int>& ans){
  if(root==NULL){
    return;
  }
  if(isLeaf(root)){
    ans.push_back(root->data); //just store leaf nodes
    return;
  }
  addLeaves(root->left,ans);
  addLeaves(root->right,ans);
}
 
vector <int> boundary(Node *root)
{
  //Your code here
  vector<int> ans;
  if(root==NULL) return ans;
  if(!isLeaf(root)) ans.push_back(root->data); // if leaf then its done by addLeaf
  addLeftBound(root,ans);
  addLeaves(root,ans);
  addRightBound(root,ans);
 
  return ans;
 
}
 
int main()
{
    // Let us construct the tree given in the above diagram
    Node* root = newNode(20);
    root->left = newNode(8);
    root->left->left = newNode(4);
    root->left->right = newNode(12);
    root->left->right->left = newNode(10);
    root->left->right->right = newNode(14);
    root->right = newNode(22);
    root->right->right = newNode(25);
  
    vector<int>ans = boundary(root);
      for(int v : ans){
        cout<<v<<" ";
    }
      cout<<"\n";
  
    return 0;
}
 
//Code done by Balakrishnan R (rbkraj000)

20 8 4 10 14 25 22 

Complejidad de tiempo: O(n) donde n es el número de Nodes en el árbol binario.
Espacio Auxiliar: O(n)