Prerrequisitos : Morris Inorder Traversal , Tree Traversals (Inorder, Preorder y Postorder)
Dado un Binary Tree , la tarea es imprimir los elementos en orden posterior utilizando una complejidad de tiempo O(N) y un espacio constante.
Input: 1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
Output: 8 9 4 5 2 6 7 3 1
Input: 5
/ \
7 3
/ \ / \
4 11 13 9
/ \
8 4
Output: 8 4 4 11 7 13 9 3 5
Método 1: Uso de Morris Inorder Traversal
- Cree un Node ficticio y haga la raíz como su hijo izquierdo.
- Inicializar actual con Node ficticio.
- Mientras que la corriente no es NULL
- Si la corriente no tiene un hijo izquierdo, atraviesa el hijo derecho, actual = actual->derecho
- De lo contrario,
- Encuentre el hijo más a la derecha en el subárbol izquierdo.
- Si el hijo derecho del hijo más a la derecha es NULL
- Hacer actual como el hijo derecho del Node más a la derecha.
- Atraviesa el hijo izquierdo, actual = actual->izquierda
- De lo contrario,
- Establezca el puntero derecho del elemento secundario más a la derecha en NULL.
- Desde el hijo izquierdo de la corriente, recorra junto con los hijos derechos hasta el hijo más a la derecha e invierta los punteros.
- Retroceda desde el Node secundario más a la derecha hasta el Node secundario izquierdo actual invirtiendo los punteros e imprimiendo los elementos.
- Atraviesa el hijo derecho, actual = actual->derecho
A continuación se muestra el diagrama que muestra el hijo más a la derecha en el subárbol izquierdo, apuntando a su sucesor en orden.
A continuación se muestra el diagrama que destaca la ruta 1->2->5->9 y la forma en que se procesan e imprimen los Nodes según el algoritmo anterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// Post Order traversal
// of Binary Tree in O(N)
// time and O(1) space
#include <bits/stdc++.h>
using namespace std;
class node
{
public:
int data;
node *left, *right;
};
// Helper function that allocates a
// new node with the given data and
// NULL left and right pointers.
node* newNode(int data)
{
node* temp = new node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Postorder traversal without recursion
// and without stack
void postOrderConstSpace(node* root)
{
if (root == NULL)
return;
node* current = newNode(-1);
node* pre = NULL;
node* prev = NULL;
node* succ = NULL;
node* temp = NULL;
current->left = root;
while (current)
{
// If left child is null.
// Move to right child.
if (current->left == NULL)
{
current = current->right;
}
else
{
pre = current->left;
// Inorder predecessor
while (pre->right &&
pre->right != current)
pre = pre->right;
// The connection between current and
// predecessor is made
if (pre->right == NULL)
{
// Make current as the right
// child of the right most node
pre->right = current;
// Traverse the left child
current = current->left;
}
else
{
pre->right = NULL;
succ = current;
current = current->left;
prev = NULL;
// Traverse along the right
// subtree to the
// right-most child
while (current != NULL)
{
temp = current->right;
current->right = prev;
prev = current;
current = temp;
}
// Traverse back
// to current's left child
// node
while (prev != NULL)
{
cout << prev->data << " ";
temp = prev->right;
prev->right = current;
current = prev;
prev = temp;
}
current = succ;
current = current->right;
}
}
}
}
// Driver code
int main()
{
/* Constructed tree is as follows:-
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
*/
node* root = NULL;
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->right->left = newNode(8);
root->left->right->right = newNode(9);
postOrderConstSpace(root);
return 0;
}
// This code is contributed by Saurav Chaudhary
Java
// Java program to implement
// Post Order traversal
// of Binary Tree in O(N)
// time and O(1) space
// Definition of the
// binary tree
class TreeNode {
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
}
public String toString()
{
return data + " ";
}
}
public class PostOrder {
TreeNode root;
// Function to find Post Order
// Traversal Using Constant space
void postOrderConstantspace(TreeNode
root)
{
if (root == null)
return;
TreeNode current
= new TreeNode(-1),
pre = null;
TreeNode prev = null,
succ = null,
temp = null;
current.left = root;
while (current != null) {
// Go to the right child
// if current does not
// have a left child
if (current.left == null) {
current = current.right;
}
else {
// Traverse left child
pre = current.left;
// Find the right most child
// in the left subtree
while (pre.right != null
&& pre.right != current)
pre = pre.right;
if (pre.right == null) {
// Make current as the right
// child of the right most node
pre.right = current;
// Traverse the left child
current = current.left;
}
else {
pre.right = null;
succ = current;
current = current.left;
prev = null;
// Traverse along the right
// subtree to the
// right-most child
while (current != null) {
temp = current.right;
current.right = prev;
prev = current;
current = temp;
}
// Traverse back from
// right most child to
// current's left child node
while (prev != null) {
System.out.print(prev);
temp = prev.right;
prev.right = current;
current = prev;
prev = temp;
}
current = succ;
current = current.right;
}
}
}
}
// Driver Code
public static void main(String[] args)
{
/* Constructed tree is as follows:-
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
*/
PostOrder tree = new PostOrder();
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(4);
tree.root.left.right
= new TreeNode(5);
tree.root.right.left
= new TreeNode(6);
tree.root.right.right
= new TreeNode(7);
tree.root.left.right.left
= new TreeNode(8);
tree.root.left.right.right
= new TreeNode(9);
tree.postOrderConstantspace(
tree.root);
}
}
Python3
# Python3 program to implement # Post Order traversal # of Binary Tree in O(N) # time and O(1) space class node: def __init__(self, data): self.data = data self.left = None self.right = None # Helper function that allocates a # new node with the given data and # None left and right pointers. def newNode(data): temp = node(data) return temp # Postorder traversal without recursion # and without stack def postOrderConstSpace(root): if (root == None): return current = newNode(-1) pre = None prev = None succ = None temp = None current.left = root while (current): # If left child is None. # Move to right child. if (current.left == None): current = current.right else: pre = current.left # Inorder predecessor while (pre.right and pre.right != current): pre = pre.right # The connection between current # and predecessor is made if (pre.right == None): # Make current as the right # child of the right most node pre.right = current # Traverse the left child current = current.left else: pre.right = None succ = current current = current.left prev = None # Traverse along the right # subtree to the # right-most child while (current != None): temp = current.right current.right = prev prev = current current = temp # Traverse back # to current's left child # node while (prev != None): print(prev.data, end = ' ') temp = prev.right prev.right = current current = prev prev = temp current = succ current = current.right # Driver code if __name__=='__main__': ''' Constructed tree is as follows:- 1 / \ 2 3 / \ / \ 4 5 6 7 / \ 8 9 ''' root = None 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.right.left = newNode(8) root.left.right.right = newNode(9) postOrderConstSpace(root) # This code is contributed by pratham76
C#
// C# program to implement
// Post Order traversal
// of Binary Tree in O(N)
// time and O(1) space
using System;
// Definition of the
// binary tree
public class TreeNode
{
public int data;
public TreeNode left, right;
public TreeNode(int item)
{
data = item;
left = right = null;
}
}
class PostOrder{
public TreeNode root;
// Function to find Post Order
// Traversal Using Constant space
void postOrderConstantspace(TreeNode root)
{
if (root == null)
return;
TreeNode current = new TreeNode(-1), pre = null;
TreeNode prev = null,
succ = null,
temp = null;
current.left = root;
while (current != null)
{
// Go to the right child
// if current does not
// have a left child
if (current.left == null)
{
current = current.right;
}
else
{
// Traverse left child
pre = current.left;
// Find the right most child
// in the left subtree
while (pre.right != null &&
pre.right != current)
pre = pre.right;
if (pre.right == null)
{
// Make current as the right
// child of the right most node
pre.right = current;
// Traverse the left child
current = current.left;
}
else
{
pre.right = null;
succ = current;
current = current.left;
prev = null;
// Traverse along the right
// subtree to the
// right-most child
while (current != null)
{
temp = current.right;
current.right = prev;
prev = current;
current = temp;
}
// Traverse back from
// right most child to
// current's left child node
while (prev != null)
{
Console.Write(prev.data + " ");
temp = prev.right;
prev.right = current;
current = prev;
prev = temp;
}
current = succ;
current = current.right;
}
}
}
}
// Driver code
static public void Main ()
{
/* Constructed tree is as follows:-
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
*/
PostOrder tree = new PostOrder();
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(5);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(7);
tree.root.left.right.left = new TreeNode(8);
tree.root.left.right.right = new TreeNode(9);
tree.postOrderConstantspace(tree.root);
}
}
// This code is contributed by offbeat
Javascript
<script>
// Javascript program to implement
// Post Order traversal
// of Binary Tree in O(N)
// time and O(1) space
// Definition of the
// binary tree
class TreeNode
{
constructor(item)
{
this.data = item;
this.left = null;
this.right = null;
}
}
var root;
// Function to find Post Order
// Traversal Using Constant space
function postOrderConstantspace(root)
{
if (root == null)
return;
var current = new TreeNode(-1), pre = null;
var prev = null,
succ = null,
temp = null;
current.left = root;
while (current != null)
{
// Go to the right child
// if current does not
// have a left child
if (current.left == null)
{
current = current.right;
}
else
{
// Traverse left child
pre = current.left;
// Find the right most child
// in the left subtree
while (pre.right != null &&
pre.right != current)
pre = pre.right;
if (pre.right == null)
{
// Make current as the right
// child of the right most node
pre.right = current;
// Traverse the left child
current = current.left;
}
else
{
pre.right = null;
succ = current;
current = current.left;
prev = null;
// Traverse along the right
// subtree to the
// right-most child
while (current != null)
{
temp = current.right;
current.right = prev;
prev = current;
current = temp;
}
// Traverse back from
// right most child to
// current's left child node
while (prev != null)
{
document.write(prev.data + " ");
temp = prev.right;
prev.right = current;
current = prev;
prev = temp;
}
current = succ;
current = current.right;
}
}
}
}
// Driver code
/* Constructed tree is as follows:-
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
*/
var tree = new TreeNode();
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(5);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(7);
tree.root.left.right.left = new TreeNode(8);
tree.root.left.right.right = new TreeNode(9);
postOrderConstantspace(tree.root);
</script>
Producción
4 8 9 5 2 6 7 3 1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Método 2: en el método 1, recorremos una ruta, invertimos referencias, imprimimos Nodes a medida que restauramos las referencias invirtiéndolas nuevamente. En el método 2, en lugar de invertir las rutas y restaurar la estructura, viajamos al Node principal desde el Node actual usando el subárbol izquierdo del Node actual. Esto podría ser más rápido según la estructura del árbol, por ejemplo, en un árbol sesgado a la derecha.
El siguiente algoritmo y diagramas proporcionan los detalles del enfoque.
A continuación se muestra el diagrama conceptual que muestra cómo se utilizan las referencias secundarias izquierda y derecha para recorrer hacia adelante y hacia atrás.
A continuación se muestra el diagrama que destaca la ruta 1->2->5->9 y la forma en que se procesan e imprimen los Nodes según el algoritmo anterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement the above approach
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
TreeNode* left;
TreeNode* right;
int data;
TreeNode(int data)
{
this->data = data;
this->left = nullptr;
this->right = nullptr;
}
};
TreeNode* root;
// Function to Calculate Post
// Order Traversal Using
// Constant Space
static void postOrderConstantspace(TreeNode* root)
{
if (root == nullptr)
return;
TreeNode* current = nullptr;
TreeNode* prevNode = nullptr;
TreeNode* pre = nullptr;
TreeNode* ptr = nullptr;
TreeNode* netChild = nullptr;
TreeNode* prevPtr = nullptr;
current = root;
while (current != nullptr)
{
if (current->left == nullptr)
{
current->left = prevNode;
// Set prevNode to current
prevNode = current;
current = current->right;
}
else
{
pre = current->left;
// Find the right most child
// in the left subtree
while (pre->right != nullptr &&
pre->right != current)
pre = pre->right;
if (pre->right == nullptr)
{
pre->right = current;
current = current->left;
}
else
{
// Set the right most
// child's right pointer
// to NULL
pre->right = nullptr;
cout << pre->data << " ";
ptr = pre;
netChild = pre;
prevPtr = pre;
while (ptr != nullptr)
{
if (ptr->right == netChild)
{
cout << ptr->data << " ";
netChild = ptr;
prevPtr->left = nullptr;
}
if (ptr == current->left)
break;
// Break the loop
// all the left subtree
// nodes of current
// processed
prevPtr = ptr;
ptr = ptr->left;
}
prevNode = current;
current = current->right;
}
}
}
cout << prevNode->data << " ";
// Last path traversal
// that includes the root.
ptr = prevNode;
netChild = prevNode;
prevPtr = prevNode;
while (ptr != nullptr)
{
if (ptr->right == netChild)
{
cout << ptr->data << " ";
netChild = ptr;
prevPtr->left = nullptr;
}
if (ptr == root)
break;
prevPtr = ptr;
ptr = ptr->left;
}
}
int main()
{
/* Constructed tree is as follows:-
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
*/
root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
root->left->right->left = new TreeNode(8);
root->left->right->right = new TreeNode(9);
postOrderConstantspace(root);
return 0;
}
// This code is contributed by mukesh07.
Java
// Java Program to implement
// the above approach
class TreeNode {
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
}
public String toString()
{
return data + " ";
}
}
public class PostOrder {
TreeNode root;
// Function to Calculate Post
// Order Traversal
// Using Constant Space
void postOrderConstantspace(TreeNode root)
{
if (root == null)
return;
TreeNode current = null;
TreeNode prevNode = null;
TreeNode pre = null;
TreeNode ptr = null;
TreeNode netChild = null;
TreeNode prevPtr = null;
current = root;
while (current != null) {
if (current.left == null) {
current.left = prevNode;
// Set prevNode to current
prevNode = current;
current = current.right;
}
else {
pre = current.left;
// Find the right most child
// in the left subtree
while (pre.right != null
&& pre.right != current)
pre = pre.right;
if (pre.right == null) {
pre.right = current;
current = current.left;
}
else {
// Set the right most
// child's right pointer
// to NULL
pre.right = null;
System.out.print(pre);
ptr = pre;
netChild = pre;
prevPtr = pre;
while (ptr != null) {
if (ptr.right == netChild) {
System.out.print(ptr);
netChild = ptr;
prevPtr.left = null;
}
if (ptr == current.left)
break;
// Break the loop
// all the left subtree
// nodes of current
// processed
prevPtr = ptr;
ptr = ptr.left;
}
prevNode = current;
current = current.right;
}
}
}
System.out.print(prevNode);
// Last path traversal
// that includes the root.
ptr = prevNode;
netChild = prevNode;
prevPtr = prevNode;
while (ptr != null) {
if (ptr.right == netChild) {
System.out.print(ptr);
netChild = ptr;
prevPtr.left = null;
}
if (ptr == root)
break;
prevPtr = ptr;
ptr = ptr.left;
}
}
// Main Function
public static void main(String[] args)
{
/* Constructed tree is as follows:-
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
*/
PostOrder tree = new PostOrder();
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left
= new TreeNode(4);
tree.root.left.right
= new TreeNode(5);
tree.root.right.left
= new TreeNode(6);
tree.root.right.right
= new TreeNode(7);
tree.root.left.right.left
= new TreeNode(8);
tree.root.left.right.right
= new TreeNode(9);
tree.postOrderConstantspace(
tree.root);
}
}
Python3
# Python3 Program to implement the above approach class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None # Function to Calculate Post # Order Traversal Using # Constant Space def postOrderConstantspace(root): if root == None: return current = None prevNode = None pre = None ptr = None netChild = None prevPtr = None current = root while current != None: if current.left == None: current.left = prevNode # Set prevNode to current prevNode = current current = current.right else: pre = current.left # Find the right most child # in the left subtree while pre.right != None and pre.right != current: pre = pre.right if pre.right == None: pre.right = current current = current.left else: # Set the right most # child's right pointer # to NULL pre.right = None print(pre.data, end = " ") ptr = pre netChild = pre prevPtr = pre while ptr != None: if ptr.right == netChild: print(ptr.data, end = " ") netChild = ptr prevPtr.left = None if ptr == current.left: break # Break the loop # all the left subtree # nodes of current # processed prevPtr = ptr ptr = ptr.left prevNode = current current = current.right print(prevNode.data, end = " ") # Last path traversal # that includes the root. ptr = prevNode netChild = prevNode prevPtr = prevNode while ptr != None: if ptr.right == netChild: print(ptr.data, end = " ") netChild = ptr prevPtr.left = None if (ptr == root): break prevPtr = ptr ptr = ptr.left """ Constructed tree is as follows:- 1 / \ 2 3 / \ / \ 4 5 6 7 / \ 8 9 """ root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) root.right.left = TreeNode(6) root.right.right = TreeNode(7) root.left.right.left = TreeNode(8) root.left.right.right = TreeNode(9) postOrderConstantspace(root) # This code is contributed by divyeshrabadiya07.
C#
// C# Program to implement
// the above approach
using System;
class TreeNode{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
}
public string toString()
{
return data + " ";
}
}
class PostOrder{
TreeNode root;
// Function to Calculate Post
// Order Traversal Using
// Constant Space
void postOrderConstantspace(TreeNode root)
{
if (root == null)
return;
TreeNode current = null;
TreeNode prevNode = null;
TreeNode pre = null;
TreeNode ptr = null;
TreeNode netChild = null;
TreeNode prevPtr = null;
current = root;
while (current != null)
{
if (current.left == null)
{
current.left = prevNode;
// Set prevNode to current
prevNode = current;
current = current.right;
}
else
{
pre = current.left;
// Find the right most child
// in the left subtree
while (pre.right != null &&
pre.right != current)
pre = pre.right;
if (pre.right == null)
{
pre.right = current;
current = current.left;
}
else
{
// Set the right most
// child's right pointer
// to NULL
pre.right = null;
Console.Write(pre.data + " ");
ptr = pre;
netChild = pre;
prevPtr = pre;
while (ptr != null)
{
if (ptr.right == netChild)
{
Console.Write(ptr.data + " ");
netChild = ptr;
prevPtr.left = null;
}
if (ptr == current.left)
break;
// Break the loop
// all the left subtree
// nodes of current
// processed
prevPtr = ptr;
ptr = ptr.left;
}
prevNode = current;
current = current.right;
}
}
}
Console.Write(prevNode.data + " ");
// Last path traversal
// that includes the root.
ptr = prevNode;
netChild = prevNode;
prevPtr = prevNode;
while (ptr != null)
{
if (ptr.right == netChild)
{
Console.Write(ptr.data + " ");
netChild = ptr;
prevPtr.left = null;
}
if (ptr == root)
break;
prevPtr = ptr;
ptr = ptr.left;
}
}
// Driver code
public static void Main(string[] args)
{
/* Constructed tree is as follows:-
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
*/
PostOrder tree = new PostOrder();
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(5);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(7);
tree.root.left.right.left = new TreeNode(8);
tree.root.left.right.right = new TreeNode(9);
tree.postOrderConstantspace(tree.root);
}
}
// This code is contributed by Rutvik_56
Javascript
<script>
// Javascript Program to implement the above approach
class TreeNode
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
let root;
// Function to Calculate Post
// Order Traversal Using
// Constant Space
function postOrderConstantspace(root)
{
if (root == null)
return;
let current = null;
let prevNode = null;
let pre = null;
let ptr = null;
let netChild = null;
let prevPtr = null;
current = root;
while (current != null)
{
if (current.left == null)
{
current.left = prevNode;
// Set prevNode to current
prevNode = current;
current = current.right;
}
else
{
pre = current.left;
// Find the right most child
// in the left subtree
while (pre.right != null &&
pre.right != current)
pre = pre.right;
if (pre.right == null)
{
pre.right = current;
current = current.left;
}
else
{
// Set the right most
// child's right pointer
// to NULL
pre.right = null;
document.write(pre.data + " ");
ptr = pre;
netChild = pre;
prevPtr = pre;
while (ptr != null)
{
if (ptr.right == netChild)
{
document.write(ptr.data + " ");
netChild = ptr;
prevPtr.left = null;
}
if (ptr == current.left)
break;
// Break the loop
// all the left subtree
// nodes of current
// processed
prevPtr = ptr;
ptr = ptr.left;
}
prevNode = current;
current = current.right;
}
}
}
document.write(prevNode.data + " ");
// Last path traversal
// that includes the root.
ptr = prevNode;
netChild = prevNode;
prevPtr = prevNode;
while (ptr != null)
{
if (ptr.right == netChild)
{
document.write(ptr.data + " ");
netChild = ptr;
prevPtr.left = null;
}
if (ptr == root)
break;
prevPtr = ptr;
ptr = ptr.left;
}
}
/* Constructed tree is as follows:-
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
*/
root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
root.left.right.left = new TreeNode(8);
root.left.right.right = new TreeNode(9);
postOrderConstantspace(root);
// This code is contributed by divyesh072019.
</script>
Producción
4 8 9 5 2 6 7 3 1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)