I came up with some code for a simple binary tree. I want to balance it but I am having trouble figuring out how to do this.
My idea was to create a malloced array of pointers to nodes then qsort them and rebuild the tree from that. The problem with this is that (AFAIK) I will need to use recursion to get at all the nodes which makes it tricky to keep track of the array index to place to node.
Heres my code:
Code:
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
struct node *left;
struct node *right;1
int num;
}Node;
Node *CreateHeadNode(int num) // Creates a new tree
{
Node *head = malloc(sizeof(Node));
head->left = NULL;
head->right = NULL;
head->num = num;
return head;
}
void AddNode(Node *head, int num)
{
Node *new_node = malloc(sizeof(Node));
new_node->left = NULL;
new_node->right = NULL;
new_node->num = num;
Node *here = head;
Node *next = (num < here->num)? here->left: here->right;
while(next)
{
here = next;
next = (num < here->num)? here->left: here->right;
}
//'here' will be the last node
if(num < here->num)
here->left = new_node;
else
here->right = new_node;
}
void PrintTree(Node *head)
{
printf("Node: %2d\tL:%p \tR:%p\n", head->num, head->left, head->right);
if(head->left) PrintTree(head->left);
if(head->right)PrintTree(head->right);
}
void TreeSize(Node *node, int *count)
{
(*count)++;
if(node->left)TreeSize(node->left, count);
if(node->right)TreeSize(node->right, count);
}
void BalanceTree(Node *head)
{
int size = 0;
TreeSize(head, &size);
Node **temp = malloc(size * sizeof(Node*));
// Stuck here
free(temp);
}
int main()
{
Node *head = CreateHeadNode(10);
AddNode(head, 15);
AddNode(head, 12);
AddNode(head, 18);
AddNode(head, 11);
AddNode(head, 1);
AddNode(head, 6);
PrintTree(head);
int count = 0;
TreeSize(head, &count);
printf("Node Count: %d\n", count);
return 0;
}
Anyone got any suggestions as to the best way to go about this?
Cheers.