// 若二叉树中存在和 x 相同的元素，则 p 指向该结点并返回 OK,否则返回 FALSE
bool Preorder (BiTree T, int x, BiNode *p)
{
    //如果二叉树不为空，开始查询结点
    if (T)
    {
        //如果根节点就是目标结点
        if (T->data == x)
        {
            //p 指向该结点并返回真
            p = T;
            
            return true;
        }
        else
        {
            //递归调用，也就是先序遍历
            if (Preorder(T->lchild, x, p))
            {
               return true;
            }
            else
            {
                return(Preorder(T->rchild, x, p)) ;
            }
        }//end of else
    }//end of if
    else
    {
        return false;
    }
}

//统计二叉树中所有末位结点的个数，也就是叶子结点的个数的统计
void CountLeaf(BiTree T, int *count)
{
    //如果不为空树
    if (T != NULL)
    {
        //如果树的左右子树都为空，那么叶子结点数+1
        if ((!T->lchild) && (!T->rchild))
        {
            // 对叶子结点计数
            count++;
        }
        //否则，继续递归遍历
        CountLeaf(T->lchild, count);
        CountLeaf(T->rchild, count);
    } // if
}

//返回指针T所指二叉树中所有结点个数
//还是前序遍历
int Count(BiTree T)
{
    //如果 T 为空
    if (!T)
    {
        //则说明是空树，返回0个结点
        return 0;
    }
    //如果 T 的左右子树 为空，说明只有一个结点，根节点而已
    if (!T->lchild && !T->rchild)
    {
       return 1;
    }
    else{
        //否则，递归遍历
        int m = Count(T->lchild);
        int n = Count(T->rchild);
        
        return (m + n + 1);
    } //else
}

//求二叉树的深度，后续遍历的使用
int Depth(BiTree T)
{
    int depth;
    int depthLeft;
    int depthRight;
    //如果二叉树为空
    if (!T)
    {
        depth = 0;
    }
    else
    {
        depthLeft = Depth(T->lchild);
        depthRight = Depth(T->rchild);
        depth = 1 + (depthLeft > depthRight ? depthLeft : depthRight);
    }
    
    return depth;
}

//生成一个二叉树的结点,(其数据域为item,左指针域为lptr,右指针域为rptr)
BiNode * GetTreeNode(int item, BiNode *lptr, BiNode *rptr)
{
    BiTree T;
    //如果新建结点失败
    if (!(T = new BiNode))
    {
        //退出
        exit(1);
    }
    //新建结点成功
    T->data = item;
    //
    T->lchild = lptr;
    T->rchild = rptr;
    //返回新建的结点的指针
    return T;
}

BiNode * CopyTree(BiNode *T)
{
    BiNode *newT;
    BiNode *newlptr;
    BiNode *newrptr;
    //如果源树为空
    if (!T)
    {
        //返回空
       return NULL;
    }
    //如果根的左子树不为空
    if (T->lchild)
    {
        newlptr = CopyTree(T->lchild); //复制左子树
    }
    else
    {
        //左子树为 null
        newlptr = NULL;
    }
    //如果根的右子树不为空
    if (T->rchild)
    {
        newrptr = CopyTree(T->rchild); //复制右子树
    }
    else
    {
        //否则，右子树为 null
        newrptr = NULL;
    }
    //新生成一个二叉树的结点，也就是后续遍历的过程
    newT = GetTreeNode(T->data, newlptr, newrptr);
    
    return newT;
}

//递归建立二叉树
bool CreateBiTree(BiTree T)
{
    char ch;
    //输入结点的值
    scanf(&ch);
    //如果输入空字符
    if(ch == ' ')
    {
        //代表空结点
        T = NULL;
    }
    else
    {
        T = (BiNode*)malloc(sizeof(BiNode));
        //如果新建结点失败
        if (!T)
        {
             exit(1);
        }
        //成功。先序遍历的顺序建立二叉树
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
    
    return true;
}