Dada una array que representa un árbol de tal manera que los índices de la array son valores en los Nodes del árbol y los valores de la array dan el Node principal de ese índice (o Node) en particular. El valor del índice del Node raíz siempre sería -1 ya que no hay un padre para la raíz. Construya la representación vinculada estándar de un árbol binario dado a partir de esta representación dada. Consulte para comprender cómo construir un árbol binario a partir de una representación de array principal dada .
Formas de representar:
Los árboles se pueden representar de dos maneras, como se indica a continuación:
- Representación de Node Dinámico (Representación Vinculada).
- Representación de array (Representación secuencial).
Ahora, vamos a hablar de la representación secuencial de los árboles. Para representar un árbol usando una array, la numeración de los Nodes puede comenzar desde 0–(n-1) o 1– n, considere la siguiente ilustración de la siguiente manera:
Ilustración:
A(0)
/ \
B(1) C(2)
/ \ \
D(3) E(4) F(6)
OR,
A(1)
/ \
B(2) C(3)
/ \ \
D(4) E(5) F(7)
Procedimiento:
Nota: padre, hijo_izquierdo y hijo_derecho son los valores de los índices de la array.
Caso 1: (0—n-1)
if (say)father=p; then left_son=(2*p)+1; and right_son=(2*p)+2;
Caso 2: 1—n
if (say)father=p; then left_son=(2*p); and right_son=(2*p)+1;
Implementación:
Ejemplos
C++
// C++ implementation of tree using array
// numbering starting from 0 to n-1.
#include<bits/stdc++.h>
using namespace std;
char tree[10];
int root(char key) {
if (tree[0] != '\0')
cout << "Tree already had root";
else
tree[0] = key;
return 0;
}
int set_left(char key, int parent) {
if (tree[parent] == '\0')
cout << "\nCan't set child at "
<< (parent * 2) + 1
<< " , no parent found";
else
tree[(parent * 2) + 1] = key;
return 0;
}
int set_right(char key, int parent) {
if (tree[parent] == '\0')
cout << "\nCan't set child at "
<< (parent * 2) + 2
<< " , no parent found";
else
tree[(parent * 2) + 2] = key;
return 0;
}
int print_tree() {
cout << "\n";
for (int i = 0; i < 10; i++) {
if (tree[i] != '\0')
cout << tree[i];
else
cout << "-";
}
return 0;
}
// Driver Code
int main() {
root('A');
set_left('B',0);
set_right('C', 0);
set_left('D', 1);
set_right('E', 1);
set_right('F', 2);
print_tree();
return 0;
}
Java
// JAVA implementation of tree using array
// numbering starting from 0 to n-1.
// Importing required classes
import java.io.*;
import java.lang.*;
import java.util.*;
// Class 1
// Helper class (Node class)
class Tree {
// Main driver method
public static void main(String[] args)
{
// Creating object of class 2 inside main() method
Array_imp obj = new Array_imp();
// Setting root node
obj.Root("A");
// obj.set_Left("B", 0);
obj.set_Right("C", 0);
obj.set_Left("D", 1);
obj.set_Right("E", 1);
obj.set_Left("F", 2);
obj.print_Tree();
}
}
// Class 2
// Helper class
class Array_imp {
// Member variables of this class
static int root = 0;
static String[] str = new String[10];
// Method 1
// Creating root node
public void Root(String key) { str[0] = key; }
// Method 2
// Creating left son of root
public void set_Left(String key, int root)
{
int t = (root * 2) + 1;
if (str[root] == null) {
System.out.printf(
"Can't set child at %d, no parent found\n",
t);
}
else {
str[t] = key;
}
}
// Method 3
// Creating right son of root
public void set_Right(String key, int root)
{
int t = (root * 2) + 2;
if (str[root] == null) {
System.out.printf(
"Can't set child at %d, no parent found\n",
t);
}
else {
str[t] = key;
}
}
// Method 4
// To print our tree
public void print_Tree()
{
// Iterating using for loop
for (int i = 0; i < 10; i++) {
if (str[i] != null)
System.out.print(str[i]);
else
System.out.print("-");
}
}
}
C#
// C# implementation of tree using array
// numbering starting from 0 to n-1.
using System;
public class Tree {
public static void Main(String[] args)
{
Array_imp obj = new Array_imp();
obj.Root("A");
// obj.set_Left("B", 0);
obj.set_Right("C", 0);
obj.set_Left("D", 1);
obj.set_Right("E", 1);
obj.set_Left("F", 2);
obj.print_Tree();
}
}
class Array_imp {
static int root = 0;
static String[] str = new String[10];
/*create root*/
public void Root(String key)
{
str[0] = key;
}
/*create left son of root*/
public void set_Left(String key, int root)
{
int t = (root * 2) + 1;
if (str[root] == null) {
Console.Write("Can't set child at {0}, no parent found\n", t);
}
else {
str[t] = key;
}
}
/*create right son of root*/
public void set_Right(String key, int root)
{
int t = (root * 2) + 2;
if (str[root] == null) {
Console.Write("Can't set child at {0}, no parent found\n", t);
}
else {
str[t] = key;
}
}
public void print_Tree()
{
for (int i = 0; i < 10; i++) {
if (str[i] != null)
Console.Write(str[i]);
else
Console.Write("-");
}
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 implementation of tree using array
# numbering starting from 0 to n-1.
tree = [None] * 10
def root(key):
if tree[0] != None:
print("Tree already had root")
else:
tree[0] = key
def set_left(key, parent):
if tree[parent] == None:
print("Can't set child at", (parent * 2) + 1, ", no parent found")
else:
tree[(parent * 2) + 1] = key
def set_right(key, parent):
if tree[parent] == None:
print("Can't set child at", (parent * 2) + 2, ", no parent found")
else:
tree[(parent * 2) + 2] = key
def print_tree():
for i in range(10):
if tree[i] != None:
print(tree[i], end="")
else:
print("-", end="")
print()
# Driver Code
root('A')
set_right('C', 0)
set_left('D', 1)
set_right('E', 1)
set_right('F', 2)
print_tree()
# This code is contributed by Gaurav Kumar Tailor
Can't set child at 3 , no parent found Can't set child at 4 , no parent found A-C---F---
Complejidad de tiempo : O (log n) desde que se usó el montón para crear un árbol binario
Complejidad espacial : O (n) para array
Publicación traducida automáticamente
Artículo escrito por sanjal_katiyar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA