[RESOLVIDO] Arvore Binaria - Balanceamento - Mediana Recursiva de Array

Boa noite amigos,
Estou com uma duvida que considero basica, mas nao estou conseguindo solucionar

preciso pegar de forma recursiva a mediana de um array.

Exemplo: um array de 15 posicoes: 0 a 14 :

https://lh4.googleusercontent.com/6rGqM4UbVZlqL7se7bLIelopXFoY8ULJPeUJ_INIM21hjO13Z8rbEmMbgV9sKPtil4fsMVVWnOecVurfJ16zNdvUwDHdmSnOwmU=w1024
Primeira mediana: 7
fim (14) - inicio (0) / 2

Ate ai tudo certo, entao preciso pegar de forma recursiva m1 e m2:
m1 = mediana(0,6) = 3
m2 = mediana(8,14) = 11

e assim sucessivamente m3 = mediana(0,m1) e m4 = mediana(4,6)
m3 deveria retornar = 1 e m4 deveria retornar = 5
assim m5 = 9 e m6 = 13

e prosseguir ate pegar todos os numeros…
A sequencia de retorno do array 0-14 ficaria assim:
7,3,11,1,5,9,13,0,2,4,6,8,10,12,14

Fiz o seguinte codigo mas nao esta funcionando:

public void balanceamento02Mediana(int inicio, int fim) throws Exception{
        /* Tentando uma outra abordagem de mediana conforem explciacao de lucca*/
        int medianaFixa = 0;
        int mediana = 0;
        if(fim-inicio &gt; 1){
            if((fim-inicio)%2 == 0){
                mediana = (fim-inicio) / 2;
                medianaFixa = arrayInPreOrdem.length/2;
            }else{
                mediana = ((fim-inicio-1) / 2);
                medianaFixa = (arrayInPreOrdem.length-1)/2;
            } // if else
            System.out.println(inicio + mediana);
            inserirArvore(arrayInPreOrdem[inicio + mediana][0],arrayInPreOrdem[inicio + mediana][1]);
            
            balanceamento02Mediana(mediana-1, fim);
            balanceamento02Mediana(inicio, mediana-1);            
                        
        } // if        
                
    } // mtd balanceamento02Mediana

Outra forma de explicar o problema

Seguinte, estou tentando fazer balanceamento de uma arvore binaria …

Percorrer a arvore binaria em Inordem e salvar a sequencia num array (arrayInPreOrdem).

Depois montar a arvore binaria balanceada pegando o meio de cada parte :

Um exemplo de inordem num array de 15 itens.

para uma arvore balanceada, deveria pegar os itens na seguinte ordem do array arrayInPreOrdem[i] :
7,3,11,1,5,9,13,0,2,4,6,8,10,12,14

0 - 14 = 7

0 - 7 = 3
8 - 14 = 11

0 - 2 = 1
4 - 6 = 5
8 - 10 = 9
12 - 14 = 13

depois 0, 2 , 4 , 6 , 8 , 10 , 12 , 14

Assim a arvore estaria balanceada.

Então por isso pegar a mediana do array de 0-14. Que seria a sequencia acima.

O problema é que meu codigo soh faz a primeira parte
retorna 7, 3, 1, ou seja soh faz a mediana para baixo, quando vai fazer a parte de cima, ja alterou o tamanha da primeira mediana (que deveria ser 7, por isso tentei mediana fixa) para fazer a segunda parte (8-14).
Por isso inverti para testar, mas so inverte a ordem, rodando somente a metade do codigo correto.
7, 11, 13.

Abracos

Obrigado pela atenção

A construção da arvore ja esta funcionando e consegui arrumar meu codigo.
Ufa, foram alguns dias em cima disso. E o erro era bem bobo.
Obrigado pela ajuda

public void balanceamentoArvore() throws Exception{
		inicioCaminhadaarrayInOrdem(this.raiz);
		this.raiz = null;
		balanceamento02incioMediana(0, arrayInPreOrdem.length-1);
	} // mtd balanceamentoArvore

	public void balanceamento02incioMediana(int inicio, int fim) throws Exception{
		/* Tentando uma outra abordagem de mediana conforme explicacao de lucca*/
		int mediana = 0;
		if(fim-inicio &gt;= 0){
			if((fim-inicio)%2 == 0){
				mediana = (fim-inicio) / 2 + inicio;
			}else{
				mediana = ((fim-inicio-1) / 2 + inicio);
			} // if else
			
			System.out.println("M : " + (mediana));
			inserirArvore(arrayInPreOrdem[mediana][0],arrayInPreOrdem[mediana][1]);
			balanceamento02incioMediana(inicio, mediana-1);	
			balanceamento02incioMediana(mediana+1, fim);
		} // if		fim-inicio &gt; 1
								
	} // mtd balanceamento02incioMediana

1 Resposta

Topicos relacionados