Dada una string str que contiene solo caracteres en minúsculas. El problema es imprimir los caracteres junto con su frecuencia en el orden en que aparecen usando
ejemplos de árboles binarios:
Entrada: str = “aaaabbnnccccz”
Salida: “a4b2n2c4z”
Explicación:
Entrada: str = «geeksforgeeks»
Salida: g2e4k2s2for
Acercarse:
- Comience con el primer carácter de la string.
- Realizar una inserción de orden de nivel del carácter en el árbol binario
- Elige el siguiente personaje:
- Si el personaje ha sido visto y lo encontramos durante la inserción del orden de nivel, aumente la cuenta del Node.
- Si el personaje no se ha visto hasta ahora, vaya al paso número 2.
- Repita el proceso para todos los caracteres de la string.
- Imprima el recorrido de orden de nivel del árbol que debe generar la salida deseada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Node in the tree where
// data holds the character
// of the string and cnt
// holds the frequency
struct node {
char data;
int cnt;
node *left, *right;
};
// Function to add a new
// node to the Binary Tree
node* add(char data)
{
// Create a new node and
// populate its data part,
// set cnt as 1 and left
// and right children as NULL
node* newnode = new node;
newnode->data = data;
newnode->cnt = 1;
newnode->left = newnode->right = NULL;
return newnode;
}
// Function to add a node
// to the Binary Tree in
// level order
node* addinlvlorder(node* root, char data)
{
if (root == NULL) {
return add(data);
}
// Use the queue data structure
// for level order insertion
// and push the root of tree to Queue
queue<node*> Q;
Q.push(root);
while (!Q.empty()) {
node* temp = Q.front();
Q.pop();
// If the character to be
// inserted is present,
// update the cnt
if (temp->data == data) {
temp->cnt++;
break;
}
// If the left child is
// empty add a new node
// as the left child
if (temp->left == NULL) {
temp->left = add(data);
break;
}
else {
// If the character is present
// as a left child, update the
// cnt and exit the loop
if (temp->left->data == data) {
temp->left->cnt++;
break;
}
// Add the left child to
// the queue for further
// processing
Q.push(temp->left);
}
// If the right child is empty,
// add a new node to the right
if (temp->right == NULL) {
temp->right = add(data);
break;
}
else {
// If the character is present
// as a right child, update the
// cnt and exit the loop
if (temp->right->data == data) {
temp->right->cnt++;
break;
}
// Add the right child to
// the queue for further
// processing
Q.push(temp->right);
}
}
return root;
}
// Function to print the
// level order traversal of
// the Binary Tree
void printlvlorder(node* root)
{
// Add the root to the queue
queue<node*> Q;
Q.push(root);
while (!Q.empty()) {
node* temp = Q.front();
// If the cnt of the character
// is more then one, display cnt
if (temp->cnt > 1) {
cout << temp->data << temp->cnt;
}
// If the cnt of character
// is one, display character only
else {
cout << temp->data;
}
Q.pop();
// Add the left child to
// the queue for further
// processing
if (temp->left != NULL) {
Q.push(temp->left);
}
// Add the right child to
// the queue for further
// processing
if (temp->right != NULL) {
Q.push(temp->right);
}
}
}
// Driver code
int main()
{
string s = "geeksforgeeks";
node* root = NULL;
// Add individual characters
// to the string one by one
// in level order
for (int i = 0; i < s.size(); i++) {
root = addinlvlorder(root, s[i]);
}
// Print the level order
// of the constructed
// binary tree
printlvlorder(root);
return 0;
}
Java
// Java implementation of
// the above approach
import java.util.*;
class GFG
{
// Node in the tree where
// data holds the character
// of the String and cnt
// holds the frequency
static class node
{
char data;
int cnt;
node left, right;
};
// Function to add a new
// node to the Binary Tree
static node add(char data)
{
// Create a new node and
// populate its data part,
// set cnt as 1 and left
// and right children as null
node newnode = new node();
newnode.data = data;
newnode.cnt = 1;
newnode.left = newnode.right = null;
return newnode;
}
// Function to add a node
// to the Binary Tree in
// level order
static node addinlvlorder(node root, char data)
{
if (root == null)
{
return add(data);
}
// Use the queue data structure
// for level order insertion
// and push the root of tree to Queue
Queue<node> Q = new LinkedList<node>();
Q.add(root);
while (!Q.isEmpty())
{
node temp = Q.peek();
Q.remove();
// If the character to be
// inserted is present,
// update the cnt
if (temp.data == data)
{
temp.cnt++;
break;
}
// If the left child is
// empty add a new node
// as the left child
if (temp.left == null)
{
temp.left = add(data);
break;
}
else
{
// If the character is present
// as a left child, update the
// cnt and exit the loop
if (temp.left.data == data)
{
temp.left.cnt++;
break;
}
// Add the left child to
// the queue for further
// processing
Q.add(temp.left);
}
// If the right child is empty,
// add a new node to the right
if (temp.right == null)
{
temp.right = add(data);
break;
}
else
{
// If the character is present
// as a right child, update the
// cnt and exit the loop
if (temp.right.data == data)
{
temp.right.cnt++;
break;
}
// Add the right child to
// the queue for further
// processing
Q.add(temp.right);
}
}
return root;
}
// Function to print the
// level order traversal of
// the Binary Tree
static void printlvlorder(node root)
{
// Add the root to the queue
Queue<node> Q = new LinkedList<node>();
Q.add(root);
while (!Q.isEmpty())
{
node temp = Q.peek();
// If the cnt of the character
// is more then one, display cnt
if (temp.cnt > 1)
{
System.out.print((temp.data +""+ temp.cnt));
}
// If the cnt of character
// is one, display character only
else
{
System.out.print((char)temp.data);
}
Q.remove();
// Add the left child to
// the queue for further
// processing
if (temp.left != null)
{
Q.add(temp.left);
}
// Add the right child to
// the queue for further
// processing
if (temp.right != null)
{
Q.add(temp.right);
}
}
}
// Driver code
public static void main(String[] args)
{
String s = "geeksforgeeks";
node root = null;
// Add individual characters
// to the String one by one
// in level order
for (int i = 0; i < s.length(); i++)
{
root = addinlvlorder(root, s.charAt(i));
}
// Print the level order
// of the constructed
// binary tree
printlvlorder(root);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python implementation of
# the above approach
# Node in the tree where
# data holds the character
# of the String and cnt
# holds the frequency
class node:
def __init__(self):
self.data = ''
self.cnt = 0
self.left = None
self.right = None
# Function to add a new
# node to the Binary Tree
def add(data):
# Create a new node and
# populate its data part,
# set cnt as 1 and left
# and right children as None
newnode = node()
newnode.data = data
newnode.cnt = 1
newnode.left = newnode.right = None
return newnode
# Function to add a node
# to the Binary Tree in
# level order
def addinlvlorder(root, data):
if (root == None):
return add(data)
# Use the queue data structure
# for level order insertion
# and push the root of tree to Queue
Q = []
Q.append(root)
while (len(Q) != 0):
temp = Q[0]
Q = Q[1:]
# If the character to be
# inserted is present,
# update the cnt
if (temp.data == data):
temp.cnt += 1
break
# If the left child is
# empty add a new node
# as the left child
if (temp.left == None):
temp.left = add(data)
break
else:
# If the character is present
# as a left child, update the
# cnt and exit the loop
if (temp.left.data == data):
temp.left.cnt += 1
break
# push the left child to
# the queue for further
# processing
Q.append(temp.left)
# If the right child is empty,
# add a new node to the right
if (temp.right == None):
temp.right = add(data)
break
else:
# If the character is present
# as a right child, update the
# cnt and exit the loop
if (temp.right.data == data):
temp.right.cnt += 1
break
# push the right child to
# the queue for further
# processing
Q.append(temp.right)
return root
# Function to print the
# level order traversal of
# the Binary Tree
def printlvlorder(root):
# push the root to the queue
Q = []
Q.append(root)
while (len(Q) != 0):
temp = Q[0]
# If the cnt of the character
# is more then one, display cnt
if (temp.cnt > 1):
print(f"{temp.data}{temp.cnt}",end="")
# If the cnt of character
# is one, display character only
else:
print(temp.data,end="")
Q = Q[1:]
# push the left child to
# the queue for further
# processing
if (temp.left != None):
Q.append(temp.left)
# push the right child to
# the queue for further
# processing
if (temp.right != None):
Q.append(temp.right)
# Driver code
s = "geeksforgeeks"
root = None
# push individual characters
# to the String one by one
# in level order
for i in range(len(s)):
root = addinlvlorder(root, s[i])
# Print the level order
# of the constructed
# binary tree
printlvlorder(root)
# This code is contributed by shinjanpatra
C#
// C# implementation of
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Node in the tree where
// data holds the character
// of the String and cnt
// holds the frequency
public class node
{
public char data;
public int cnt;
public node left, right;
};
// Function to add a new
// node to the Binary Tree
static node add(char data)
{
// Create a new node and
// populate its data part,
// set cnt as 1 and left
// and right children as null
node newnode = new node();
newnode.data = data;
newnode.cnt = 1;
newnode.left = newnode.right = null;
return newnode;
}
// Function to add a node
// to the Binary Tree in
// level order
static node addinlvlorder(node root, char data)
{
if (root == null)
{
return add(data);
}
// Use the queue data structure
// for level order insertion
// and push the root of tree to Queue
List<node> Q = new List<node>();
Q.Add(root);
while (Q.Count != 0)
{
node temp = Q[0];
Q.RemoveAt(0);
// If the character to be
// inserted is present,
// update the cnt
if (temp.data == data)
{
temp.cnt++;
break;
}
// If the left child is
// empty add a new node
// as the left child
if (temp.left == null)
{
temp.left = add(data);
break;
}
else
{
// If the character is present
// as a left child, update the
// cnt and exit the loop
if (temp.left.data == data)
{
temp.left.cnt++;
break;
}
// Add the left child to
// the queue for further
// processing
Q.Add(temp.left);
}
// If the right child is empty,
// add a new node to the right
if (temp.right == null)
{
temp.right = add(data);
break;
}
else
{
// If the character is present
// as a right child, update the
// cnt and exit the loop
if (temp.right.data == data)
{
temp.right.cnt++;
break;
}
// Add the right child to
// the queue for further
// processing
Q.Add(temp.right);
}
}
return root;
}
// Function to print the
// level order traversal of
// the Binary Tree
static void printlvlorder(node root)
{
// Add the root to the queue
List<node> Q = new List<node>();
Q.Add(root);
while (Q.Count != 0)
{
node temp = Q[0];
// If the cnt of the character
// is more then one, display cnt
if (temp.cnt > 1)
{
Console.Write((temp.data +""+ temp.cnt));
}
// If the cnt of character
// is one, display character only
else
{
Console.Write((char)temp.data);
}
Q.RemoveAt(0);
// Add the left child to
// the queue for further
// processing
if (temp.left != null)
{
Q.Add(temp.left);
}
// Add the right child to
// the queue for further
// processing
if (temp.right != null)
{
Q.Add(temp.right);
}
}
}
// Driver code
public static void Main(String[] args)
{
String s = "geeksforgeeks";
node root = null;
// Add individual characters
// to the String one by one
// in level order
for (int i = 0; i < s.Length; i++)
{
root = addinlvlorder(root, s[i]);
}
// Print the level order
// of the constructed
// binary tree
printlvlorder(root);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of
// the above approach
// Node in the tree where
// data holds the character
// of the String and cnt
// holds the frequency
class node
{
constructor()
{
this.data = '';
this.cnt = 0;
this.left = null;
this.right = null;
}
};
// Function to add a new
// node to the Binary Tree
function add(data)
{
// Create a new node and
// populate its data part,
// set cnt as 1 and left
// and right children as null
var newnode = new node();
newnode.data = data;
newnode.cnt = 1;
newnode.left = newnode.right = null;
return newnode;
}
// Function to add a node
// to the Binary Tree in
// level order
function addinlvlorder(root, data)
{
if (root == null)
{
return add(data);
}
// Use the queue data structure
// for level order insertion
// and push the root of tree to Queue
var Q = [];
Q.push(root);
while (Q.length != 0)
{
var temp = Q[0];
Q.shift();
// If the character to be
// inserted is present,
// update the cnt
if (temp.data == data)
{
temp.cnt++;
break;
}
// If the left child is
// empty add a new node
// as the left child
if (temp.left == null)
{
temp.left = add(data);
break;
}
else
{
// If the character is present
// as a left child, update the
// cnt and exit the loop
if (temp.left.data == data)
{
temp.left.cnt++;
break;
}
// push the left child to
// the queue for further
// processing
Q.push(temp.left);
}
// If the right child is empty,
// add a new node to the right
if (temp.right == null)
{
temp.right = add(data);
break;
}
else
{
// If the character is present
// as a right child, update the
// cnt and exit the loop
if (temp.right.data == data)
{
temp.right.cnt++;
break;
}
// push the right child to
// the queue for further
// processing
Q.push(temp.right);
}
}
return root;
}
// Function to print the
// level order traversal of
// the Binary Tree
function printlvlorder(root)
{
// push the root to the queue
var Q = [];
Q.push(root);
while (Q.length != 0)
{
var temp = Q[0];
// If the cnt of the character
// is more then one, display cnt
if (temp.cnt > 1)
{
document.write((temp.data +""+ temp.cnt));
}
// If the cnt of character
// is one, display character only
else
{
document.write(temp.data);
}
Q.shift();
// push the left child to
// the queue for further
// processing
if (temp.left != null)
{
Q.push(temp.left);
}
// push the right child to
// the queue for further
// processing
if (temp.right != null)
{
Q.push(temp.right);
}
}
}
// Driver code
var s = "geeksforgeeks";
var root = null;
// push individual characters
// to the String one by one
// in level order
for(var i = 0; i < s.length; i++)
{
root = addinlvlorder(root, s[i]);
}
// Print the level order
// of the constructed
// binary tree
printlvlorder(root);
</script>
Producción:
g2e4k2s2for
Publicación traducida automáticamente
Artículo escrito por code_freak y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA