Dado un árbol binario y una clave, escribe una función que imprima todos los ancestros de la clave en el árbol binario dado.
Por ejemplo, considere el siguiente árbol binario
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /
8 9 10
Las siguientes son diferentes teclas de entrada y sus ancestros en el árbol anterior
Input Key List of Ancestors ------------------------- 1 2 1 3 1 4 2 1 5 2 1 6 3 1 7 3 1 8 4 2 1 9 5 2 1 10 7 3 1
La solución recursiva para este problema se discute aquí .
Está claro que necesitamos usar un recorrido iterativo basado en la pila del árbol binario. La idea es tener todos los ancestros en la pila cuando lleguemos al Node con la clave dada. Una vez que alcancemos la clave, todo lo que tenemos que hacer es imprimir el contenido de la pila.
¿Cómo apilar todos los ancestros cuando llegamos al Node dado? Podemos atravesar todos los Nodes en modo Postorder. Si echamos un vistazo más de cerca al recorrido recursivo posterior al orden, podemos observar fácilmente que, cuando se llama a la función recursiva para un Node, la pila de llamadas recursivas contiene ancestros del Node. Entonces, la idea es hacer un recorrido iterativo posterior al orden y detener el recorrido cuando alcancemos el Node deseado.
A continuación se muestra la implementación del enfoque anterior.
Implementación:
C
// C program to print all ancestors of a given key
#include <stdio.h>
#include <stdlib.h>
// Maximum stack size
#define MAX_SIZE 100
// Structure for a tree node
struct Node
{
int data;
struct Node *left, *right;
};
// Structure for Stack
struct Stack
{
int size;
int top;
struct Node* *array;
};
// A utility function to create a new tree node
struct Node* newNode(int data)
{
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
// A utility function to create a stack of given size
struct Stack* createStack(int size)
{
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack->size = size;
stack->top = -1;
stack->array = (struct Node**) malloc(stack->size * sizeof(struct Node*));
return stack;
}
// BASIC OPERATIONS OF STACK
int isFull(struct Stack* stack)
{
return ((stack->top + 1) == stack->size);
}
int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}
void push(struct Stack* stack, struct Node* node)
{
if (isFull(stack))
return;
stack->array[++stack->top] = node;
}
struct Node* pop(struct Stack* stack)
{
if (isEmpty(stack))
return NULL;
return stack->array[stack->top--];
}
struct Node* peek(struct Stack* stack)
{
if (isEmpty(stack))
return NULL;
return stack->array[stack->top];
}
// Iterative Function to print all ancestors of a given key
void printAncestors(struct Node *root, int key)
{
if (root == NULL) return;
// Create a stack to hold ancestors
struct Stack* stack = createStack(MAX_SIZE);
// Traverse the complete tree in postorder way till we find the key
while (1)
{
// Traverse the left side. While traversing, push the nodes into
// the stack so that their right subtrees can be traversed later
while (root && root->data != key)
{
push(stack, root); // push current node
root = root->left; // move to next node
}
// If the node whose ancestors are to be printed is found,
// then break the while loop.
if (root && root->data == key)
break;
// Check if right sub-tree exists for the node at top
// If not then pop that node because we don't need this
// node any more.
if (peek(stack)->right == NULL)
{
root = pop(stack);
// If the popped node is right child of top, then remove the top
// as well. Left child of the top must have processed before.
// Consider the following tree for example and key = 3. If we
// remove the following loop, the program will go in an
// infinite loop after reaching 5.
// 1
// / \
// 2 3
// \
// 4
// \
// 5
while (!isEmpty(stack) && peek(stack)->right == root)
root = pop(stack);
}
// if stack is not empty then simply set the root as right child
// of top and start traversing right sub-tree.
root = isEmpty(stack)? NULL: peek(stack)->right;
}
// If stack is not empty, print contents of stack
// Here assumption is that the key is there in tree
while (!isEmpty(stack))
printf("%d ", pop(stack)->data);
}
// Driver program to test above functions
int main()
{
// Let us construct a binary tree
struct 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->right->right = newNode(9);
root->right->right->left = newNode(10);
printf("Following are all keys and their ancestors\n");
for (int key = 1; key <= 10; key++)
{
printf("%d: ", key);
printAncestors(root, key);
printf("\n");
}
getchar();
return 0;
}
C++
// C++ program to print all ancestors of a given key
#include <bits/stdc++.h>
using namespace std;
// Structure for a tree node
struct Node
{
int data;
struct Node *left, *right;
};
// A utility function to create a new tree node
struct Node* newNode(int data)
{
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
// Iterative Function to print all ancestors of a given key
void printAncestors(struct Node *root, int key)
{
if (root == NULL) return;
// Create a stack to hold ancestors
stack<struct Node* > st;
// Traverse the complete tree in postorder way till we find the key
while (1)
{
// Traverse the left side. While traversing, push the nodes into
// the stack so that their right subtrees can be traversed later
while (root && root->data != key)
{
st.push(root); // push current node
root = root->left; // move to next node
}
// If the node whose ancestors are to be printed is found,
// then break the while loop.
if (root && root->data == key)
break;
// Check if right sub-tree exists for the node at top
// If not then pop that node because we don't need this
// node any more.
if (st.top()->right == NULL)
{
root = st.top();
st.pop();
// If the popped node is right child of top, then remove the top
// as well. Left child of the top must have processed before.
while (!st.empty() && st.top()->right == root)
{root = st.top();
st.pop();
}
}
// if stack is not empty then simply set the root as right child
// of top and start traversing right sub-tree.
root = st.empty()? NULL: st.top()->right;
}
// If stack is not empty, print contents of stack
// Here assumption is that the key is there in tree
while (!st.empty())
{
cout<<st.top()->data<<" ";
st.pop();
}
}
// Driver program to test above functions
int main()
{
// Let us construct a binary tree
struct 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->right->right = newNode(9);
root->right->right->left = newNode(10);
cout<<"Following are all keys and their ancestors"<<endl;
for (int key = 1; key <= 10; key++)
{
cout<<key<<":"<<" ";
printAncestors(root, key);
cout<<endl;
}
return 0;
}
// This code is contributed by Gautam Singh
Java
// Java program to print all ancestors of a given key
import java.util.Stack;
public class GFG
{
// Class for a tree node
static class Node
{
int data;
Node left,right;
// constructor to create Node
// left and right are by default null
Node(int data)
{
this.data = data;
}
}
// Iterative Function to print all ancestors of a given key
static void printAncestors(Node root,int key)
{
if(root == null)
return;
// Create a stack to hold ancestors
Stack<Node> st = new Stack<>();
// Traverse the complete tree in postorder way till we find the key
while(true)
{
// Traverse the left side. While traversing, push the nodes into
// the stack so that their right subtrees can be traversed later
while(root != null && root.data != key)
{
st.push(root); // push current node
root = root.left; // move to next node
}
// If the node whose ancestors are to be printed is found,
// then break the while loop.
if(root != null && root.data == key)
break;
// Check if right sub-tree exists for the node at top
// If not then pop that node because we don't need this
// node any more.
if(st.peek().right == null)
{
root =st.peek();
st.pop();
// If the popped node is right child of top, then remove the top
// as well. Left child of the top must have processed before.
while( st.empty() == false && st.peek().right == root)
{
root = st.peek();
st.pop();
}
}
// if stack is not empty then simply set the root as right child
// of top and start traversing right sub-tree.
root = st.empty() ? null : st.peek().right;
}
// If stack is not empty, print contents of stack
// Here assumption is that the key is there in tree
while( !st.empty() )
{
System.out.print(st.peek().data+" ");
st.pop();
}
}
// Driver program to test above functions
public static void main(String[] args)
{
// Let us construct a binary tree
Node 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.right.right = new Node(9);
root.right.right.left = new Node(10);
System.out.println("Following are all keys and their ancestors");
for(int key = 1;key <= 10;key++)
{
System.out.print(key+": ");
printAncestors(root, key);
System.out.println();
}
}
}
//This code is Contributed by Sumit Ghosh
Python3
# Python3 program to print all ancestors of a given key
# Class for a tree node
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Iterative Function to print all ancestors of a given key
def printAncestors(root, key):
if(root == None):
return;
# Create a stack to hold ancestors
st = []
# Traverse the complete tree in postorder way till we find the key
while(True):
# Traverse the left side. While traversing, append the nodes into
# the stack so that their right subtrees can be traversed later
while(root != None and root.data != key):
st.append(root); # append current node
root = root.left; # move to next node
# If the node whose ancestors are to be printed is found,
# then break the while loop.
if(root != None and root.data == key):
break;
# Check if right sub-tree exists for the node at top
# If not then pop that node because we don't need this
# node any more.
if(st[-1].right == None):
root = st[-1];
st.pop();
# If the popped node is right child of top, then remove the top
# as well. Left child of the top must have processed before.
while(len(st) != 0 and st[-1].right == root):
root = st[-1];
st.pop();
# if stack is not empty then simply set the root as right child
# of top and start traversing right sub-tree.
root = None if len(st) == 0 else st[-1].right;
# If stack is not empty, print contents of stack
# Here assumption is that the key is there in tree
while(len(st) != 0):
print(st[-1].data, end = " ")
st.pop();
# Driver program to test above functions
if __name__=='__main__':
# Let us construct a binary tree
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.right.right = Node(9);
root.right.right.left = Node(10);
print("Following are all keys and their ancestors");
for key in range(1, 11):
print(key, end = ": ");
printAncestors(root, key);
print();
# This code is contributed by rutvik_56.
C#
// C# program to print all ancestors
// of a given key
using System;
using System.Collections.Generic;
class GFG
{
// Class for a tree node
public class Node
{
public int data;
public Node left, right;
// constructor to create Node
// left and right are by default null
public Node(int data)
{
this.data = data;
}
}
// Iterative Function to print
// all ancestors of a given key
public static void printAncestors(Node root,
int key)
{
if (root == null)
{
return;
}
// Create a stack to hold ancestors
Stack<Node> st = new Stack<Node>();
// Traverse the complete tree in
// postorder way till we find the key
while (true)
{
// Traverse the left side. While
// traversing, push the nodes into
// the stack so that their right
// subtrees can be traversed later
while (root != null && root.data != key)
{
st.Push(root); // push current node
root = root.left; // move to next node
}
// If the node whose ancestors
// are to be printed is found,
// then break the while loop.
if (root != null && root.data == key)
{
break;
}
// Check if right sub-tree exists for
// the node at top. If not then pop
// that node because we don't need
// this node any more.
if (st.Peek().right == null)
{
root = st.Peek();
st.Pop();
// If the popped node is right child
// of top, then remove the top as well.
// Left child of the top must have
// processed before.
while (st.Count > 0 &&
st.Peek().right == root)
{
root = st.Peek();
st.Pop();
}
}
// if stack is not empty then simply
// set the root as right child of top
// and start traversing right sub-tree.
root = st.Count == 0 ?
null : st.Peek().right;
}
// If stack is not empty, print contents
// of stack. Here assumption is that the
// key is there in tree
while (st.Count > 0)
{
Console.Write(st.Peek().data + " ");
st.Pop();
}
}
// Driver Code
public static void Main(string[] args)
{
// Let us construct a binary tree
Node 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.right.right = new Node(9);
root.right.right.left = new Node(10);
Console.WriteLine("Following are all keys " +
"and their ancestors");
for (int key = 1; key <= 10; key++)
{
Console.Write(key + ": ");
printAncestors(root, key);
Console.WriteLine();
}
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to print all ancestors of a given key
// Class for a tree node
class Node
{
// constructor to create Node
// left and right are by default null
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Iterative Function to print
// all ancestors of a given key
function printAncestors(root, key)
{
if (root == null)
{
return;
}
// Create a stack to hold ancestors
let st = [];
// Traverse the complete tree in
// postorder way till we find the key
while (true)
{
// Traverse the left side. While
// traversing, push the nodes into
// the stack so that their right
// subtrees can be traversed later
while (root != null && root.data != key)
{
st.push(root); // push current node
root = root.left; // move to next node
}
// If the node whose ancestors
// are to be printed is found,
// then break the while loop.
if (root != null && root.data == key)
{
break;
}
// Check if right sub-tree exists for
// the node at top. If not then pop
// that node because we don't need
// this node any more.
if (st[st.length - 1].right == null)
{
root = st[st.length - 1];
st.pop();
// If the popped node is right child
// of top, then remove the top as well.
// Left child of the top must have
// processed before.
while (st.length > 0 &&
st[st.length - 1].right == root)
{
root = st[st.length - 1];
st.pop();
}
}
// if stack is not empty then simply
// set the root as right child of top
// and start traversing right sub-tree.
root = st.length == 0 ?
null : st[st.length - 1].right;
}
// If stack is not empty, print contents
// of stack. Here assumption is that the
// key is there in tree
while (st.length > 0)
{
document.write(st[st.length - 1].data + " ");
st.pop();
}
}
// Let us construct a binary tree
let 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.right.right = new Node(9);
root.right.right.left = new Node(10);
document.write("Following are all keys " +
"and their ancestors" + "</br>");
for (let key = 1; key <= 10; key++)
{
document.write(key + ": ");
printAncestors(root, key);
document.write("</br>");
}
// This code is contributed by decode2207.
</script>
Producción
Following are all keys and their ancestors 1: 2: 1 3: 1 4: 2 1 5: 2 1 6: 3 1 7: 3 1 8: 4 2 1 9: 5 2 1 10: 7 3 1
Ejercicio
Tenga en cuenta que la solución anterior asume que la clave dada está presente en el árbol binario dado. Puede entrar en bucle infinito si la clave no está presente. Extienda la solución anterior para que funcione incluso cuando la clave no está presente en el árbol.
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