I've made an algorithm that finds the largest number in a binary tree: (I know I should call the function "max" instead of "minimax", but It's too tedious to change it-)
I create a struct for every node and then link them together through the left and right pointers.
#include <stdio.h>
#include <stdlib.h>
// Struct for every node:
typedef struct treenode
{
int value;
struct treenode *left;
struct treenode *right;
} treenode;
// Prototypes:
treenode *createNode(int value);
treenode *minimax(treenode *root);
int main()
{
// Create the nodes:
treenode *n1 = createNode(0);
treenode *n2 = createNode(2);
treenode *n3 = createNode(3);
treenode *n4 = createNode(200);
treenode *n5 = createNode(5);
treenode *n6 = createNode(102);
treenode *n7 = createNode(101);
treenode *n8 = createNode(999);
treenode *n9 = createNode(888);
// Link them together:
n1->left = n2;
n1->right = n3;
n3->left = n4;
n3->right = n5;
n5->left = n6;
n5->right = n7;
n7->left = n8;
n7->right = n9;
// Print the output of minimax():
printf("%d", minimax(n1)->value);
// Free the nodes:
free(n1);
free(n2);
free(n3);
free(n4);
free(n5);
free(n6);
free(n7);
free(n8);
free(n9);
return 0;
}
// Creates a new node in the tree, that isn't linked to anything:
treenode *createNode(int value)
{
treenode *result = malloc(sizeof(treenode));
if (result != NULL)
{
result->left = NULL;
result->right = NULL;
result->value = value;
}
return result;
}
// The minimax() function is recursive:
treenode *minimax(treenode *root)
{
// If there are no "children" linked with the current node, return the current node:
if (root->left == NULL && root->right == NULL)
return root;
// If there is only one child linked, minimax() this child and return the biggest value in it:
if (root->left == NULL)
return minimax(root->right);
if (root->right == NULL)
return minimax(root->left);
// If the biggest value in the left child is greater than the biggest value in the right child, return the left child:
if (minimax(root->left)->value > minimax(root->right)->value)
return root->left;
// If the biggest value in the right child is greater than the biggest value in the left child, return the right child:
if (minimax(root->right)->value > minimax(root->left)->value)
return root->left;
// If the biggest values in both children are equal, return the left one:
if (minimax(root->right)->value == minimax(root->left)->value)
return root->left;
}
The program printed "2" instead of "999", not like I expected, but I can't find the error...
The maximum value could be stored in the root or anywhere in the left or right branches.
treenode *minimax(treenode *root)
{
treenode *ret = root;
treenode *temp;
if (root)
{
temp = minimax(root->left);
if (temp && temp->value > ret->value)
{
ret = temp;
}
temp = minimax(root->right);
if (temp && temp->value > ret->value)
{
ret = temp;
}
}
return ret;
}