#include<stdio.h>
#include<malloc.h>

//定义节点
typedef struct node
{
        struct node *pre;
        struct node *left;
        struct node *right;
        void *         value;
}node;
/*==========================================
函数功能：比较输入值与当前节点值的大小
输入参数：输入值和当前节点
返回参数：相应孩子
作    者：
日    期：2007-3-16
===========================================*/
node *compare(void * value,node *boot)//
{

        if(*(double*)value<*(double*)boot->value)
                return boot->left;           //小于当前值返回左孩
        else
                return boot->right;         //大于当前值返回右孩
}

/*=========================================
函数功能：创建树
输入参数：插入值和根节点
返回参数：新创建的节点
作    者：
日    期：2007-3-16
=========================================*/
node *insert(void * value,node *boot)
{
        node *new,*bot;
        bot=boot;
        new=malloc(sizeof(node));       //分配空间
        new->value=value;               //赋值
        new->left=new->right=NULL;
        if(boot==NULL)                  //如果根为空，创建根节点
        {
                boot=new;
        }
        else
        {
                for(;;)
                {
                        if(*(double*)value==*(double*)boot->value)//如果此值以包含，提示，并终断。
                        {
                                printf("In this tree has contain this value!\n");
                                free(new);
                                break;
                        }
                        else
                        {
                                bot=compare(value,bot);//比较输入值与当前节点值，返回相应节点。
                                if(bot==NULL)          //返回值为空时
                                {
                                        if(*(double*)value<*(double*)boot->value)//输入值小于当前值
                       
                                        {
                                                boot->left=new;
                                                new->pre=boot;
                                                break;//插入节点为左孩
                                        }
                                        else
                                        {
                                                boot->right=new;
                                                new->pre=boot;
                                                break;//否则为右孩
                                        }
                                }
                        }
                        boot=bot;
                }
        }
        return new;
}

/*============================================
函数功能：打印当前节点值
输入参数：当前节点
返回参数：空
作    者：
日    期：2006-3-16
==============================================*/
void print(node *now)
{
        if(now==NULL)
                printf("This node is void!\n");
        else
                printf("%lf\n",*(double*)now->value);
}
/*=============================================
函数功能：当前节点移动
输入参数：当前节点
返回参数：移动后的节点
作    者：
日    期：2006-3-16
=============================================*/
//移向当前节点的父节点。
node *pre(node *now)
{
        if(now->pre==NULL)
                printf("This node is the boot!\n");
        else
                now=now->pre;
        return now;          
}
//移向当前节点的左孩。
node *left(node *now)
{
        if(now->left==NULL)
                printf("This node has no left child!\n");
        else
                now=now->left;
        return now;
}
//移向当前节点的右孩。
node *right(node *now)
{
        if(now->right==NULL)
                printf("This node has no right child!\n");
        else
                now=now->right;
        return now;
}
//========================================

/*========================================
函数功能：前序遍历返回二叉树的所有节点值
输入参数：根结点
返回参数：空
作    者：
日    期：2006-3-16
========================================*/
/*void printall_a(node *boot)      //遍历子函数一
{
        if(boot==NULL)
                return;
        else
        {
                print(boot);
                if(boot->left!=NULL)//如果左不为空：左孩赋予根
                {
                        boot=boot->left;
                       
                }
                else if(boot->right!=NULL)//否则，如果右不为：友孩赋予根
                        boot=boot->right;
                else
                {
                        for(;;)
                        {
                                if(boot==NULL||boot->pre==NULL)//如果根为空，或根的夫为空
                                {
                                        boot=NULL;
                                        break;//根置为空，终端
                                }
                                else
                                        ;
                                if(boot==boot->pre->left)//如果根为左孩
                                {
                                        if(boot->pre->right!=NULL)//且根的夫的友孩不为空
                                        {
                                                boot=boot->pre->right;
                                                break;//跟赋值为根的父的友孩
                                        }
                                        else
                                                boot=boot->pre;//为空时根赋值为父
                                }
                                else//如果根为右孩
                                {                            
                                        if(boot->pre->pre==NULL)//且根的父的父为空
                                        {
                                                boot=NULL;//根赋值为空
                                                break;
                                        }
                                        else
                                                ;
                                        if(boot->pre->pre->right!=NULL&&boot->pre!=boot->pre->pre->right)//如果根的父的父的友孩不为空，且根的夫不为根的父的父的友孩
                                        {
                                                boot=boot->pre->pre->right;
                                                break;
                                        }
                                        else
                                                boot=boot->pre;
                                }
                        }
       
                }
        printall(boot);//递归
        }
}*/

//遍历子函数二：递归法，左优先遍历(高效)（为空不返回）。
void printall_b(node *node)
{
        if(node!=NULL)
        {
                print(node);
                printall_b(node->left);
                printall_b(node->right);
        }
}
void printall(node *boot)           //遍历主函数
{
        if(boot==NULL)
                printf("This tree is void!\n");
        else
                printall_b(boot);
}

/*=============================================
函数功能：前序遍历输出所有叶节点的值
输入参数：二叉树的根结点
返回参数：空
作    者：
日    期：2006-3-16
=============================================*/
void printaleaf(node *node)
{
        if(node!=NULL)
        {
                if(node->left==NULL&&node->right==NULL)
                        print(node);
                else
                        ;
                printaleaf(node->left);
                printaleaf(node->right);
        }


}

/*==========================================================================
函数功能：自左到右，遍历下一叶节点
输入参数：任意节点
返回参数：以当前节点为基准，自左到右返回单个叶节点,尾层叶节点遍历完后，返回NULL
作    者：
日    期：2006-3-16
==============================================================================*/

