Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C++
node* rightrotate(struct node *root)
{
    node *node1;
    node1=root->left;
    root->left=node1->right;
    node1->right=root;
    root->h = max(h(root->left), h(root->right));
    node1->h = max(h(node1->left), h(node1->right));
    return node1;
}
node* leftrotate(struct node *root)
{
 
    node *node1;
    node1=root->right;
    root->right =node1->left;
    node1->left =root;
    root->h = max(h(root->left), h(root->right));
    node1->h = max(h(node1->left), h(node1->right));
 
    return node1;
 
}
 

 

void preorder(struct node *root)
{
    if(root !=NULL)
    {
        cout<<root->key<<endl;
        preorder(root->right);
        preorder(root->left);
    }
 

 

example:
 
when i get 10 20 30 40 50 25
 
when i use preorder function
 
: 30 20 10 20 40 50
Posted 29-Jan-13 8:51am
Comments
Andreas Gieriet at 29-Jan-13 14:56pm
   
Some code is missing.
Did you run the debugger? If not, go an do it.
Andi
mahla.r_1993 at 29-Jan-13 14:58pm
   
#include "stdafx.h"
#include
using namespace std ;
 
struct node
{
int key ;
int h;
node *left;
node *root;
node *right;
};
 

 

 
int h(struct node* x)
{
if (x == NULL)
return 0;
return x->h;
}
int balanceavl(struct node *n)
{
if (n == NULL)
return 0;
return (h(n->left) , h(n->right));
 

}
 

 

 
node* rightrotate(struct node *root)
{
node *node1;
node1=root->left;
root->left=node1->right;
node1->right=root;
root->h = max(h(root->left), h(root->right));
node1->h = max(h(node1->left), h(node1->right));
return node1;
}
node* leftrotate(struct node *root)
{
 
node *node1;
node1=root->right;
root->right =node1->left;
node1->left =root;
root->h = max(h(root->left), h(root->right));
node1->h = max(h(node1->left), h(node1->right));

return node1;
 
}
 

 

 
void inorder(struct node *root)
{
if(root !=NULL)
{
inorder(root->left);
cout<<root->key<<endl;
inorder(root->right);
}
}
 
void preorder(struct node *root)
{
if(root !=NULL)
{
cout<<root->key<<endl;
preorder(root->right);
preorder(root->left);
}
 

}
 

 
struct node *remove(struct node *root, int key)
{
node* successor(struct node *x);
 
struct node *remove_node;
if (root == NULL)
{
return root;
}
 
if ( key < root->key)
{
root->left = remove(root->left, key);
 
}
else if ( key > root->key)
{
root->right = remove(root->right,key);
 
}
else {
 
if ((root->left == NULL) && (root->right != NULL)){
remove_node = root->right;
*root = *remove_node;
free(remove_node); // this is for free-ing the memory
 
} else if ((root->right == NULL) && (root->left != NULL)){
remove_node = root->left;
*root = *remove_node;
free(remove_node);
 
} else if ((root->right == NULL) && (root->left == NULL)){
remove_node = root;
root = NULL;
 
} //else {
 
// remove_node = successor(root);
// root->key = remove_node->key;
// root->right = remove(root->right, remove_node->key);
// }
}
 
if (root == NULL) {
return root;
//lr
if (balanceavl(root) == 2){
if (balanceavl(root->left) == -1) {
root->left = leftrotate(root->left);
return rightrotate(root);
//ll
} else if (balanceavl(root->left) == 1) {
return rightrotate(root);
}
}
//rr
if (balanceavl(root) == -2) {
if (balanceavl(root->right) == -1) {
return leftrotate(root);
}
 

//rl
else if (balanceavl(root->right) == 1) {
root->right = rightrotate(root->right);
return leftrotate(root);
}
}
}
 
return root;
}
struct node* newNode(int key)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->h = 1; // new node is initially added at leaf
return(node);
}
struct node* insert(struct node* root, int key)
{
/* 1. Perform the normal BST rotation */
if (root == NULL)
return(newNode(key));

if (key < root->key)
root->left = insert(root->left, key);
else
root->right = insert(root->right, key);

/* 2. Update height of this ancestor node */
root->h= max(h(root->left), h(root->right)) + 1;

/* 3. Get the balance factor of this ancestor node to check whether
this node became unbalanced */
int balance = balanceavl(root);

// If this node becomes unbalanced, then there are 4 cases

if (root == NULL) {
return root;
//lr
if (balanceavl(root) == 2){
if (balanceavl(root->left) == -1) {
root->left = leftrotate(root->left);
return rightrotate(root);
//ll
} else if (balanceavl(root->left) == 1) {
return rightrotate(root);
}
}
//rr
if (balanceavl(root) == -2) {
mahla.r_1993 at 29-Jan-13 14:59pm
   
it is my code i dont understand what is wrong in this code ?? i can not get a preorder fot avl tree:(
Andreas Gieriet at 29-Jan-13 15:02pm
   
Did you run the debugger?
Andi
mahla.r_1993 at 29-Jan-13 15:07pm
   
yes i dont understand
plz help me :(
Andreas Gieriet at 29-Jan-13 15:27pm
   
What "yes"?
So you did run the debugger and stepped through the code?
 
If you don't know running a program in the debugger you better learn this first. It's not magic: you need to set a breakpoint at the location you want the program to stop in order to do single stepping after that and to look at the variables.
Check your debugger documentation on how to set a breakpoint, run the program to the breakpoint, do single step, look at variable contents, finally continue and/or stop debugging.
 
If you can not spend the time to learn the debugger well enough to debug your programs, you are screwed up. That's basic.
 
If this is your code, you should be familiar with it to debug.
 
If this is homework assignment, please lable it as such.
 
Cheers
Andi
 
BTW: This is from the style plain C code (not C++ code), except for the cin/cout io.
mahla.r_1993 at 29-Jan-13 15:57pm
   
i know how to use debugger but i can not find my problem :(
 
help !!!!!!
Andreas Gieriet at 29-Jan-13 17:41pm
   
Some comments:
- The balance functions returns an weird value:
return (h(...), h(...));.
This is the comma operator - by intension?
- What is your main function? Where do these numbers in your original questions come from?
- newNode is a mess, remove is a mess too
- Why do you use malloc in C++ - this is crap, sorry.
 
I'm tempted to give up with such a code base and start from scratch: What do you want to achieve? What is the program supposed to do?
 
Andi
jibesh at 29-Jan-13 20:22pm
   
Yes as Andi said in his last comment , you only said you are having problem but what is the problem? is it the expected output 10,20,30,40 is not getting the out when you call preorder? at which point you are invoking the preorder method?
 
by looking at the preorder method its obvious that it prints left and right child of the rootNode recursively so the given out put looks ok to me.
 
i.e
30
10 20

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
0 OriginalGriff 385
1 Sergey Alexandrovich Kryukov 195
2 Prakriti Goyal 177
3 jlopez788 134
4 Kruti Joshi 117
0 OriginalGriff 6,742
1 Sergey Alexandrovich Kryukov 5,479
2 Maciej Los 3,474
3 Peter Leow 3,313
4 DamithSL 2,505


Advertise | Privacy | Mobile
Web04 | 2.8.140721.1 | Last Updated 29 Jan 2013
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100