Programación de árbol binario establecimiento de pedidos anticipados recorrido en orden
Análisis teórico
Un punto importante en el conocimiento básico de la estructura de datos es si se puede basar en dos combinaciones diferentes de secuencias transversales (hay tres tipos: primer orden + orden medio , primer orden + último orden, inorden + postorden), determina de forma única un árbol binario. Luego, el árbol binario se reconstruye de acuerdo con las diferentes secuencias transversales del árbol binario (orden previo, orden medio, orden posterior). Obviamente, estas tres combinaciones no pueden determinar de forma única un árbol binario. Entre ellas, el orden previo y posterior no pueden determinar de forma única un árbol binario. La siguiente es la prueba y la conclusión sobre este tema.
① Dada la secuencia de preorden y la secuencia de orden de un nodo de árbol binario, el árbol binario se puede determinar de forma única.
Prueba: debido a que el primer elemento de la secuencia de preorden es el nodo raíz, este elemento divide la secuencia de orden del árbol binario en dos partes. El lado izquierdo (suponiendo que hay L elementos) representa el. subárbol izquierdo. Si no hay ningún elemento, significa que el subárbol izquierdo está vacío; el lado derecho (suponiendo que hay elementos R) es el subárbol derecho. De acuerdo con el orden del "subárbol raíz-izquierdo-subárbol derecho" en el recorrido de preorden, el subárbol izquierdo se construye a partir de la secuencia de nodos L comenzando desde el segundo elemento de la secuencia de preorden y la secuencia de nodos L a la izquierda de la raíz del secuencia en orden. Subárbol, el subárbol derecho se construye a partir de la última secuencia de elementos R de la secuencia de preorden y la secuencia de elementos R a la derecha de la raíz de la secuencia en orden.
② Un árbol binario puede determinarse de forma única mediante la secuencia en orden y la secuencia de preorden, pero un árbol binario no puede determinarse de forma única mediante la secuencia de preorden y la secuencia de posorden, porque los subárboles izquierdo y derecho no se pueden determinar.
Contraejemplo: un árbol binario con solo un subárbol izquierdo en cualquier nodo y un árbol binario con solo un subárbol derecho en cualquier nodo tienen la misma secuencia de preorden y la misma secuencia de postorden, pero son dos árboles binarios diferentes. .
La secuencia transversal de preorden de estos dos árboles binarios es 2-1-3, y la secuencia transversal de postorden es 3-1-2. Pero, obviamente, son árboles binarios diferentes, por lo que el árbol binario no se puede determinar de forma única en función de la secuencia de preorden y la secuencia de postorden.
③ Se ha demostrado que un árbol binario puede determinarse mediante la secuencia de preorden y la secuencia en orden de un árbol binario. Ahora demostremos que un árbol binario también puede determinarse de forma única. secuencia en orden y secuencia posterior al orden de un árbol binario.
Prueba:
Cuando n = 1, solo hay un nodo raíz, y este árbol binario puede determinarse mediante la secuencia en orden y la secuencia posterior al orden.
Supongamos que la conclusión se cumple cuando n = m-1, es decir, cuando el número de nodos es m-1, la secuencia en orden y la secuencia posterior al orden pueden determinar de forma única el árbol binario. Ahora se demuestra que la conclusión se cumple cuando n=m.
Supongamos que la secuencia de orden medio es S1, S2,…,Sm, y la secuencia de orden posterior es P1, P2,…,Pm. Dado que el último elemento Pm de la secuencia de postorden es la raíz, se puede encontrar un nodo igual a Pm en la secuencia de orden (suponiendo que cada nodo en el árbol binario es diferente entre sí) Si (1≤i≤m), porque la secuencia en orden se obtiene del recorrido en orden, por lo que Si es el nodo raíz, S1, S2,..., Si-1 son las secuencias en orden del subárbol izquierdo y Si+1, Si+2,. .., Sm son las secuencias en orden de la secuencia de secuencia del subárbol derecho.
Si i = 1, entonces S1 es la raíz. En este momento, el subárbol izquierdo del árbol binario está vacío y el número de nodos del subárbol derecho es m-1, entonces {S2, S3. ,…,Sm} y {P1, P2,…,Pm-1} pueden determinar de forma única el subárbol derecho, determinando así también el árbol binario.
Si i = m, entonces Sm es la raíz. En este momento, el subárbol derecho del árbol binario está vacío y el número de nodos del subárbol izquierdo es m-1, entonces {S1, S2,…,Sm-1} y {P1, P2,…,Pm-1} determinan de forma única el subárbol izquierdo, determinando así también el árbol binario.
Finalmente, cuando 1 3. Ideas de construcción 1) Construya un árbol binario basado en la secuencia transversal de preorden y la secuencia transversal de orden Suponga que lo conocido El árbol binario es el siguiente: ___7___ / \ 10 2 / \ / 4 3 8 \ / 1 11 Entonces los resultados de su recorrido en preorden y recorrido en orden son los siguientes: preorder = {7,10,4,3,1, 2,8,11} inorder = {4,10,3,1,7,11,8,2} Varios puntos a tener en cuenta: 1) El primer nodo atravesado en preorden es siempre el nodo raíz. Por ejemplo, en el árbol binario de la figura anterior, el nodo raíz es 7, que también es el primer valor en el recorrido de preorden. En el recorrido de preorden, el nodo principal siempre se recorre antes que el nodo secundario. 2) Se puede observar que en el recorrido en orden, 7 es el cuarto valor (contando desde 0). Dado que el orden transversal en orden es: subárbol izquierdo, nodo raíz, subárbol derecho. Por lo tanto, los cuatro nodos {4,10,3,1} a la izquierda de 7 pertenecen al subárbol izquierdo, y los {11,8,2} a la derecha del nodo raíz 7 pertenecen al subárbol derecho. 3) La fórmula recursiva se puede obtener fácilmente a partir de la conclusión anterior. Después de construir el nodo raíz 7, podemos construir su subárbol izquierdo y su subárbol derecho de acuerdo con el recorrido en orden {4, 10, 3, 1} y {11,8,2} respectivamente. También necesitamos los resultados transversales de pedido previo correspondientes para descubrir patrones. Podemos saber por el recorrido de preorden que el recorrido de preorden de los subárboles izquierdo y derecho es {10, 4, 3, 1} y {2, 8, 11} respectivamente. Los subárboles izquierdo y derecho también son árboles binarios respectivamente, por lo que el problema se puede resolver de forma recursiva. 4) La cuestión de cómo obtener la posición del nodo raíz en el recorrido en orden no se ha discutido en detalle. Si se utiliza un escaneo lineal para encontrar la posición, cada búsqueda tomará O(. N) tiempo. Si el árbol binario está equilibrado. Si es así, todo el algoritmo requiere tiempo O (NlgN). Si el árbol binario está desequilibrado, en el peor de los casos se necesita O(N^2) tiempo. Para mejorar la eficiencia, podemos considerar el uso de una tabla hash para almacenar y encontrar la posición del nodo raíz en el recorrido en orden. Cada búsqueda solo toma O (1) tiempo, por lo que construir todo el árbol solo toma O (N). ) tiempo. Por conveniencia aquí, solo usamos una matriz para marcar la ubicación. También sería muy conveniente usar una tabla hash. Cabe señalar que los valores de los nodos del árbol binario aquí no pueden tener el mismo valor. Código: // Entrada: el primer puntero y el último puntero de preorden y orden intermedia, // Llamada recursiva, determinada cada una time Nodo actual BinaryTreeNode* ConstructCore(int* startPerorder, int* endPreorder, int* startInorder, int* endInorder) { //Preorder One es el nodo raíz int rootValue = startPerorder[0]; BinaryTreeNode* root = new BinaryTreeNode root->m_nValue = rootValue p> root->m_pLeft = root->m_pRight = NULL //Condición de salida recursiva if ( startPerorder==endPreorder ) { if ( startInorder==endInorder && *startPerorder==*endInorder ) return root else throw std: :exception("Entrada no válida."); // Manejo de excepciones } //Encontrar el valor del nodo raíz en el recorrido en orden int* rootInorder = startInorder; while(rootInorder<=endInorder && *rootInorder!=rootValue) ++rootInorder //Excepción; manejo if ( rootInorder==endInorder && *rootInorder!=rootValue) throw std::exception("Entrada no válida."); = rootInorder - startInorder; int* leftPreorderEnd = startPerorder+leftLength if ( leftLength > 0 ) { // Construir subárbol izquierdo root->m_pLeft=ConstructCore(startPerorder+1,leftPreorderEnd,startInorder, rootInorder-1 } if ( leftLength < endPreorder); -startPerorder ) { //Construye el subárbol correcto root->m_pR derecho= ConstructCore(leftPreorderEnd+1,endPreorder,rootInorder+1,endInorder } return root } //Construye un árbol binario basado en preorder e inorder BinaryTreeNode* Construct(int* preorder, int* inorder, int length) { if( preorder ==NULL || inorder==NULL || longitud <=0) return NULL return ConstructCore(preorder, preorder+longitud-1, inorder,inorder+longitud - 1); } void TraverseTreePostorder(BinaryTreeNode* proot) { if ( proot == NULL ) return; if ( proot->m_pLeft != NULL ) TraverseTreePostorder(proot->m_pLeft if ( proot-); > m_pRight != NULL ) TraverseTreePostorder(proot->m_pRight); cout << proot->m_nValue << " " } Código de prueba de la función principal: int main() { int preorder[] = {7,10,4,3, 1,2,8,11}; int inorder[] = {4,10,3,1,7,11,8,2}; BinaryTreeNode* pRoot = Construir (preorden, orden, 8); TraverseTreePostorder(pRoot); cout < devuelve 0; } 2) Construya un árbol binario basado en la secuencia transversal en orden y la secuencia transversal posterior al orden El principio es básicamente el mismo que el principio anterior, y el anterior todavía se puede utilizar el ejemplo ___7___ / \ 10 2 / \ / 4 3 8 \ / 1 11 Entonces los resultados de su recorrido en orden y postorden son los siguientes: inorder = { 4,10,3,1,7,11,8 ,2} postorder = {7,10,4,3,1,2,8,11} Código : //Entrada: Medio El primer puntero y el último puntero del pedido y post-orden Aguja, //Llamada recursiva, determina el nodo actual cada vez BinaryTreeNode* ConstructCore_in_post(int* startInorder, int* endInorder, int* startPostorder, int* endPostorder) { //El último nodo del postorder es el nodo raíz int rootValue = *endPostorder BinaryTreeNode* root = new BinaryTreeNode; root->m_nValue = rootValue; root->m_pLeft = root->m_pRight = NULL //Condición de salida recursiva if ( startInorder==endInorder ) { if ( startPostorder==endPostorder && *startInorder==*endPostorder ) return root else throw std::exception("Entrada no válida."); //Manejo de excepciones } //En Buscar el nodo raíz actual en la secuencia int* rootInorder = startInorder while(rootInorder<=endInorder && *rootInorder != rootValue ) ++rootInorder; int leftLength = rootInorder - startInorder; int* leftInorderEnd = startInorder+leftLength-1 if ( leftLength > 0 ) { //Construye el subárbol izquierdo root->m_pLeft=ConstructCore_in_post(startInorder,leftInorderEnd,startPostorder, startPostorder+leftLength-1 ); } if ( leftLength < endInorder-startInorder ) { //Construye el subárbol derecho root->m_pRight= ConstructCore_in_post ( rootInorder+1,endInorder,startPostorder+leftLength,endPostorder-1 } devuelve raíz } /); / Según el orden de precedencia y medio Construya un árbol binario en orden BinaryTreeNode* Construct(int* inorder, int* postorder, int length) { if(inorder==NULL | | postorder=NULL || longitud <=0) return NULL return ConstructCore_in_post(inorder, inorder+length-1, postorder+length-1); /p> } void TraverseTreePreorder(BinaryTreeNode* proot) { if ( proot == NULL ) return; cout << proot->m_nValue << " " if ( proot->m_pLeft != NULL ) TraverseTreePreorder(proot-> m_pLeft); if ( proot->m_pRight != NULL ) TraverseTreePreorder(proot->m_pRight } Prueba de función principal: int main() { int inorder[] = {4,10,3,1,7,11,8, 2}; int postorder[] = {4,1,3,10,11,8,2,7}; BinaryTreeNode* pRoot = Construir(inorder,postorder, 8); TraverseTreePreorder(pRoot); cout < devuelve 0;