node *leaf(node *boot)
{
        if(boot==NULL)
                return NULL;
        else
        {
                if(boot->left!=NULL)//如果左不为空：左孩赋予根
                {
                        boot=boot->left;
                       
                }
                else if(boot->right!=NULL)//否则，如果右不为：友孩赋予根
                        boot=boot->right;
                else            //如果左孩子和右孩子为空
                {
                        for(;;)
                        {
                                if(boot==NULL||boot->pre==NULL)//如果根为空，或根的父为空
                                {
                                        boot=boot;
                                        break;//根值不变，终断
                                }
                                else
                                        ;
                                if(boot==boot->pre->left)//如果根为左孩
                                {
                                        if(boot->pre->right!=NULL)//且根的夫的右孩不为空
                                        {
                                                boot=boot->pre->right;
                                                break;//跟赋值为根的父的友孩
                                        }
                                        else
                                                boot=boot->pre;//为空时根赋值为父
                                }
                                else//如果根为右孩
                                {                            
                                        if(boot->pre->pre==NULL)//且根的父的父为空
                                        {
                                                boot=NULL;//根赋值为空
                                                break;
                                        }
                                        else
                                                ;
                                        if(boot->pre->pre->right!=NULL&&boot->pre!=boot->pre->pre->right)//如果根的父的父的右孩不为空，且根的父不为根的父的父的左孩
                                        {
                                                boot=boot->pre->pre->right;
                                                break;
                                        }
                                        else
                                                boot=boot->pre;
                                }
                        }
       
                }
                if(boot==NULL)
                        return NULL;
                else if(boot->left==NULL&&boot->right==NULL)
                        return boot;
                else
                        return leaf(boot);//递归
        }
}

/*==================================================
 函数功能： 删除当前也节点,返回当前节点的父节点
 输入参数：需删除的节点
 返回参数：当前节点的父
 作    者：
 日    期：2006-3-16
==================================================*/
node *del(node *boot)
{
        node *now=boot;
        if(boot==NULL)
                printf("This node is void\n");
        else if(boot->left==NULL&&boot->right==NULL)
        {
                boot=now->pre;
                if(boot==NULL)
                        ;
                else if(boot->left==now)
                        boot->left=NULL;
                else
                        boot->right=NULL;
                free(now);
        }
        else
                printf("This node is not leaf.\n");
        return boot;
}
/*===========================================
函数功能：查找数值，并返回节点值
输入参数：二叉树的根节点节点，与要查找的值
返回参数：与要查找数值相等的节点
作    者：
日    期：2006-3-16
===========================================*/
node *search(node *boot,void * a)
{
        if(*(double*)boot->value==*(double*)a)
                return boot;
        else if(*(double*)boot->value>*(double*)a&&boot->left!=NULL)
                boot=boot->left;

        else if(*(double*)boot->value<*(double*)a&&boot->right!=NULL)
                boot=boot->right;


        else
                return NULL;
        return search(boot,a);
       
}
//深度相关
/*================================================
函数功能：测试二叉树的深度
输入参数：二叉树的根结点
返回参数：深度
作    者：
日    期：2007-3-18
================================================*/
int deep(node *boot)
{
        int l,r;
        if(boot==NULL)
                return 0;
        else
        {
                l=deep(boot->left);
                r=deep(boot->right);
        }
        if(l>r)
                return l+1;
        else
                return r+1;
}

/*================================================
函数功能：指定深度遍历（本地定义第一层为：一）
输入参数：树的根节点和指定遍历层
返回参数：自左到右输出指定层的节点值
作    者：
日    期：2006-3-18
=================================================*/
void printc(node *boot,int a)
{
        if(boot!=NULL)
        {
                if(a==1)
                        print(boot);
                else
                {
                        --a;
                        printc(boot->left,a);
                        printc(boot->right,a);
                }
        }
}

/*================================================
主函数
=================================================*/

int main(void)
{
        node *boot,*now,*temp;
        now=boot=NULL;
        int i;
        double value,*new;

        for(;;)//创建树
        {
       
                printf("Please input the value(0 is the end):");
                new=malloc(sizeof(double));
                scanf("%lf",new);
                getchar();
                if(*new==0)
                        break;
                now=insert((void*)(new),boot);
                if(boot==NULL)
                        boot=now;
        }

        printf("左序遍历：\n");
        printall(boot);

        i=deep(boot);//深度计算
        printf("The deep of the tree is %d\n",i);

        printf("rearch:");//查找
        scanf("%lf",&value);
        now=search(boot,(void*)(&value));
        if(now==NULL)
                printf("This tree has not this value.\n");
        else
        {       printf("Include this value:");
                print(now);
        }

        now=boot;
        printaleaf(boot);//遍历所有叶节点
        for(;;)//叶节点的操作
        {
                if(boot==NULL)
                        break;
                temp=now;
                now=leaf(now);
                if(now==NULL)
                {
                        {
                                printf("The last float leaf over,next(pre float):\n");
                                now=boot;
                                continue;
                        }
                }
                else
                        ;       
                printf("The present leaf node value is:");
                print(now);
                printf("del-0,continue-1,break-2:");
                scanf("%d",&i);
                if(i==1)
                        continue;
                else if(i==2)
                        break;
                else if(i==0)
                {
                        if(now->pre==NULL&&now->left==NULL&&now->right==NULL)
                                boot=NULL;
                        now=del(now);
                        if(now==NULL)
                                break;
                        else
                                ;
                }
                else
                {
                        printf("The input is error!\n");
                        now=temp;
                }       
        }
        printall(boot);//遍历所有
        printf("层遍历\n");
        for(i=1;i<=deep(boot);i++)
        {
                printc(boot,i);
                printf("\n");
        }
        return 0;
}