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

5 comments:

Tonguç said...

Emre Macit'e bisiler mi oldu biz gormeyeli, yilanlar felan, bi de "in memory of" felan olm allah korusun gocenlerin ardindan yazilir bunlar, alla allaaa :)

emreknlk said...

macit sucunu bilio Tonguc abi, bi gun zehirlencek yilan isirmasindan gorucek gununu :)

Özgür Macit said...

Müsait olduğumda senin beğenmediğin o yılanla senin destan uzunluğundaki kodunu iki satırda yazayım da sen öyle mel mel, ağzın açılmış ve ağzından sular akaraktan bakarken sen biz karşına geçip "vah zavallı, iyi çocuktu aslında, C'ye çok düşkündü velakin" diyelim :)

emreknlk said...

ağzımdan sular akıcağını da nerden çıkardın özgür:) "programming is an art more than knowledge". Ayrıca bilmeni isterim ben C ye değil C bana düşkün (H) :)

Anonymous said...

Hi Emre;

If you print out program output as you did in source, it would be more readable for people who wants to ,also, see output.

Kindly Wishes...
Mennan