Thread: heap arrainging question..

a heap is a binary tree in which the root is bigger then both its sons.

i need to write a function which gets a node and a root of the heap where this node is located in the bottom level.

i need to switch this nodes value with the roots and delete it
and then rearrange the tree so ill get a heap again.

the diagram is in this link

i tried to implement it here
but i dont know why i get all these errors??

Code:

#define false 0
#define true 1


typedef struct TreeNode
{
	struct TreeNode *father;
	struct TreeNode *left;
	struct TreeNode *right;
	double val;
}TreeNode;

TreeNode * maxson(TreeNode * root);
void swap(TreeNode * root,TreeNode * node);
double deletemax(treenode **heap,treenode *leaf);
TreeNode * maxson(TreeNode * root);
void arrange(TreeNode ** root);
int main()
{
   TreeNode* root;
   double t;
   root=(TreeNode*)malloc(sizeof(TreeNode));
   root->val=9;
   root->right=(TreeNode*)malloc(sizeof(TreeNode));
   root->right->val=4;
   root->right->left=NULL;
   root->right->right=NULL;
   root->right->father=root;

   root->left=(TreeNode*)malloc(sizeof(TreeNode));
   root->left->val=8;
   root->left->left=(TreeNode*)malloc(sizeof(TreeNode));
   root->left->left->val=7;
   root->left->right=(TreeNode*)malloc(sizeof(TreeNode));
   root->left->right->val=6;
   root->left->right->father=root->left;
   root->left->left->father=root->left;

   root->left->right->right=NULL;
   root->left->right->left=NULL;

   root->left->left->right=NULL;
   root->left->left->left=NULL;

   t=deletemax(&heap,root->left->right);
   return 0;
}

double deletemax(treenode **heap,treenode *leaf)//i have to use this signature
{
	double temp=*heap->val;
  swap(*heep,leaf);
  free(leaf);
   arrange(heap);
 return temp;
  
}
void swap(TreeNode * root,TreeNode * node)
{
	double temp;
    temp=root->val;
    root->val=node->val;
	root->val=temp;

}

TreeNode * maxson(TreeNode * root)
{
  if (root->left>root->right)
  {
        return root->left;
  }
  else
  {
        return root->right;
  }
}

void arrange(TreeNode ** root)
{
   treenode* temp;
   temp=maxson(*root); 
   if ((*root->left==NULL)&&(*root->right==NULL))
   {
       return;
   }
   if (temp->val>*root->val)
   {
      swap(*root,node);
      
   }
   arrange(&(root->left));
   arrange(&(root->right));
}

run your code in the debugger.

Also think - what will happen to the father after you free the son

acctually i am not using the father at all so i dont care
i fixed the code a little more

but my main problem is marked in a comment "here is the problem" in the code.
the problem is when i free the memory
of pointer "leaf"
then when i want it to point to NULL
it doesnt do it.
the debuger shows some random memory instead of NULL
??

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define false 0
#define true 1


typedef struct TreeNode
{
	struct TreeNode *father;
	struct TreeNode *left;
	struct TreeNode *right;
	double val;
}TreeNode;

TreeNode * maxson(TreeNode * root);
void swap(TreeNode * root,TreeNode * node);
double deletemax(TreeNode **heap,TreeNode *leaf);
TreeNode * maxson(TreeNode * root);
void arrange(TreeNode ** root);
int main()
{
   TreeNode* root;
   double t;
   root=(TreeNode*)malloc(sizeof(TreeNode));
   root->val=9;
   root->right=(TreeNode*)malloc(sizeof(TreeNode));
   root->right->val=4;
   root->right->left=NULL;
   root->right->right=NULL;
   root->right->father=root;

   root->left=(TreeNode*)malloc(sizeof(TreeNode));
   root->left->val=8;
   root->left->left=(TreeNode*)malloc(sizeof(TreeNode));
   root->left->left->val=7;
   root->left->right=(TreeNode*)malloc(sizeof(TreeNode));
   root->left->right->val=6;
   root->left->right->father=root->left;
   root->left->left->father=root->left;

   root->left->right->right=NULL;
   root->left->right->left=NULL;

   root->left->left->right=NULL;
   root->left->left->left=NULL;

   t=deletemax(&root,root->left->right);
   return 0;
}

double deletemax(TreeNode **heap,TreeNode *leaf)//i have to use this signature
{
	double temp=(*heap)->val;
  swap(*heap,leaf);
  
  free(leaf);
  leaf=NULL;                                      //here is the problem
   arrange(heap);
 return temp;
  
}
void swap(TreeNode * root,TreeNode * node)
{
	double temp;
    temp=root->val;
    root->val=node->val;
	node->val=temp;

}

TreeNode * maxson(TreeNode * root)
{
	if (root->left==NULL)
	{
      return root->right;
	}
	
	if (root->right==NULL)
	{
      return root->left;
	}
 
  if (root->left->val>root->right->val)
  {
        return root->left;
  }
  else
  {
        return root->right;
  }
}

void arrange(TreeNode ** root)
{
   TreeNode* temp;
   temp=maxson(*root); 
   if (((*root)->left==NULL)&&((*root)->right==NULL))
   {
       return;
   }
   if (temp->val>(*root)->val)
   {
      swap(*root,temp);
      
   }
   arrange(&((*root)->left));
   arrange(&((*root)->right));
}

Originally Posted by transgalactic2

acctually i am not using the father at all so i dont care

If you do not care about your code - stop posting it here