Sunday, April 01, 2007

Explore yourself before expoloring snakes

This post's title is written for my friend ozgur Macit. He llikes playing with snakes and i write this post in memory of him:)
Tonight i write some piece of code about binary trees. it is ordered. i mean, smaller values are in the left side, bigger values are in the right side.
The code probably isnt bug free because i didnt test it at all. I want to show you some basic concepts in C and C++. This code isnt written in C because i use templates, but i dont use the OOP also. It is C++ in C :)
Please take care of pointers, pointer to pointers, recursion, binary tree, template and other things which lies in the code...
I write most of the functions for solving problems in http://cslibrary.stanford.edu/110/BinaryTrees.html
I especially like hasPathSum function. It is very short and useful.


Firstly here is a test module:

#include"binaryTree.h"
#include<iostream>
using namespace std;


int main(){

BinaryTree<int> tree;

addNode( &tree.root , 100 );
addNode( &tree.root , 500 );
addNode( &tree.root , 200 );
addNode( &tree.root , 70 );
addNode( &tree.root , 10 );
addNode( &tree.root , 340 );
addNode( &tree.root , 324 );


printTreeInorder( tree.root );


cout << "size is: "<< size(tree.root )<<endl;
cout << "max depth is: "<< maxDepth(tree.root )<<endl;
cout << "min value is: "<< minValue(tree.root )<<endl;
cout << "max value is: "<< maxValue(tree.root )<<endl;
cout << "haspathsum ( 180 ) value is: "<< boolalpha << hasPathSum(tree.root , 180 )<<endl;

mirror(tree.root );
printTreeInorder( tree.root );

return 0;
}


And the binaryTree.h

#ifndef binaryTree
#define binaryTree


template <typename T>
struct Node{
T data;
Node* left;
Node* right;
Node( T dt )
{
data = dt;
left = right=reinterpret_cast<Node<T>*>(0);
}
};


template<typename T>
struct BinaryTree{
Node<T>* root;
BinaryTree()
{
root = reinterpret_cast<Node<T>*>(0);
}
};


template<typename T>
Node<T>* getNode( T data ) {
return new Node<T>( data );
}

template<typename T>
bool addNode( Node<T>** root , T data ){
try{
if(!*root){
*root = getNode( data);
}else{
if( data < (*root)->data )
addNode(&(*root)->left , data );
else
addNode(&(*root)->right,data);
}
}catch(...){
return false;
}

return true;
}

template<typename T>
int size( Node<T>* root ){

if( !root )
return 0;
if( !root->left && !root->right )
return 1;
else{
return size( root->left ) + size( root->right ) + 1;
}
}


template<typename T>
int maxDepth( Node<T>* root ){

if(!root)
return -1;
else{
int leftSize , rightSize;
leftSize = 1 + maxDepth( root->left );
rightSize = 1 + maxDepth( root->right );
return rightSize > leftSize ? rightSize : leftSize;
}
}

template<typename T>
T minValue( Node<T>* root ){
T dummy;
if( !root ){
return dummy;
}
if( root->left )
return minValue( root->left );
else
return root->data;
}

template<typename T>
T maxValue( Node<T>* root ){
T dummy;
if( !root ){
return dummy;
}
if( root->right )
return maxValue( root->right );
else
return root->data;
}


bool hasPathSum(struct Node<int>* root, int sum) {

if( !root )
return ( sum == 0 );
else{
return ( hasPathSum(root->left , sum - root->data ) || hasPathSum(root->right , sum - root->data ) );
}
}

template<typename T>
void mirror( Node<T>* root ){
if( !root->left && !root->right)
return;
if( root->left )
mirror(root->left);
if( root->right)
mirror(root->right);
Node<T>* t;
t = root->left;
root->left = root->right;
root->right = t;
}


template<typename T>
void printTreePreorder( Node<T>* root ){

if( root ){
cout << root->data << endl;
printTreePreorder( root->left );
printTreePreorder( root->right );
}
}

template<typename T>
void printTreeInorder( Node<T>* root ){

if( root ){
printTreeInorder( root->left );
cout << root->data << endl;
printTreeInorder( root->right );
}
}

template<typename T>
void printTreePostorder( Node<T>* root ){

if( root ){
printTreePostorder( root->left );
printTreePostorder( root->right );
cout << root->data << endl;
}
}

#endif