13,248,295 members (44,682 online)
Rate this:
See more:
```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 9:51am
Andreas Gieriet 29-Jan-13 14:56pm

Some code is missing.
Did you run the debugger? If not, go an do it.
Andi
mahla.r_1993 29-Jan-13 14:58pm

#include "stdafx.h"
#include<iostream>
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;

} 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 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 29-Jan-13 15:02pm

Did you run the debugger?
Andi
mahla.r_1993 29-Jan-13 15:07pm

yes i dont understand
plz help me :(
Andreas Gieriet 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 29-Jan-13 15:57pm

i know how to use debugger but i can not find my problem :(

help !!!!!!
Andreas Gieriet 29-Jan-13 17:41pm

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

Top Experts
Last 24hrsThis month
 Peter Leow 135 ppolymorphe 85 OriginalGriff 70 Andy Lanng 50 Bryian Tan 50
 OriginalGriff 3,404 Karthik Bangalore 1,967 ppolymorphe 1,379 Dave Kreskowiak 1,276 CPallini 1,185