¶þ²æÊ÷µÄ»ù±¾²Ù×÷,×î»ù±¾µÄ³õʼ»¯Ïú»ÙÇå¿ÕÊ÷

Óöþ²æÊ÷µÄ˳Ðò´æ´¢ÊµÏÖ£º1.InitBiTree£¨&T£©
2.DestroyBiTree(&T)
3.CreateBiTree(&T,definition)
4.ClearBiTree(&T)
5.BiTreeEmpty(T)
ÄÄλ´óÉñ¿ÉÒÔ¸ø³öÈ«²¿ÊµÏÖ´úÂ룬лл

// ´´½¨¶þ²æÊ÷,ÇëÊäÈë½ÚµãµÄ×ÜÊýÁ¿: 7
// ÇëÁ¬ÐøÊäÈë7¸ö½ÚµãµÄÊý¾Ý: 4 2 6 1 3 5 7
// ǰÐò±éÀúÐòÁÐ: 4 2 1 3 6 5 7
// ÖÐÐò±éÀúÐòÁÐ: 1 2 3 4 5 6 7
// ºóÐò±éÀúÐòÁÐ: 1 3 2 5 7 6 4
// ¶þ²æÊ÷µÄ½ÚµãÒ»¹²ÓÐ7¸ö,¶ÈΪ1µÄ½ÚµãÓÐ0¸ö,¶ÈΪ2µÄ½ÚµãÓÐ3¸ö,
// Ҷ×Ó½ÚµãÓÐ4¸ö,Êý¾ÝÖµµÄ×î´óÖµÊÇ7,×îСֵÊÇ1
//
// ¶ÔÓ¦µÄ¶þ²æÊ÷:
//
//       4
//    /      \
//   2        6
//  /  \     /  \
// 1    3   5    7

#include "stdio.h"
#include "stdlib.h"
struct Tree
{
    int data;
    struct Tree *left;
    struct Tree *right;
};
typedef struct Tree TreeNode;
typedef TreeNode *Bitree;

typedef struct stack_node //Õ»µÄ½á¹¹Ìå
{
    Bitree bt;
struct stack_node *next;
} stack_list, *stack_link;

Bitree insertNode(Bitree root,int data) //²åÈë½áµã
{
    Bitree newnode;
    Bitree current;
    Bitree back;
    newnode=(Bitree)malloc(sizeof(TreeNode));
    if(newnode==NULL)
    {
        printf("\n¶¯Ì¬·ÖÅäÄÚ´æ³ö´í.\n");
        exit(1);
    }
    newnode->data=data;
    newnode->left=NULL;
    newnode->right=NULL;
    if(root==NULL)
    {
        return newnode;
    }
    else
    {
        current=root;
        while(current!=NULL)
        {
            back=current;
            if(current->data > data)
               current=current->left;
            else
               current=current->right;
        }
        if(back->data > data)
            back->left=newnode;
        else
            back->right=newnode;
    }
    return root;
}

Bitree createTree() //´´½¨¶þ²æÊ÷(·ÇµÝ¹é)
{
    Bitree root=NULL;
    int len;
    int data;
    int i;
    printf("´´½¨¶þ²æÊ÷,ÇëÊäÈë½ÚµãµÄ×ÜÊýÁ¿: ");
    scanf("%d",&len);
    printf("ÇëÁ¬ÐøÊäÈë%d¸ö½ÚµãµÄÊý¾Ý: ",len);
    for(i=0;idata);
        preOrder(ptr->left);
        preOrder(ptr->right);
    }
}

void inOrder(Bitree ptr) //ÖÐÐò±éÀú(µÝ¹é·¨)
{
    if(ptr!=NULL)
    {
        inOrder(ptr->left);
        printf("%d ",ptr->data);
        inOrder(ptr->right);
    }
}

