How do I find and show the "uncle" of an element And How do I show the depth of a cer
title: How do I find and show the "uncle" of an element
And How do I show the depth of a certain element of the tree
Hello, I have an avl tree and I'm trying to make two functions. The first is to show the "uncle" of an element and the second is to show the depth of an element, for example: element = 3
4
/ \
2 6
/ \ / \
1 3 5 7
showing 4, 2 and 3. Here is the code it's still unfinished
esq = left
dir = right
pai = root
altura = height
arvoreperfume.h:
Code:
#ifndef _Perfume_Arvore_H
#define _Perfume_Arvore_H
struct PERFUME
{
struct PERFUME *esq;
struct PERFUME *dir;
int cod;
char nome[30];
float preco;
int altura;
int depth;
};
typedef struct PERFUME Perfume;
typedef struct PERFUME * Perfume_ptr;
Perfume_ptr inserir(Perfume_ptr pai, int c, char n[30], float p);
#endif
arvoreperfumeMain.c:
Code:
#include "arvoreperfume.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
int main()
{
int existe;
Perfume_ptr pai=NULL;
int opcao = 1;
int entrada = 0;
char nomep[30];
int altura;
float precop;
char temp[30];
while(opcao!=0)
{
system("color Fc");//primeiro digito muda o fundo, o segundo muda a cor do texto
printf(" ________________________\n");
printf("|________________________|\n\n\n\n");
printf("=====>Menu<=====\n");
printf("________________\n");
printf("1-->Inserir\n");
printf("6-->Mostrar tio");
printf("7-->Mostrar caminho");
printf("0-->Sair \n");
printf("________________\n");
printf("Opcao:");
scanf("%d%*c", &opcao); //*c é pra não deixar um enter no buffer
system("cls");
switch(opcao)
{
case 1:{
printf("\nDigite o codigo: ");
scanf ("%d*c", &entrada);
printf("digite o nome: ");
scanf ("%s*c", &nomep);
printf("digite o preco: ");
scanf ("%f*c", &precop);
system("cls");
pai = inserir(pai, entrada, nomep, precop);
break;
}
case 6:{
printf("\nDigite o codigo: ");
scanf ("%d*c", &entrada);
//function here
break;
}
case 7:{
printf("\nDigite o codigo: ");
scanf ("%d*c", &entrada);
//function here
break;
}
}
}
getchar();
return 0;
}
arvoreperfume.c:
Code:
#include "arvoreperfume.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int altura (Perfume_ptr P) {
if(P == NULL)
return -1;
else
return P->altura;
}
int Max (int Lhs, int Rhs){
return Lhs > Rhs ? Lhs : Rhs;
}
Perfume_ptr RotacaoSimplesEsquerda( Perfume_ptr K2 ) {
Perfume_ptr K1;
K1 = K2->esq;
K2->esq = K1->dir;
K1->dir = K2;
K2->altura = Max( altura( K2->esq ), altura( K2->dir ) ) + 1;
K1->altura = Max( altura( K1->esq ), K2->altura ) + 1;
return K1; /* New root */
}
Perfume_ptr RotacaoSimplesDireita( Perfume_ptr K1 ) {
Perfume_ptr K2;
K2 = K1->dir;
K1->dir = K2->esq;
K2->esq = K1;
K1->altura = Max( altura( K1->esq ), altura( K1->dir ) ) + 1;
K2->altura = Max( altura( K2->esq ), K1->altura ) + 1;
return K2; /* New root */
}
Perfume_ptr RotacaoDuplaEsquerda( Perfume_ptr K3 ) {
/* Rotate between K1 and K2 */
K3->esq = RotacaoSimplesDireita( K3->esq );
/* Rotate between K3 and K2 */
return RotacaoSimplesEsquerda( K3 );
}
Perfume_ptr RotacaoDuplaDireita( Perfume_ptr K1 ) {
/* Rotate between K3 and K2 */
K1->dir = RotacaoSimplesEsquerda( K1->dir );
/* Rotate between K1 and K2 */
return RotacaoSimplesDireita( K1 );
}
Perfume_ptr inserir(Perfume_ptr pai, int c, char n[30], float p)
{
if (pai)
{
if (c < (pai) -> cod)
{
pai->esq = inserir(((pai)->esq), c, n, p);
if (altura (pai->esq) - altura (pai->dir) == 2)
if (c < (pai)->dir->cod)
(pai) = RotacaoSimplesEsquerda (pai);
else
(pai) = RotacaoDuplaEsquerda (pai);
}
else
if (c > (pai) -> cod)
{
pai->dir = inserir(((pai)->dir), c, n, p);
if (altura (pai->dir) - altura (pai->esq) == 2)
if (c > pai->dir->cod)
(pai) = RotacaoSimplesDireita (pai);
else
(pai) = RotacaoDuplaDireita (pai);
}
}
else
{
pai = (Perfume_ptr)malloc(sizeof (PERFUME));
if (pai)
{
(pai) -> cod = c;
strcpy((pai) -> nome, n);
(pai) -> preco = p;
(pai) -> esq = NULL;
(pai) -> dir = NULL;
}
else
{
printf("Nao foi possivel alocar memoria!\n");
}
}
(pai)->altura = Max (altura(pai->esq), altura(pai->dir)) +1;
return pai;
}
Perfume_ptr
grandparent(Perfume_ptr pai)
{
if ((pai != NULL) && (pai->cod != NULL))
return pai->cod->cod;
else
return NULL;
}
Perfume_ptr
uncle(Perfume_ptr pai)
{
Perfume_ptr g = grandparent(pai);
if (g == NULL)
return NULL;
if (pai->cod == g->esq)
return g->dir;
else
return g->esq;
}
Perfume_ptr
avl_tree_subtract_depth(Perfume_ptr pai)
{
if(pai == NULL) {
return NULL;
}
pai->depth--;
avl_tree_subtract_depth(pai->esq);
avl_tree_subtract_depth(pai->dir);
}
Perfume_ptr
avl_tree_add_depth(Perfume_ptr pai)
{
if (pai == NULL) {
return NULL;
}
pai->depth++;
avl_tree_add_depth(pai->esq);
avl_tree_add_depth(pai->dir);
}
