Thread: Comparision of binary trees, balance.

  1. #31
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    No, the return type should be struct tree *:
    Code:
    struct tree *DSWbalance(struct tree *root)
    {
        /* algorithm */
    
        return root;  // this is the "new" root, since rotations may alter the root of the tree
    }

  2. #32
    Registered User
    Join Date
    Jan 2012
    Posts
    29
    Ohhh god, I'm so stupid. I've never considered that function can be something else than void or int

    Although not everything is okey.

    Code:
    case 1:                system("cls");
                    printf("Enter a value: ");
                    scanf("%d", &value);                
                    if(insert(&headone, value)==1)
                    {
                        printf("Value exists! Press any key to continue.\n");
                        getchar();
                        getchar();
                    }
                    else
                    {
                        insert(&headtwo, value);
                        headtwo=DSWbalance(headtwo); //when this part is 'on' program doesn't give my errors, but it looks like algorithm is wrong, when I print a result of it I have only one element in a tree
                    }
                    break;
    If red part is off, and I put into my tree 5 values, ie 5, 4, 3, 2, 1, then I perform balancing I have error of access violation. I checked step-by-step what's going on inside of it. First part (creating a spine) looks okey. Not so sure of second part. Problem occurs when 'k' reaches 'i'.


    Code:
    struct tree *DSWbalance(struct tree *root){  
        struct tree *p;
        int nodecount;
        int i;
        
        for(p=root,nodecount=0;p!=0;p=p->right,++nodecount) //spine
            {
                while(rightrotate(&p)==1) { }
            }
        
        for(i=nodecount/2; i>0; i/=2 ) //balance
            {
                int k;
                for(p=root,k=0;k<i;++k,p=p->right)
                    leftrotate(&p);
            }
        return root;
        
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Converting From Binary Tree to Threaded Binary Trees
    By elton_fan in forum C Programming
    Replies: 15
    Last Post: 11-08-2007, 11:41 PM
  2. binary tree balance problem
    By overkill in forum C++ Programming
    Replies: 5
    Last Post: 08-17-2006, 05:52 AM
  3. Binary Trees MINI MAXING, probability trees
    By curlious in forum General AI Programming
    Replies: 3
    Last Post: 09-30-2005, 10:57 AM
  4. balance binary tree
    By xddxogm3 in forum C++ Programming
    Replies: 6
    Last Post: 12-07-2003, 05:33 PM
  5. traversing binary trees or partial trees
    By sballew in forum C Programming
    Replies: 4
    Last Post: 12-05-2001, 09:19 PM

Tags for this Thread