[数据结构与算法]树的三种基本操作

求叶子结点的数目

用任何一种递归算法 凡是左右指针均为空的 是叶子 统计数目即可

int sum=0;
void countLeaf(BiTNode *T,int *sum)
{
    if(!T)
    {
        if(!T->lchild && !T->rchild)
        {
            (*sum)++;    //指针指向的数据+1
        }
        if(T->lchild)
        {
            countLeaf(T->lchild,sum);
        }
        if(T->rchild)
        {
            countLeaf(rchild,sum);
        }
    }
}

copy二叉树

BiTNode * CopyTree(BiTNode *T)
{
    BiTNode *newNode = NULL:
    BiTNode *newLp = NULL;
    BiTNode *newRp = NULL;
    if(!T)
    { 
        return NULL;
    }
    //copy 左子树
    if(!T->lchild)
    {
        newLp = CopyTree(T->lchild); //copy左子树
    }
    else
    {
        newLp = NULL;
    }

    //copy 右子树
    if(!T-> rchild)
    {
        newRp = CopyTree(T->rchild);
    }
    else
    {
        newRp = NULL;
    }
    
    //malloc根节点
    newNode =(BiTnode*) malloc(sizeof(BiTNode));
    if(newNode == NULL)
    {
        return NULL;
    }
    newNode->lchild = newLp;
    newNode->rchild = newRp;
    newNode->data = T->data;
    return newNode;
}

求树的深度

int Depth(BiTNode *T)
{
    int deptleft = 0;
    int deptright =0;
    int deptvalue = 0;
    
    if(!T)
    {
        deptvalue = 0;
        return deptvalue;
    }
    deptleft = Depth(T->lchild);
    deptright = Depth(T->rchild);
    deptvalue = 1 + (deptleft>deptright?deptleft:deptright) ;
    return deptvalue;
}