El recorrido previo al pedido de un árbol de búsqueda binaria es 15, 10, 12, 11, 20, 18, 16, 19. ¿Cuál de los siguientes es el recorrido posterior al pedido del árbol?
(A) 10, 11, 12, 15, 16, 18, 19, 20
(B) 11, 12, 10, 16, 19, 18, 20, 15
(C) 20, 19, 18, 16, 15, 12 , 11, 10
(D) 19, 16, 18, 20, 11, 12, 10, 15
Respuesta: (B)
Explicación: consulte: encuentre el recorrido posterior al pedido de BST a partir del recorrido previo al pedido
// C++ program for finding postorder // traversal of BST from preorder traversal #include <bits/stdc++.h> using namespace std; // Function to find postorder traversal from // preorder traversal. void findPostOrderUtil(int pre[], int n, int minval, int maxval, int& preIndex) { // If entire preorder array is traversed then // return as no more element is left to be // added to post order array. if (preIndex == n) return; // If array element does not lie in range specified, // then it is not part of current subtree. if (pre[preIndex] < minval || pre[preIndex] > maxval) { return; } // Store current value, to be printed later, after // printing left and right subtrees. Increment // preIndex to find left and right subtrees, // and pass this updated value to recursive calls. int val = pre[preIndex]; preIndex++; // All elements with value between minval and val // lie in left subtree. findPostOrderUtil(pre, n, minval, val, preIndex); // All elements with value between val and maxval // lie in right subtree. findPostOrderUtil(pre, n, val, maxval, preIndex); cout << val << " "; } // Function to find postorder traversal. void findPostOrder(int pre[], int n) { // To store index of element to be // traversed next in preorder array. // This is passed by reference to // utility function. int preIndex = 0; findPostOrderUtil(pre, n, INT_MIN, INT_MAX, preIndex); } // Driver code int main() { int pre[] = { 15, 10, 12, 11, 20, 18, 16, 19 }; int n = sizeof(pre) / sizeof(pre[0]); // Calling function findPostOrder(pre, n); return 0; }
Código: https://ide.geeksforgeeks.org/t49kAtJwr7
La opción (B) es correcta.
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