Like Tree4Likes
  • 1 Post By quzah
  • 3 Post By anduril462

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. #1
    Registered User
    Join Date
    Jun 2011
    Posts
    7

    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);
    }

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    Add a struct PERFUME *pai; to your struct PERFUME. Make sure it always points to the current node's parent/father. Set it when you insert a node, and update it when you delete a node or rotate some part of your tree. When you do this, finding the uncle should be easy, since your uncle is just your father's brother, or your father's father's other child. Follow the parent link up to your grandfather, then down to the left child. If that's the same as your father, then your uncle must be your grandfather's right child. Otherwise, it must be your grandfather's left child.

    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. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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 );
    That looks about right.

    edit - too slow


    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    Registered User
    Join Date
    Jun 2011
    Posts
    7
    aduril462: thanks!

    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: ");
                        scanf ("%d*c", &entrada);
                        depth = depthfind(pai, 0, 3 );
                        break;
                       }

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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: ");
                        scanf ("%d*c", &entrada);
                        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.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    Jun 2011
    Posts
    7
    sorry!
    Code:
    printf("caminho:", rval);
    return rval;
    entrada is the value that the user enters to show the depth

  7. #7
    Registered User
    Join Date
    Jun 2011
    Posts
    7
    still does not work =/

  8. #8
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    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.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  9. #9
    Registered User
    Join Date
    Jun 2011
    Posts
    7
    Thank you and sorry I'll read

  10. #10
    Registered User
    Join Date
    Jun 2011
    Posts
    7
    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. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    anduril462 likes this.
    Hope is the first step on the road to disappointment.

  12. #12
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    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. #13
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    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.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  14. #14
    Registered User
    Join Date
    Jun 2011
    Posts
    7
    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
    RotacaoDuplaDireita(Perfume_ptr K1)
    {
                /*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);     
    }
    Last edited by saintshion; 06-30-2011 at 07:30 PM.

  15. #15
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    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.

    Name:  Single Rotate Right.jpg
Views: 995
Size:  58.8 KB

    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).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. IT policy disabling of "Show Desktop" button
    By hk_mp5kpdw in forum Tech Board
    Replies: 5
    Last Post: 04-16-2010, 01:13 PM
  2. "The man show"
    By RoD in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 08-18-2003, 12:07 PM
  3. "itoa"-"_itoa" , "inp"-"_inp", Why some functions have "
    By L.O.K. in forum Windows Programming
    Replies: 5
    Last Post: 12-08-2002, 08:25 AM
  4. "CWnd"-"HWnd","CBitmap"-"HBitmap"...., What is mean by "
    By L.O.K. in forum Windows Programming
    Replies: 2
    Last Post: 12-04-2002, 07:59 AM
  5. The "Show us your desktop!" Thread
    By face_master in forum A Brief History of Cprogramming.com
    Replies: 88
    Last Post: 11-16-2002, 07:55 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21