Dado un árbol binario y dos números P y K , la tarea es imprimir el Sucesor en orden K del número dado P del árbol binario en espacio constante. Ejemplos:
Entrada: Árbol:
1 / \ 12 11 / / \ 3 4 13 \ / 15 9P = 12, K = 4
Salida: 1 4 15 11
Explicación:
Recorrido en orden: 3 12 1 4 15 11 9 13
Los 4 Sucesores en orden de un Node 12 son {1, 4, 15, 11}
Entrada: Árbol:
5 / \ 21 77 / \ \ 61 16 36 \ / 10 3 / 23P = 23, K = 3
Salida: 10 5 77
Explicación:
recorrido en orden: 61 21 16 23 10 5 77 3 36
Los 3 sucesores en orden de un Node 23 son {10, 5, 77}.
Enfoque:
para resolver este problema, estamos utilizando el recorrido en orden de Morris de un árbol binario para evitar el uso de espacio adicional. Busque el Node ‘P’ mientras genera la secuencia en orden. Una vez encontrado, imprima los siguientes K Nodes que aparecen en la secuencia en orden.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to print K Inorder
// Successor of the Binary Tree
// without using extra space
#include <bits/stdc++.h>
using namespace std;
/* A binary tree Node has data,
a pointer to left child
and a pointer to right child */
struct tNode {
int data;
struct tNode* left;
struct tNode* right;
};
/* Function to traverse the
binary tree without recursion and
without stack */
void MorrisTraversal(struct tNode* root,
int p, int k)
{
struct tNode *current, *pre;
if (root == NULL)
return;
bool flag = false;
current = root;
while (current != NULL) {
// Check if the left child exists
if (current->left == NULL) {
if (flag == true) {
cout << current->data
<< " ";
k--;
}
if (current->data == p)
flag = true;
// Check if K is 0
if (k == 0)
flag = false;
// Move current to its right
current = current->right;
}
else {
// Find the inorder predecessor
// of current
pre = current->left;
while (pre->right != NULL
&& pre->right != current)
pre = pre->right;
/* Make current as the right
child of its inorder
predecessor */
if (pre->right == NULL) {
pre->right = current;
current = current->left;
}
/* Revert the changes made in the
'if' part to restore the original
tree i.e., fix the right child
of predecessor */
else {
pre->right = NULL;
if (flag == true) {
cout << current->data
<< " ";
k--;
}
if (current->data == p)
flag = true;
if (k == 0)
flag = false;
current = current->right;
}
}
}
}
/* Function that allocates
a new Node with the
given data and NULL left
and right pointers. */
struct tNode* newtNode(int data)
{
struct tNode* node = new tNode;
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
/* Driver code*/
int main()
{
struct tNode* root = newtNode(1);
root->left = newtNode(12);
root->right = newtNode(11);
root->left->left = newtNode(3);
root->right->left = newtNode(4);
root->right->right = newtNode(13);
root->right->left->right = newtNode(15);
root->right->right->left = newtNode(9);
int p = 12;
int k = 4;
MorrisTraversal(root, p, k);
return 0;
}
Java
// Java implementation to print K Inorder
// Successor of the Binary Tree
// without using extra space
// A binary tree Node has data,
// a pointer to left child
// and a pointer to right child
class tNode
{
int data;
tNode left, right;
tNode(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree{
tNode root;
// Function to traverse a binary tree
// without recursion and without stack
void MorrisTraversal(tNode root, int p, int k)
{
tNode current, pre;
if (root == null)
return;
boolean flag = false;
current = root;
while (current != null)
{
if (current.left == null)
{
if (flag == true)
{
System.out.print(current.data + " ");
k--;
}
if (current.data == p)
{
flag = true;
}
if (k == 0)
{
flag = false;
}
current = current.right;
}
else
{
// Find the inorder predecessor
// of current
pre = current.left;
while (pre.right != null &&
pre.right != current)
pre = pre.right;
// Make current as right child of
// its inorder predecessor
if (pre.right == null)
{
pre.right = current;
current = current.left;
}
// Revert the changes made in the
// 'if' part to restore the original
// tree i.e., fix the right child of
// predecessor
else
{
pre.right = null;
if (flag == true)
{
System.out.print(current.data + " ");
k--;
}
if (current.data == p)
{
flag = true;
}
if (k == 0)
{
flag = false;
}
current = current.right;
}
}
}
}
// Driver code
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new tNode(1);
tree.root.left = new tNode(12);
tree.root.right = new tNode(11);
tree.root.left.left = new tNode(3);
tree.root.right.left = new tNode(4);
tree.root.right.right = new tNode(13);
tree.root.right.left.right = new tNode(15);
tree.root.right.right.left = new tNode(9);
int p = 12;
int k = 4;
tree.MorrisTraversal(tree.root, p, k);
}
}
// This code is contributed by MOHAMMAD MUDASSIR
Python3
# Python3 implementation to print K Inorder # Successor of the Binary Tree # without using extra space ''' A binary tree Node has data, a pointer to left child and a pointer to right child ''' class tNode: def __init__(self, data): self.data = data self.left = None self.right = None ''' Function to traverse the binary tree without recursion and without stack ''' def MorrisTraversal(root, p, k): current = None pre = None if (root == None): return; flag = False; current = root; while (current != None): # Check if the left child exists if (current.left == None): if (flag == True): print(current.data, end = ' ') k -= 1 if (current.data == p): flag = True; # Check if K is 0 if (k == 0): flag = False; # Move current to its right current = current.right; else: # Find the inorder predecessor # of current pre = current.left while (pre.right != None and pre.right != current): pre = pre.right; # Make current as the right #child of its inorder predecessor if(pre.right == None): pre.right = current; current = current.left; # Revert the changes made in the # 'if' part to restore the original # tree i.e., fix the right child # of predecessor else: pre.right = None; if (flag == True): print(current.data, end = ' ') k -= 1 if (current.data == p): flag = True; if (k == 0): flag = False; current = current.right; ''' Function that allocates a new Node with the given data and None left and right pointers. ''' def newtNode(data): node = tNode(data); return (node); # Driver code if __name__=='__main__': root = newtNode(1); root.left = newtNode(12); root.right = newtNode(11); root.left.left = newtNode(3); root.right.left = newtNode(4); root.right.right = newtNode(13); root.right.left.right = newtNode(15); root.right.right.left = newtNode(9); p = 12; k = 4; MorrisTraversal(root, p, k); # This code is contributed by rutvik_56
C#
// C# program to print inorder traversal
// without recursion and stack
using System;
// A binary tree Node has data,
// pointer to left child and a
// pointer to right child
class BinaryTree{
tNode root;
public class tNode
{
public int data;
public tNode left, right;
public tNode(int item)
{
data = item;
left = right = null;
}
}
// Function to traverse binary tree without
// recursion and without stack
void MorrisTraversal(tNode root, int p, int k)
{
tNode current, pre;
if (root == null)
return;
current = root;
bool flag = false;
while (current != null)
{
if (current.left == null)
{
if (flag == true)
{
Console.Write(current.data + " ");
k--;
}
if (current.data == p)
{
flag = true;
}
if (k == 0)
{
flag = false;
}
current = current.right;
}
else
{
// Find the inorder predecessor
// of current
pre = current.left;
while (pre.right != null &&
pre.right != current)
pre = pre.right;
// Make current as right child
// of its inorder predecessor
if (pre.right == null)
{
pre.right = current;
current = current.left;
}
// Revert the changes made in
// if part to restore the original
// tree i.e., fix the right child
// of predecessor
else
{
pre.right = null;
if (flag == true)
{
Console.Write(current.data + " ");
k--;
}
if (current.data == p)
{
flag = true;
}
if (k == 0)
{
flag = false;
}
current = current.right;
}
}
}
}
// Driver code
public static void Main(String []args)
{
BinaryTree tree = new BinaryTree();
tree.root = new tNode(1);
tree.root.left = new tNode(12);
tree.root.right = new tNode(11);
tree.root.left.left = new tNode(3);
tree.root.right.left = new tNode(4);
tree.root.right.right = new tNode(13);
tree.root.right.left.right = new tNode(15);
tree.root.right.right.left = new tNode(9);
int p = 12;
int k = 4;
tree.MorrisTraversal(tree.root, p, k);
}
}
// This code is contributed by MOHAMMAD MUDASSIR
Javascript
<script>
// Javascript implementation to print K Inorder
// Successor of the Binary Tree
// without using extra space
// A binary tree Node has data,
// a pointer to left child
// and a pointer to right child
class tNode
{
constructor(item) {
this.left = null;
this.right = null;
this.data = item;
}
}
let root;
// Function to traverse a binary tree
// without recursion and without stack
function MorrisTraversal(root, p, k)
{
let current, pre;
if (root == null)
return;
let flag = false;
current = root;
while (current != null)
{
if (current.left == null)
{
if (flag == true)
{
document.write(current.data + " ");
k--;
}
if (current.data == p)
{
flag = true;
}
if (k == 0)
{
flag = false;
}
current = current.right;
}
else
{
// Find the inorder predecessor
// of current
pre = current.left;
while (pre.right != null &&
pre.right != current)
pre = pre.right;
// Make current as right child of
// its inorder predecessor
if (pre.right == null)
{
pre.right = current;
current = current.left;
}
// Revert the changes made in the
// 'if' part to restore the original
// tree i.e., fix the right child of
// predecessor
else
{
pre.right = null;
if (flag == true)
{
document.write(current.data + " ");
k--;
}
if (current.data == p)
{
flag = true;
}
if (k == 0)
{
flag = false;
}
current = current.right;
}
}
}
}
root = new tNode(1);
root.left = new tNode(12);
root.right = new tNode(11);
root.left.left = new tNode(3);
root.right.left = new tNode(4);
root.right.right = new tNode(13);
root.right.left.right = new tNode(15);
root.right.right.left = new tNode(9);
let p = 12;
let k = 4;
MorrisTraversal(root, p, k);
// This code is contributed by decode2207.
</script>
Producción:
1 4 15 11
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA