# How do I find and show the "uncle" of an element And How do I show the depth of a cer

This is a discussion on How do I find and show the "uncle" of an element And How do I show the depth of a cer within the C Programming forums, part of the General Programming Boards category; title: How do I find and show the "uncle" of an element And How do I show the depth of ...

1. ## 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;
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("________________\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: ");

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: ");
//function here
break;
}
case 7:{
printf("\nDigite o codigo: ");
//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
}
}
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
{
if (pai == NULL) {
return NULL;
}

pai->depth++;

}```

Once you add this parent link, it will be much easier to find the height of the node. I think you can figure this out yourself.

Note: You can do this without a link back to the father node, but the code is much more complicated, and involves traversing the tree.

3. Code:
```int depthfind( tree *t, int d, int tofind )
{
int rval = -1
if( t )
{
if( t->value == tofind )
rval = d;
if( rval == -1 )
rval = depthfind( t->left, d+1, tofind );
if( rval == -1 )
rval = depthfind( t->right, d+1, tofind );
}
return rval;
}
...
depth = depthfind( firstnode, 0, 3 );```

edit - too slow

Quzah.

quzah: ok, and to print the depth?
example: 4,5,6,1,2

thanks

arvoreperfume.c:
Code:
```int depthfind(Perfume_ptr pai, int c, int tofind )
{
int rval = -1;
if( pai )
{
if( pai->cod == tofind )
rval = c;
if( rval == -1 )
rval = depthfind( pai->esq, c+1, tofind );
if( rval == -1 )
rval = depthfind( pai->dir, c+1, tofind );
}
return rval;
printf("caminho:", rval);
}```

arvoreperfume.h:
Code:
`int depthfind(Perfume_ptr pai, int c, int tofind );`
arvoreperfumeMain.c:
Code:
```int main()...
int depth;
...

case 7:{
printf("\nDigite o codigo: ");
depth = depthfind(pai, 0, 3 );
break;
}```

5. You aren't even trying to understand what I wrote, are you?
Code:
```    return rval;
printf("caminho:", rval);
}```
That line is never reachable.
Code:
```                    printf("\nDigite o codigo: ");
depth = depthfind(pai, 0, 3 );
break;```
I'm not sure what entrada is, but you probably mean to be passing it as one of those arguments (the third one probably).

Quzah.

6. sorry!
Code:
```printf("caminho:", rval);
return rval;```
entrada is the value that the user enters to show the depth

7. still does not work =/

8. Don't bump your own thread, that is the quickest way to get ignored and have your thread locked. A great tutorial about everything you are looking to do can be found here. Read through that and then take a look at your code again. This will present you the information you have already been given in a more detailed manner. Take a look at it, understand it, and then work on your code.

9. Thank you and sorry I'll read

10. anduril462:
I tried to do as you said but did not work.

Look:

arvore.h:
Code:
```struct PERFUME
{
struct PERFUME *esq;
struct PERFUME *dir;
struct PERFUME *pai;    int cod;
char nome[30];
float preco;
int altura;
};```
arvore.c:
Code:
```Perfume_ptr
RotacaoSimplesEsquerda(Perfume_ptr K2)
{
Perfume_ptr K1, K3;

K1 = K2->esq;

K3 = K1->pai;
K1->pai = K2->pai;
K2->pai = K3;
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;  /*Nova raiz*/
}

