#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <vector>
/*
#define __MAX( a, b ) \
({\
(a) > (b)?(a):(b);\
})
#define MAX(_a, _b) \
({ \
typeof(_a) __a = (_a); \
typeof(_b) __b = (_b); \
__a >= __b ? __a : __b; \
})*/
typedef struct __TREE_NODE{
char name;
struct __TREE_NODE * Lchild;
struct __TREE_NODE *Rchild;
}Node;
Node * CreateTree( );
int GetLongestPath( Node * T, std::vector<Node *> &vtr );
void PrintLongestPath( Node * T );
int HierachicalTraverse( Node * T );
int PreTraverse( Node * T);
int PostDelete( Node ** T );
int GetDepth( Node * T );
int nonRecursiveInorder( Node * T, int type );
int InorderTraverse( Node * T );
int NonRecurisveTraverse( Node * T);
int PostnonrecursiveTrav( Node * T );
int main()
{
Node * Head = NULL;
Head = CreateTree();
printf("\nthe Tree's depth is %d\n", GetDepth( Head ) );
printf("\n");
printf("The longest path is:\n\t");
PrintLongestPath( Head );
printf("\n");
printf("\nhierachical is:\n\t");
HierachicalTraverse( Head );
printf("\npreoreder Traverse is:");
printf("\nRecursive:\n\t");
PreTraverse( Head );
printf("\nnon-recursive:\n\t");
nonRecursiveInorder( Head, 1 );
printf("\n\n");
printf("\ninorder Traverse is:");
printf("\nRecursive:\n\t");
InorderTraverse( Head );
printf("\nnon-recursive:\n\t");
NonRecurisveTraverse( Head );
printf("\n\n");
printf("\npostorder Traverse is:");
printf("\nRecursive:\n\t");
PostnonrecursiveTrav( Head );
printf("\nnonRecursive:\n\t");
PostDelete( &Head );
printf("\n\n\n");
getc(stdin);
return 0;
}
/********************************************************************************
Get Tree's Length and the longest path, Recursive realization
*********************************************************************************/
int max( int a, int b )
{
return a > b?a:b;
}
int GetDepth( Node * T )
{
if( !T )
return 0;
return 1 + max( GetDepth( T->Lchild ), GetDepth( T->Rchild ) );
}
int GetLongestPath( Node * T, std::vector<Node *> &vtr )
{
int Llen = 0, Rlen = 0;
if( !T )
return 0;
vtr.push_back( T );
Llen = GetLongestPath( T->Lchild, vtr );
Rlen = GetLongestPath( T->Rchild, vtr );
if( Llen >= Rlen )
{
for( int i = 0; i < Rlen; i ++ )
vtr.pop_back();
return 1 + Llen;
}
else
{
int k = 0, i, j;
for( k = 0, i = vtr.size() - Rlen, j = i - Llen; k < Rlen; i ++,k ++, j ++ )
vtr[j] = vtr[i];
for( k = 0; k < Llen; k ++ )
vtr.pop_back();
return 1 + Rlen;
}
}
void PrintLongestPath( Node * T )
{
std::vector<Node *> vtr;
GetLongestPath( T, vtr );
//printf("Has get the longest Path\n");
for( std::vector<Node *>::const_iterator it = vtr.begin(); it != vtr.end(); it ++ )
{
printf("%c ", (*it)->name);
}
}
/*****************************************************************
Recursive Function
******************************************************************/
Node * CreateTree( )
{
Node * T = NULL;
char tmp = {0};
printf("please input T's name:\n");
tmp = getc(stdin);
getc(stdin);
if( tmp == '$' )
return NULL;
if( NULL == (T =(Node *) malloc( sizeof(Node))))
return NULL;
T->name = tmp;
T->Lchild = CreateTree( );
T->Rchild = CreateTree( );
return T;
}
int PreTraverse( Node * T)
{
if( !T )
return 0;
printf("%c ", T->name );
PreTraverse( T->Lchild );
PreTraverse( T->Rchild );
return 1;
}
int InorderTraverse( Node * T )
{
if( !T )
return 1;
InorderTraverse( T->Lchild );
printf("%c ", T->name );
InorderTraverse( T->Rchild );
return 1;
}
int PostDelete( Node ** T )
{
if( ! *T )
return 1;
PostDelete( &(*T)->Lchild );
PostDelete( &(*T)->Rchild );
printf("%c ",(* T)->name );
memset( *T, 0, sizeof( Node ) );
free( *T );
*T = NULL;
return 1;
}
/*******************************************************************************
Nonrecursive Function
********************************************************************************/
int NonRecurisveTraverse( Node * T)
{
std::stack<Node *> stk;
while( 1 )
{
if( T )
{
stk.push( T );
T = T->Lchild;
}
else
{
if( stk.empty() )
break;
T = stk.top();
printf("%c ", T->name );
stk.pop();
T = T->Rchild;
}
}
return 1;
}
int nonRecursiveInorder( Node * T, int type = 2 )
{
std::stack<Node *> stk;
if( T )
{
stk.push( T );
if( 1 == type )
printf("%c ", T->name );
}
while( !stk.empty() )
{
if( T && T->Lchild )//when T=T->right in the else scope, T may be null,so here need T
{
T = T->Lchild;
if( 1 == type )
printf("%c ", T->name );
stk.push( T );
}
else
{
T = stk.top();
if( 2 == type )
printf("%c ", T->name );
stk.pop();
T = T->Rchild;
if( T )
{
if( 1 == type )
printf("%c ", T->name );
stk.push( T );
}
}
}
return 1;
}
int PostnonrecursiveTrav( Node * T )
{
std::stack<Node *> stk;
Node * prePop = NULL;
while( 1 )
{
while(T)
{
stk.push( T );
T = T->Lchild;
}
if( stk.empty() )
return 1;
T = stk.top();
while( T->Rchild == NULL || T->Rchild == prePop )
{//poping out one elemet has two prerequirsities, one is that this node's right child is null, another is this node's rchild has just been poped out
printf("%c ", T->name );
prePop = T;
stk.pop();
if( stk.empty() )
return 1;
T = stk.top();
}
T = T->Rchild;
}
}
int HierachicalTraverse( Node * T )
{
std::queue<Node *> q;
if( T )
q.push( T );
while( !q.empty() )
{
T = q.front();
q.pop();
if( T->Lchild )
q.push( T->Lchild );
if( T->Rchild )
q.push( T->Rchild );
printf("%c ", T->name );
}
return 1;
}