void postOrder(Bitree ptr) //ºóÐò±éÀú(µÝ¹é·¨)
{
    if(ptr!=NULL)
    {
        postOrder(ptr->left);
        postOrder(ptr->right);
        printf("%d ",ptr->data);
    }
}

//¼ì²é[Õ»]ÊÇ·ñÊÇ¿Õ
int isEmpty(stack_link stack)
{
if(stack == NULL)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

//ÈëÕ»
stack_link push(stack_link stack,Bitree bt)
{
stack_link new_node;

new_node=(stack_link)malloc(sizeof(stack_list));
if(!new_node)
{
  return NULL;
}
new_node->bt=bt;
new_node->next=stack;
stack=new_node;
return stack;
}

//³öÕ»
stack_link pop(stack_link stack,Bitree *bt)
{
stack_link top;

if(isEmpty(stack))
{
  *bt = NULL;
  return NULL;
}
top=stack;
*bt=top->bt;
stack=top->next;
free(top);
return stack;
}
//ͳ¼Æ½Úµã(·ÇµÝ¹é)
void reportByStack(Bitree bt,int *pTotal,int *pCount0,int *pCount1,
                   int *pCount2,int *pMaxValue,int *pMinValue)
{
    Bitree p=NULL;
    stack_link oneStack=NULL;
    int total=0;
    int count0=0,count1=0,count2=0;
    int maxValue=0,minValue=0;

    if(bt == NULL)
    {
        return;
    }

    p=bt;          //µ±Ç°¶þ²æÊ÷µÄ½Úµã
    minValue=p->data;
    maxValue=minValue;
    while(p != NULL)
    {
        if(minValue > p->data)
        {
            minValue = p->data;
        }
        if(maxValue data)
        {
            maxValue = p->data;
        }
        total++; //total=count0+count1+count2
        if(p->right == NULL && p->left == NULL) //Ò¶×Ó
        {
            count0++;
        }
        else if(p->right != NULL && p->left != NULL) //¶È2
        {
            count2++;
        }
        else //¶È1
        {
            count1++;
        }
        if(p->right != NULL)  //Èç¹ûÓÐÓÒ×ÓÊ÷,ÂíÉÏÈëÕ»
        {
            oneStack=push(oneStack,p->right);
        }
        if(p->left != NULL) //Èç¹ûÓÐ×ó×ÓÊ÷,ÉèΪµ±Ç°½Úµã
        {
            p=p->left;
        }
        else
        {
           oneStack=pop(oneStack,&p);
           if(p == NULL)
           {
               break;
           }
        }
    }
    *pTotal=total;
    *pCount0=count0;
    *pCount1=count1;
    *pCount2=count2;
    *pMaxValue=maxValue;
    *pMinValue=minValue;
}

int main()
{
    Bitree root=NULL;
    int total=0;
    int count0=0,count1=0,count2=0;
    int maxValue=0,minValue=0;

    root=createTree(); //´´½¨¶þ²æÊ÷

    printf("\nÇ°Ðò±éÀúÐòÁÐ: ");
    preOrder(root);
    printf("\nÖÐÐò±éÀúÐòÁÐ: ");
    inOrder(root);
    printf("\nºóÐò±éÀúÐòÁÐ: ");
    postOrder(root);

    //ͳ¼Æ½Úµã(·ÇµÝ¹é)
    reportByStack(root,&total,&count0,&count1,&count2,&maxValue,&minValue);
    printf("\n¶þ²æÊ÷µÄ½ÚµãÒ»¹²ÓÐ%d¸ö,¶ÈΪ1µÄ½ÚµãÓÐ%d¸ö,¶ÈΪ2µÄ½ÚµãÓÐ%d¸ö,\n",
           total,count1,count2);
    printf("Ò¶×Ó½ÚµãÓÐ%d¸ö,Êý¾ÝÖµµÄ×î´óÖµÊÇ%d,×îСֵÊÇ%d",
           count0,maxValue,minValue);

    printf("\n");
    return 0;
}