#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define DEBUG(X) printf(X)
struct TreeNode;
typedef struct TreeNode *Position_t;
typedef struct TreeNode SearchTree_t;
typedef int ElementType_t;
struct TreeNode{
ElementType_t Element;
SearchTree_t* Left;
SearchTree_t* Right;
};
SearchTree_t* MakeEmpty(SearchTree_t* Tree){
if(Tree != NULL){
MakeEmpty(Tree -> Left);
MakeEmpty(Tree -> Right);
free(Tree);
}
return NULL;
}
SearchTree_t* Insert(ElementType_t X,SearchTree_t* Tree){
if(Tree == NULL){
//create and return a one node tree
Tree = malloc(sizeof(struct TreeNode));
if(Tree == NULL){
DEBUG("Out of space!!!!");
}else{
Tree->Element = X;
Tree->Left = Tree->Right = NULL;
}
}else if(X < Tree->Element){
Tree->Left = Insert(X,Tree->Left);
}else if(X > Tree->Element){
Tree->Right = Insert(X,Tree->Right);
}else{
//else X is in the tree already,we'll do nothing
}
return Tree;
}
Position_t Find(ElementType_t X,SearchTree_t* Tree){
if(Tree == NULL){
return NULL;
}
if( X < Tree->Element){
return Find(X,Tree -> Left);
}else if( X > Tree->Element){
return Find(X,Tree -> Right);
}else{
return Tree;
}
}
Position_t FindMin(SearchTree_t* Tree){
if(Tree == NULL){
return NULL;
}else if(Tree->Left == NULL){
return Tree;
}else{
return FindMin(Tree->Left);
}
}
Position_t FindMax(SearchTree_t* Tree){
if(Tree != NULL){
while(Tree -> Right != NULL){
Tree = Tree -> Right;
}
}
return Tree;
}
int get_Tree_Depth(SearchTree_t* Tree){
int L,R;
if(Tree == NULL){
return 0;
}else{
L = get_Tree_Depth(Tree->Left);
R = get_Tree_Depth(Tree->Right);
if(L > R){
return L + 1;
}
return R+1;
}
}
static ElementType_t datas[255] = {0};
static int Element_index = 0;
#define NUM 2
void print_Tree(SearchTree_t* Tree,int Depth,int for_depth,int hight){
int i;
if(Tree == NULL){
return;
}
if(hight == 0){
for(i = 0;i < (Depth - for_depth - NUM);i++){
printf(" ");
}
}
printf("%d%%=%d\r\n",hight,Tree->Element);
if(Tree->Left != NULL){
for(i = 0;i < (Depth - for_depth-1 - NUM);i++){
printf(" ");
}
printf("/");
print_Tree(Tree->Left,Depth,for_depth+1,hight+1);
}
if(Tree->Right != NULL){
for(i = 0;i < (Depth - for_depth+1 - NUM);i++){
printf(" ");
}
printf("\\");
print_Tree(Tree->Right,Depth,for_depth-1,hight+1);
}
}
int main(){
SearchTree_t* myTree;
myTree = Insert(6,NULL);
Insert(2,myTree);
Insert(1,myTree);
Insert(4,myTree);
Insert(3,myTree);
Insert(8,myTree);
Position_t min = FindMin(myTree);
printf("min = %d\r\n",min->Element);
Position_t max = FindMax(myTree);
printf("max = %d\r\n",max->Element);
int depth = 0;
depth = get_Tree_Depth(myTree);
printf("Depth = %d\r\n",depth);
print_Tree(myTree,depth,0,0);
return 1;
}