Perfume_ptr
RotacaoSimplesDireita(Perfume_ptr K1)
{
Perfume_ptr K2, K3;

K2 = K1->dir;

K3 = K2->pai;
K2->pai = K1->pai;
K1->pai = K3;
K1->dir = K2->esq;
K2->esq = K1;

K1->altura = Max( altura(K1->esq), altura(K1->dir)) + 1;
K2->altura = Max( altura(K2->dir), K1->altura) + 1;

return K2;  /*Nova raiz*/
}```

11. What are you trying to do?
Code:
```Perfume_ptr
RotacaoSimplesEsquerda(Perfume_ptr K2)
{
Perfume_ptr K1, K3;

K1 = K2->esq;

K3 = K1->pai;
K1->pai = K2->pai;
K2->pai = K3;```
If that is NULL, then this crashes your program.

Quzah.

12. Some code comments would help you explain what you're doing, and if you make them in English then I can see what you're doing too, since I don't speak Portuguese . Those look like rotate functions. Just looking at Esquerda, you're improperly setting K3 (it should be set to K2->pai), and K2->pai should be K1, not K3. Also, I think you're incorrectly using K2 in your K1->altura statement. Lastly, you need to change K3's child pointer to point to K1. To do this, you need to know if K2 was the left or right child of K3. You probably have similar issues with your Direita function.

I recommend you read up on tree rotation, and draw some diagrams on paper with nodes and pointer arrows. Make sure your diagrams include one generation above where you're rotating (parents), and two generations below (children and grandchildren). Then write out the steps in plain Portuguese, and lastly translate that to code.

EDIT: And like Quzah said, check for NULL pointers. Not just the one he pointed out, but everywhere it could be a problem.

13. These questions that you have with AVL trees are all answered with this tutorial. I am more than positive you will be able to see what is presented there and compare that to your implementation.

14. ﻿﻿Hello, I tried to translate into English what I'm trying to do the program, if they can help me get him packing to go I would be grateful.

* do not speak English, I'm using a translator gloogle
Code:
```       /* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */
Perfume_ptr
RotacaoSimplesEsquerda(Perfume_ptr K2)
{
Perfume_ptr K1, K3;
K1 = K2->esq;

K3 = K2->pai;
K1->pai = K2->pai;
K2->pai = K3;

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;  /*Nova raiz*/ new root
}

/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child*/
/* Update heights, then return new root */
Perfume_ptr
RotacaoSimplesDireita(Perfume_ptr K1)
{
Perfume_ptr K2, K3;
K2 = K1->dir;

K3 = K2->pai;
K2->pai = K1->pai;
K1->pai = K3;

K1->dir = K2->esq;
K2->esq = K1;
K1->altura = Max( altura(K1->esq), altura(K1->dir)) + 1;
K2->altura = Max( altura(K2->dir), K1->altura) + 1;
return K2;  /*Nova raiz*/  new root
}

/* This function can be called only if K3 has a left */
/* child and K3's left child has a right child */
/* Do the left-right double rotation */
/* Update heights, then return new root */
Perfume_ptr
RotacaoDuplaEsquerda(Perfume_ptr K3)
{
/*Rotaciona entre K1 e K2*/
/* Rotate between K1 and K2 */
K3->esq = RotacaoSimplesDireita(K3->esq);
/*Rotaciona entre K3 e K2*/
/* Rotate between K3 and K2 */

return RotacaoSimplesEsquerda(K3);
}

/* This function can be called only if K1 has a right */
/* child and K1's right child has a left child */
/* Do the right-left double rotation */
/* Update heights, then return new root */
Perfume_ptr
{
/*Rotaciona entre K3 e K2*/
/* Rotate between K3 and K2 */
K1->dir = RotacaoSimplesEsquerda(K1->dir);
/*Rotaciona entre K1 e K2*/
/* Rotate between K1 and K2 */
return RotacaoSimplesDireita(K1);
}```

15. Your rotate functions are still incomplete. If you look at the attached diagram, the node, parent, child and grandchild all have pointers to be adjusted. All in all, you need to change 6 pointers, but your code is only changing 4.

Study the attached diagram, paying attention to how the pointers (arrows) between nodes change. node is the one passed into your function. parent, child and grandchild are local variables. Set them up first, then make the following 6 changes. Hopefully it translates well.
1. Set parent's appropriate child link (left or right) to child
2. Set child's parent link to parent
3. Set node's parent link to child
4. Set child's right link to node
5. Set node's left link to grandchild (it's okay if grandchild is NULL)
6. If there is a grandchild, set grandchild's parent link to node
The left rotation is very similar, but a mirror image of this. Draw out a diagram for that, and figure out which instances of right and left pointers need to be swapped. For the double rotations, read the tutorial Andrew linked you to, and read the Wikipedia article on AVL trees and draw some diagrams to figure out which node is being rotated left and which is being rotated right, and in what order (I think your current implementation might be incorrect).