Hemos hablado de Morris Traversal basado en subprocesos . ¿Podemos hacer un recorrido en orden sin subprocesos si tenemos punteros principales disponibles para nosotros?
Input: Root of Below Tree [Every node of
tree has parent pointer also]
10
/ \
5 100
/ \
80 120
Output: 5 10 80 100 120
The code should not extra space (No Recursion
and stack)
C++
// C++ program to print inorder traversal of a Binary Search
// Tree (BST) without recursion and stack
#include <bits/stdc++.h>
using namespace std;
// BST Node
struct Node
{
Node *left, *right, *parent;
int key;
};
// A utility function to create a new BST node
Node *newNode(int item)
{
Node *temp = new Node;
temp->key = item;
temp->parent = temp->left = temp->right = NULL;
return temp;
}
/* A utility function to insert a new node with
given key in BST */
Node *insert(Node *node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->key)
{
node->left = insert(node->left, key);
node->left->parent = node;
}
else if (key > node->key)
{
node->right = insert(node->right, key);
node->right->parent = node;
}
/* return the (unchanged) node pointer */
return node;
}
// Function to print inorder traversal using parent
// pointer
void inorder(Node *root)
{
bool leftdone = false;
// Start traversal from root
while (root)
{
// If left child is not traversed, find the
// leftmost child
if (!leftdone)
{
while (root->left)
root = root->left;
}
// Print root's data
printf("%d ", root->key);
// Mark left as done
leftdone = true;
// If right child exists
if (root->right)
{
leftdone = false;
root = root->right;
}
// If right child doesn't exist, move to parent
else if (root->parent)
{
// If this node is right child of its parent,
// visit parent's parent first
while (root->parent &&
root == root->parent->right)
root = root->parent;
if (!root->parent)
break;
root = root->parent;
}
else break;
}
}
int main(void)
{
Node * root = NULL;
root = insert(root, 24);
root = insert(root, 27);
root = insert(root, 29);
root = insert(root, 34);
root = insert(root, 14);
root = insert(root, 4);
root = insert(root, 10);
root = insert(root, 22);
root = insert(root, 13);
root = insert(root, 3);
root = insert(root, 2);
root = insert(root, 6);
printf("Inorder traversal is \n");
inorder(root);
return 0;
}
Java
/* Java program to print inorder traversal of a Binary Search Tree
without recursion and stack */
// BST node
class Node
{
int key;
Node left, right, parent;
public Node(int key)
{
this.key = key;
left = right = parent = null;
}
}
class BinaryTree
{
Node root;
/* A utility function to insert a new node with
given key in BST */
Node insert(Node node, int key)
{
/* If the tree is empty, return a new node */
if (node == null)
return new Node(key);
/* Otherwise, recur down the tree */
if (key < node.key)
{
node.left = insert(node.left, key);
node.left.parent = node;
}
else if (key > node.key)
{
node.right = insert(node.right, key);
node.right.parent = node;
}
/* return the (unchanged) node pointer */
return node;
}
// Function to print inorder traversal using parent
// pointer
void inorder(Node root)
{
boolean leftdone = false;
// Start traversal from root
while (root != null)
{
// If left child is not traversed, find the
// leftmost child
if (!leftdone)
{
while (root.left != null)
{
root = root.left;
}
}
// Print root's data
System.out.print(root.key + " ");
// Mark left as done
leftdone = true;
// If right child exists
if (root.right != null)
{
leftdone = false;
root = root.right;
}
// If right child doesn't exist, move to parent
else if (root.parent != null)
{
// If this node is right child of its parent,
// visit parent's parent first
while (root.parent != null
&& root == root.parent.right)
root = root.parent;
if (root.parent == null)
break;
root = root.parent;
}
else
break;
}
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = tree.insert(tree.root, 24);
tree.root = tree.insert(tree.root, 27);
tree.root = tree.insert(tree.root, 29);
tree.root = tree.insert(tree.root, 34);
tree.root = tree.insert(tree.root, 14);
tree.root = tree.insert(tree.root, 4);
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 22);
tree.root = tree.insert(tree.root, 13);
tree.root = tree.insert(tree.root, 3);
tree.root = tree.insert(tree.root, 2);
tree.root = tree.insert(tree.root, 6);
System.out.println("Inorder traversal is ");
tree.inorder(tree.root);
}
}
// This code has been contributed by Mayank Jaiswal(mayank_24)
Python3
# Python3 program to print inorder traversal of a
# Binary Search Tree (BST) without recursion and stack
# A utility function to create a new BST node
class newNode:
def __init__(self, item):
self.key = item
self.parent = self.left = self.right = None
# A utility function to insert a new
# node with given key in BST
def insert(node, key):
# If the tree is empty, return a new node
if node == None:
return newNode(key)
# Otherwise, recur down the tree
if key < node.key:
node.left = insert(node.left, key)
node.left.parent = node
elif key > node.key:
node.right = insert(node.right, key)
node.right.parent = node
# return the (unchanged) node pointer
return node
# Function to print inorder traversal
# using parent pointer
def inorder(root):
leftdone = False
# Start traversal from root
while root:
# If left child is not traversed,
# find the leftmost child
if leftdone == False:
while root.left:
root = root.left
# Print root's data
print(root.key, end = " ")
# Mark left as done
leftdone = True
# If right child exists
if root.right:
leftdone = False
root = root.right
# If right child doesn't exist, move to parent
elif root.parent:
# If this node is right child of its
# parent, visit parent's parent first
while root.parent and root == root.parent.right:
root = root.parent
if root.parent == None:
break
root = root.parent
else:
break
# Driver Code
if __name__ == '__main__':
root = None
root = insert(root, 24)
root = insert(root, 27)
root = insert(root, 29)
root = insert(root, 34)
root = insert(root, 14)
root = insert(root, 4)
root = insert(root, 10)
root = insert(root, 22)
root = insert(root, 13)
root = insert(root, 3)
root = insert(root, 2)
root = insert(root, 6)
print("Inorder traversal is ")
inorder(root)
# This code is contributed by PranchalK
C#
// C# program to print inorder traversal
// of a Binary Search Tree without
// recursion and stack
using System;
// BST node
class Node
{
public int key;
public Node left, right, parent;
public Node(int key)
{
this.key = key;
left = right = parent = null;
}
}
class BinaryTree
{
Node root;
/* A utility function to insert a
new node with given key in BST */
Node insert(Node node, int key)
{
/* If the tree is empty,
return a new node */
if (node == null)
return new Node(key);
/* Otherwise, recur down the tree */
if (key < node.key)
{
node.left = insert(node.left, key);
node.left.parent = node;
}
else if (key > node.key)
{
node.right = insert(node.right, key);
node.right.parent = node;
}
/* return the (unchanged) node pointer */
return node;
}
// Function to print inorder traversal
// using parent pointer
void inorder(Node root)
{
Boolean leftdone = false;
// Start traversal from root
while (root != null)
{
// If left child is not traversed,
// find the leftmost child
if (!leftdone)
{
while (root.left != null)
{
root = root.left;
}
}
// Print root's data
Console.Write(root.key + " ");
// Mark left as done
leftdone = true;
// If right child exists
if (root.right != null)
{
leftdone = false;
root = root.right;
}
// If right child doesn't exist,
// move to parent
else if (root.parent != null)
{
// If this node is right child
// of its parent, visit parent's
// parent first
while (root.parent != null &&
root == root.parent.right)
root = root.parent;
if (root.parent == null)
break;
root = root.parent;
}
else
break;
}
}
// Driver Code
static public void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = tree.insert(tree.root, 24);
tree.root = tree.insert(tree.root, 27);
tree.root = tree.insert(tree.root, 29);
tree.root = tree.insert(tree.root, 34);
tree.root = tree.insert(tree.root, 14);
tree.root = tree.insert(tree.root, 4);
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 22);
tree.root = tree.insert(tree.root, 13);
tree.root = tree.insert(tree.root, 3);
tree.root = tree.insert(tree.root, 2);
tree.root = tree.insert(tree.root, 6);
Console.WriteLine("Inorder traversal is ");
tree.inorder(tree.root);
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
/* javascript program to print inorder traversal of a Binary Search Tree
without recursion and stack */
// BST node
class Node {
constructor(key) {
this.key = key;
this.left = this.right = this.parent = null;
}
}
var root = null;
/*
* A utility function to insert a new node with given key in BST
*/
function insert(node , key) {
/* If the tree is empty, return a new node */
if (node == null)
return new Node(key);
/* Otherwise, recur down the tree */
if (key < node.key) {
node.left = insert(node.left, key);
node.left.parent = node;
} else if (key > node.key) {
node.right = insert(node.right, key);
node.right.parent = node;
}
/* return the (unchanged) node pointer */
return node;
}
// Function to print inorder traversal using parent
// pointer
function inorder(root) {
var leftdone = false;
// Start traversal from root
while (root != null) {
// If left child is not traversed, find the
// leftmost child
if (!leftdone) {
while (root.left != null) {
root = root.left;
}
}
// Print root's data
document.write(root.key + " ");
// Mark left as done
leftdone = true;
// If right child exists
if (root.right != null) {
leftdone = false;
root = root.right;
}
// If right child doesn't exist, move to parent
else if (root.parent != null) {
// If this node is right child of its parent,
// visit parent's parent first
while (root.parent != null && root == root.parent.right)
root = root.parent;
if (root.parent == null)
break;
root = root.parent;
} else
break;
}
}
root = insert(root, 24);
root = insert(root, 27);
root = insert(root, 29);
root = insert(root, 34);
root = insert(root, 14);
root = insert(root, 4);
root = insert(root, 10);
root = insert(root, 22);
root = insert(root, 13);
root = insert(root, 3);
root = insert(root, 2);
root = insert(root, 6);
document.write("Inorder traversal is ");
inorder(root);
// This code contributed by aashish1995
</script>
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