Dado un árbol de búsqueda binario y un entero binario K , la tarea es convertir el árbol de búsqueda binario en un árbol sesgado en orden creciente si K = 0 o en orden decreciente si K = 1 .
Ejemplos:
Input: K = 0,
5
/ \
3 6
Output:
3
\
5
\
6
Input: K = 1,
2
/ \
1 3
Output:
3
\
2
\
1
Acercarse:
- La observación clave en el problema es que el primer Node del árbol sesgado será el Node extremo izquierdo o extremo derecho del BST para orden creciente y decreciente respectivamente.
- Para el orden creciente , necesitamos hacer el recorrido en orden , ya que el recorrido en orden de un BST nos proporciona la secuencia creciente de los valores de los Nodes. Por lo tanto, el orden de recorrido en cada Node será:
- Node izquierdo: recurra a su Node izquierdo si existe, para obtener un valor más pequeño.
- Node raíz: después del recorrido completo de su Node/subárbol izquierdo, conecte el Node anterior del árbol sesgado al Node raíz.
- Node derecho: recurra al Node derecho si existe, para valores más grandes.
- Para Orden decreciente , el orden de recorrido en cada Node será:
- Node derecho: recurra a su Node derecho si existe, para obtener valores más grandes.
- Node raíz: después del recorrido completo de su Node/subárbol derecho, conecte el Node anterior del árbol sesgado al Node raíz.
- Node izquierdo: recurra al Node/subárbol izquierdo para valores más pequeños.
- De manera similar, al realizar un seguimiento del Node anterior, podemos atravesar el árbol de búsqueda binario según el orden necesario y formar el árbol sesgado.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ implementation to flatten the
// binary search tree into a skewed
// tree in increasing / decreasing order
#include<bits/stdc++.h>
using namespace std;
// Class of the node
struct Node
{
int val;
Node *left, *right;
Node(int x)
{
val = x;
left = right = NULL;
}
};
Node *prevNode = NULL;
Node *headNode = NULL;
// Function to to flatten the binary
// search tree into a skewed tree in
// increasing / decreasing order
void flattenBTToSkewed(Node *root, int order)
{
// Base Case
if (!root)
return;
// Condition to check the order
// in which the skewed tree to
// maintained
if (order)
flattenBTToSkewed(root->right, order);
else
flattenBTToSkewed(root->left, order);
Node *rightNode = root->right;
Node *leftNode = root->left;
// Condition to check if the root Node
// of the skewed tree is not defined
if (!headNode)
{
headNode = root;
root->left = NULL;
prevNode = root;
}
else
{
prevNode->right = root;
root->left = NULL;
prevNode = root;
}
// Similarly recurse for the left / right
// subtree on the basis of the order required
if (order)
flattenBTToSkewed(leftNode, order);
else
flattenBTToSkewed(rightNode, order);
}
// Function to traverse the right
// skewed tree using recursion
void traverseRightSkewed(Node *root)
{
if (!root)
return;
cout << root->val << " ";
traverseRightSkewed(root->right);
}
// Driver Code
int main()
{
// 5
// / \
// 3 6
Node *root =new Node(5);
root->left = new Node(3);
root->right = new Node(6);
// Order of the Skewed tree can
// be defined as follows -
// For Increasing order - 0
// For Decreasing order - 1
int order = 0;
flattenBTToSkewed(root, order);
traverseRightSkewed(headNode);
}
// This code is contributed by mohit kumar 29
Java
// Java implementation to flatten the
// binary search tree into a skewed
// tree in increasing / decreasing order
import java.io.*;
// Class of the node
class Node
{
int val;
Node left, right;
// Helper function that allocates a new node
// with the given data and NULL left and right
// pointers.
Node(int item)
{
val = item;
left = right = null;
}
}
class GFG
{
public static Node node;
static Node prevNode = null;
static Node headNode = null;
// Function to to flatten the binary
// search tree into a skewed tree in
// increasing / decreasing order
static void flattenBTToSkewed(Node root,
int order)
{
// Base Case
if(root == null)
{
return;
}
// Condition to check the order
// in which the skewed tree to
// maintained
if(order > 0)
{
flattenBTToSkewed(root.right, order);
}
else
{
flattenBTToSkewed(root.left, order);
}
Node rightNode = root.right;
Node leftNode = root.left;
// Condition to check if the root Node
// of the skewed tree is not defined
if(headNode == null)
{
headNode = root;
root.left = null;
prevNode = root;
}
else
{
prevNode.right = root;
root.left = null;
prevNode = root;
}
// Similarly recurse for the left / right
// subtree on the basis of the order required
if (order > 0)
{
flattenBTToSkewed(leftNode, order);
}
else
{
flattenBTToSkewed(rightNode, order);
}
}
// Function to traverse the right
// skewed tree using recursion
static void traverseRightSkewed(Node root)
{
if(root == null)
{
return;
}
System.out.print(root.val + " ");
traverseRightSkewed(root.right);
}
// Driver Code
public static void main (String[] args)
{
// 5
// / \
// 3 6
GFG tree = new GFG();
tree.node = new Node(5);
tree.node.left = new Node(3);
tree.node.right = new Node(6);
// Order of the Skewed tree can
// be defined as follows -
// For Increasing order - 0
// For Decreasing order - 1
int order = 0;
flattenBTToSkewed(node, order);
traverseRightSkewed(headNode);
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 implementation to flatten # the binary search tree into a skewed # tree in increasing / decreasing order # Class of the node class Node: # Constructor of node def __init__(self, val): self.val = val self.left = None self.right = None prevNode = None headNode = None # Function to to flatten # the binary search tree into a skewed # tree in increasing / decreasing order def flattenBTToSkewed(root, order): # Base Case if not root: return # Condition to check the order # in which the skewed tree to maintained if order: flattenBTToSkewed(root.right, order) else: flattenBTToSkewed(root.left, order) global headNode; global prevNode rightNode = root.right leftNode = root.left # Condition to check if the root Node # of the skewed tree is not defined if not headNode: headNode = root root.left = None prevNode = root else: prevNode.right = root root.left = None prevNode = root # Similarly recurse for the left / right # subtree on the basis of the order required if order: flattenBTToSkewed(leftNode, order) else: flattenBTToSkewed(rightNode, order) # Function to traverse the right # skewed tree using recursion def traverseRightSkewed(root): if not root: return print(root.val, end = " ") traverseRightSkewed(root.right) # Driver Code if __name__ == "__main__": # 5 # / \ # 3 6 root = Node(5) root.left = Node(3) root.right = Node(6) prevNode = None headNode = None # Order of the Skewed tree can # be defined as follows - # For Increasing order - 0 # For Decreasing order - 1 order = 0 flattenBTToSkewed(root, order) traverseRightSkewed(headNode)
C#
// C# implementation to flatten the
// binary search tree into a skewed
// tree in increasing / decreasing order
using System;
// Class of the node
class Node
{
public int val;
public Node left, right;
// Helper function that allocates a new
// node with the given data and NULL
// left and right pointers.
public Node(int item)
{
val = item;
left = right = null;
}
}
class GFG{
public static Node node;
static Node prevNode = null;
static Node headNode = null;
// Function to to flatten the binary
// search tree into a skewed tree in
// increasing / decreasing order
static void flattenBTToSkewed(Node root, int order)
{
// Base Case
if (root == null)
{
return;
}
// Condition to check the order
// in which the skewed tree to
// maintained
if (order > 0)
{
flattenBTToSkewed(root.right, order);
}
else
{
flattenBTToSkewed(root.left, order);
}
Node rightNode = root.right;
Node leftNode = root.left;
// Condition to check if the root Node
// of the skewed tree is not defined
if (headNode == null)
{
headNode = root;
root.left = null;
prevNode = root;
}
else
{
prevNode.right = root;
root.left = null;
prevNode = root;
}
// Similarly recurse for the left / right
// subtree on the basis of the order required
if (order > 0)
{
flattenBTToSkewed(leftNode, order);
}
else
{
flattenBTToSkewed(rightNode, order);
}
}
// Function to traverse the right
// skewed tree using recursion
static void traverseRightSkewed(Node root)
{
if (root == null)
{
return;
}
Console.Write(root.val + " ");
traverseRightSkewed(root.right);
}
// Driver Code
static public void Main()
{
// 5
// / \
// 3 6
GFG.node = new Node(5);
GFG.node.left = new Node(3);
GFG.node.right = new Node(6);
// Order of the Skewed tree can
// be defined as follows -
// For Increasing order - 0
// For Decreasing order - 1
int order = 0;
flattenBTToSkewed(node, order);
traverseRightSkewed(headNode);
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript implementation to flatten the
// binary search tree into a skewed
// tree in increasing / decreasing order
// Class of the node
class Node
{
// Helper function that allocates a new node
// with the given data and NULL left and right
// pointers.
constructor(item)
{
this.val = item;
this.left = this.right = null;
}
}
let node;
let prevNode = null;
let headNode = null;
// Function to to flatten the binary
// search tree into a skewed tree in
// increasing / decreasing order
function flattenBTToSkewed(root,order)
{
// Base Case
if(root == null)
{
return;
}
// Condition to check the order
// in which the skewed tree to
// maintained
if(order > 0)
{
flattenBTToSkewed(root.right, order);
}
else
{
flattenBTToSkewed(root.left, order);
}
let rightNode = root.right;
let leftNode = root.left;
// Condition to check if the root Node
// of the skewed tree is not defined
if(headNode == null)
{
headNode = root;
root.left = null;
prevNode = root;
}
else
{
prevNode.right = root;
root.left = null;
prevNode = root;
}
// Similarly recurse for the left / right
// subtree on the basis of the order required
if (order > 0)
{
flattenBTToSkewed(leftNode, order);
}
else
{
flattenBTToSkewed(rightNode, order);
}
}
// Function to traverse the right
// skewed tree using recursion
function traverseRightSkewed(root)
{
if(root == null)
{
return;
}
document.write(root.val + " ");
traverseRightSkewed(root.right);
}
// Driver Code
// 5
// / \
// 3 6
node = new Node(5);
node.left = new Node(3);
node.right = new Node(6);
// Order of the Skewed tree can
// be defined as follows -
// For Increasing order - 0
// For Decreasing order - 1
let order = 0;
flattenBTToSkewed(node, order);
traverseRightSkewed(headNode);
// This code is contributed by unknown2108
</script>
Producción:
3 5 6
Publicación traducida automáticamente
Artículo escrito por Archit_Dwevedi0 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA