Tuesday 16 March 2021

How to convert a pyramid into a binary tree

Let's say I have a pyramid like this, but larger

     2
    4 9
   4 9 6
  7 7 8 9

and want to convert it into a binary tree, meaning we actually want to have a tree like this:

            2
       4         9
    4    9     9    6
   7 7  7  8  7  8  8 9

In a list format the result would be

2,4,9,4,9,9,6,7,7,7,8,7,8,8,9

I tried the following way, but it only works for trees of length 4. As an input I take a tree in a txt file.

def give_input(name):
    index = 0
    lis_of_listas = []
    f = open(name, "r")
    for x in f:
        x = x.replace(' ', '')
        x = x.replace('\n', '')
        lista = [int(i) for i in list(x)]
        if (index > 1 and index % 2 == 0):
            podlista = lista[1:-1]
            podpodlista = []
            for i in podlista:
                podpodlista.append(i)
                podpodlista.append(i)
            podpodlista.append(lista[-1])
            podpodlista.insert(0, lista[0])
        elif (index > 1 and index % 2 == 1):
            podlista = lista[1:-1]
            print(len(podlista)/2)
            podlista1 = podlista[0:int(len(podlista) / 2)]
            podlista2 = podlista[int(len(podlista) / 2):len(podlista)]
            podpodlista = []
            for i in podlista1:
                podpodlista.append(i)
                podpodlista.append(i)
            podpodlista.append(podlista1[-1])
            podpodlista.append(podlista2[0])
            for j in podlista2:
                podpodlista.append(j)
                podpodlista.append(j)
            podpodlista.append(lista[-1])
            podpodlista.insert(0, lista[0])
        if index <= 1:
            lis_of_listas.append(lista)
        else:
            lis_of_listas.append(podpodlista)
        index += 1
    return [item for sublist in lis_of_listas for item in sublist]


from How to convert a pyramid into a binary tree

No comments:

Post a Comment