Dado un árbol binario y un Node en el árbol binario, encuentre el sucesor de preorden del Node dado. Se puede suponer que cada Node tiene un enlace principal.
Ejemplos:
Consider the following binary tree 20 / \ 10 26 / \ / \ 4 18 24 27 / \ 14 19 / \ 13 15 Input : 4 Output : 18 Preorder traversal of given tree is 20, 10, 4, 18, 14, 13, 15, 19, 26, 24, 27. Input : 19 Output : 26
Una solución simple es almacenar primero el recorrido Preorder del árbol dado en una array, luego buscar linealmente el Node dado e imprimir el Node al lado.
Complejidad Temporal: O(n), ya que recorreremos el árbol para buscar el Node.
Espacio Auxiliar: O(n), ya que necesitamos espacio extra para almacenar los elementos del árbol.
Una solución eficiente se basa en las siguientes observaciones.
- Si el hijo izquierdo de un Node dado existe, entonces el hijo izquierdo es el sucesor de preorden.
- Sin embargo, si el hijo izquierdo no existe, el hijo derecho existe, entonces el sucesor del pedido previo es el hijo derecho.
- Si el hijo izquierdo y el hijo derecho no existen y el Node dado es el hijo izquierdo de su padre, entonces su hermano es su sucesor de preorden.
- Si no se cumple ninguna de las condiciones anteriores (el hijo izquierdo no existe y el Node dado no es hijo izquierdo de su padre), entonces avanzamos usando punteros de padres hasta que ocurra uno de los siguientes.
- Llegamos a la raíz. En este caso, no existe un sucesor de pedido anticipado.
- El Node actual (uno de los ancestros del Node dado) es el hijo izquierdo de su padre, en este caso, el sucesor de preorden es un hermano del Node actual.
C++
// CPP program to find preorder successor of // a node in Binary Tree. #include <iostream> using namespace std; struct Node { struct Node *left, *right, *parent; int key; }; Node* newNode(int key) { Node* temp = new Node; temp->left = temp->right = temp->parent = NULL; temp->key = key; return temp; } Node* preorderSuccessor(Node* root, Node* n) { // If left child exists, then it is preorder // successor. if (n->left) return n->left; // If left child does not exist and right child // exists, then it is preorder successor. if (n->right) return n->right; // If left child does not exist, then // travel up (using parent pointers) // until we reach a node which is left // child of its parent. Node *curr = n, *parent = curr->parent; while (parent != NULL && parent->right == curr) { curr = curr->parent; parent = parent->parent; } // If we reached root, then the given // node has no preorder successor if (parent == NULL) return NULL; return parent->right; } int main() { Node* root = newNode(20); root->parent = NULL; root->left = newNode(10); root->left->parent = root; root->left->left = newNode(4); root->left->left->parent = root->left; root->left->right = newNode(18); root->left->right->parent = root->left; root->right = newNode(26); root->right->parent = root; root->right->left = newNode(24); root->right->left->parent = root->right; root->right->right = newNode(27); root->right->right->parent = root->right; root->left->right->left = newNode(14); root->left->right->left->parent = root->left->right; root->left->right->left->left = newNode(13); root->left->right->left->left->parent = root->left->right->left; root->left->right->left->right = newNode(15); root->left->right->left->right->parent = root->left->right->left; root->left->right->right = newNode(19); root->left->right->right->parent = root->left->right; Node* res = preorderSuccessor(root, root->left->right->right); if (res) { printf("Preorder successor of %d is %d\n", root->left->right->right->key, res->key); } else { printf("Preorder successor of %d is NULL\n", root->left->right->right->key); } return 0; }
Java
// Java program to find preorder successor of // a node in Binary Tree. class Solution { static class Node { Node left, right, parent; int key; }; static Node newNode(int key) { Node temp = new Node(); temp.left = temp.right = temp.parent = null; temp.key = key; return temp; } static Node preorderSuccessor(Node root, Node n) { // If left child exists, then it is preorder // successor. if (n.left != null) return n.left; // If left child does not exist and right child // exists, then it is preorder successor. if (n.right != null) return n.right; // If left child does not exist, then // travel up (using parent pointers) // until we reach a node which is left // child of its parent. Node curr = n, parent = curr.parent; while (parent != null && parent.right == curr) { curr = curr.parent; parent = parent.parent; } // If we reached root, then the given // node has no preorder successor if (parent == null) return null; return parent.right; } // Driver code public static void main(String args[]) { Node root = newNode(20); root.parent = null; root.left = newNode(10); root.left.parent = root; root.left.left = newNode(4); root.left.left.parent = root.left; root.left.right = newNode(18); root.left.right.parent = root.left; root.right = newNode(26); root.right.parent = root; root.right.left = newNode(24); root.right.left.parent = root.right; root.right.right = newNode(27); root.right.right.parent = root.right; root.left.right.left = newNode(14); root.left.right.left.parent = root.left.right; root.left.right.left.left = newNode(13); root.left.right.left.left.parent = root.left.right.left; root.left.right.left.right = newNode(15); root.left.right.left.right.parent = root.left.right.left; root.left.right.right = newNode(19); root.left.right.right.parent = root.left.right; Node res = preorderSuccessor(root, root.left.right.right); if (res != null) { System.out.printf("Preorder successor of %d is %d\n", root.left.right.right.key, res.key); } else { System.out.printf("Preorder successor of %d is null\n", root.left.right.right.key); } } } // This code is contributed by Arnab Kundu
Python3
""" Python3 program to find preorder successor of a node in Binary Tree.""" # A Binary Tree Node # Utility function to create a new tree node class newNode: # Constructor to create a new node def __init__(self, data): self.key = data self.left = None self.right = None self.parent = None def preorderSuccessor(root, n): # If left child exists, then it is # preorder successor. if (n.left): return n.left # If left child does not exist and right child # exists, then it is preorder successor. if (n.right): return n.right # If left child does not exist, then # travel up (using parent pointers) # until we reach a node which is left # child of its parent. curr = n parent = curr.parent while (parent != None and parent.right == curr): curr = curr.parent parent = parent.parent # If we reached root, then the given # node has no preorder successor if (parent == None): return None return parent.right # Driver Code if __name__ == '__main__': root = newNode(20) root.parent = None root.left = newNode(10) root.left.parent = root root.left.left = newNode(4) root.left.left.parent = root.left root.left.right = newNode(18) root.left.right.parent = root.left root.right = newNode(26) root.right.parent = root root.right.left = newNode(24) root.right.left.parent = root.right root.right.right = newNode(27) root.right.right.parent = root.right root.left.right.left = newNode(14) root.left.right.left.parent = root.left.right root.left.right.left.left = newNode(13) root.left.right.left.left.parent = root.left.right.left root.left.right.left.right = newNode(15) root.left.right.left.right.parent = root.left.right.left root.left.right.right = newNode(19) root.left.right.right.parent = root.left.right res = preorderSuccessor(root, root.left.right.right) if (res): print("Preorder successor of", root.left.right.right.key, "is", res.key) else: print("Preorder successor of", root.left.right.right.key, "is None") # This code is contributed # by SHUBHAMSINGH10
C#
// C# program to find preorder successor of // a node in Binary Tree. using System; class GFG { public class Node { public Node left, right, parent; public int key; }; static Node newNode(int key) { Node temp = new Node(); temp.left = temp.right = temp.parent = null; temp.key = key; return temp; } static Node preorderSuccessor(Node root, Node n) { // If left child exists, then it is preorder // successor. if (n.left != null) return n.left; // If left child does not exist and right child // exists, then it is preorder successor. if (n.right != null) return n.right; // If left child does not exist, then // travel up (using parent pointers) // until we reach a node which is left // child of its parent. Node curr = n, parent = curr.parent; while (parent != null && parent.right == curr) { curr = curr.parent; parent = parent.parent; } // If we reached root, then the given // node has no preorder successor if (parent == null) return null; return parent.right; } // Driver code public static void Main(String []args) { Node root = newNode(20); root.parent = null; root.left = newNode(10); root.left.parent = root; root.left.left = newNode(4); root.left.left.parent = root.left; root.left.right = newNode(18); root.left.right.parent = root.left; root.right = newNode(26); root.right.parent = root; root.right.left = newNode(24); root.right.left.parent = root.right; root.right.right = newNode(27); root.right.right.parent = root.right; root.left.right.left = newNode(14); root.left.right.left.parent = root.left.right; root.left.right.left.left = newNode(13); root.left.right.left.left.parent = root.left.right.left; root.left.right.left.right = newNode(15); root.left.right.left.right.parent = root.left.right.left; root.left.right.right = newNode(19); root.left.right.right.parent = root.left.right; Node res = preorderSuccessor(root, root.left.right.right); if (res != null) { Console.Write("Preorder successor of {0} is {1}\n", root.left.right.right.key, res.key); } else { Console.Write("Preorder successor of {0} is null\n", root.left.right.right.key); } } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript program to find preorder successor of // a node in Binary Tree. class Node { constructor(key) { this.key=key; this.left=this.right=this.parent=null; } } function preorderSuccessor(root,n) { // If left child exists, then it is preorder // successor. if (n.left != null) return n.left; // If left child does not exist and right child // exists, then it is preorder successor. if (n.right != null) return n.right; // If left child does not exist, then // travel up (using parent pointers) // until we reach a node which is left // child of its parent. let curr = n, parent = curr.parent; while (parent != null && parent.right == curr) { curr = curr.parent; parent = parent.parent; } // If we reached root, then the given // node has no preorder successor if (parent == null) return null; return parent.right; } // Driver code let root = new Node(20); root.parent = null; root.left = new Node(10); root.left.parent = root; root.left.left = new Node(4); root.left.left.parent = root.left; root.left.right = new Node(18); root.left.right.parent = root.left; root.right = new Node(26); root.right.parent = root; root.right.left = new Node(24); root.right.left.parent = root.right; root.right.right = new Node(27); root.right.right.parent = root.right; root.left.right.left = new Node(14); root.left.right.left.parent = root.left.right; root.left.right.left.left = new Node(13); root.left.right.left.left.parent = root.left.right.left; root.left.right.left.right = new Node(15); root.left.right.left.right.parent = root.left.right.left; root.left.right.right = new Node(19); root.left.right.right.parent = root.left.right; let res = preorderSuccessor(root, root.left.right.right); if (res != null) { document.write("Preorder successor of "+ root.left.right.right.key+" is "+res.key+"<br>"); } else { System.out.printf("Preorder successor of "+ root.left.right.right.key+" is null<br>"); } // This code is contributed by avanitrachhadiya2155 </script>
Preorder successor of 19 is 26
Complejidad de tiempo: O(h) donde h es la altura del árbol binario dado, ya que no estamos atravesando todos los Nodes. Hemos comprobado el hijo de cada Node que es equivalente a atravesar la altura del árbol.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por NayanGadre y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA