UC知道有关数据结构中二叉树的一道算法题
来源：百度知道 编辑：UC知道 时间：2024/05/21 08:45:02
用C语言表示
typedef struct BiNode{
ElemType data data;
struct BiNode *lchild,*rchild;
int val;
}BiNode,*BiTree;
其中val域表示该结点的子孙（含孩子结点）的个数。开始时，val域值均为0，T为指向某二叉树根结点的指针。请写算法填写该二叉树中每个结点的val域。
typedef struct BiNode{
ElemType data data;
struct BiNode *lchild,*rchild;
int val;
}BiNode,*BiTree;
其中val域表示该结点的子孙（含孩子结点）的个数。开始时，val域值均为0，T为指向某二叉树根结点的指针。请写算法填写该二叉树中每个结点的val域。
一个递归函数就搞定了。
直接调用此函数。
int f(BiNode * t){
int n = 0;
if(t->lchild){//如果左儿子不为空，则孩子数加一
n++;
n += f(t->lchild);//对左子树采用同样的方式，并将儿子数加上左子树的儿子个数
}
if(t->rchild){){//如果右儿子不为空，则孩子数加一
n++;
n += f(t->rchild););//对右子树采用同样的方式，并将儿子数加上右子树的儿子个数
}
t->val = n;
return n;//返回儿子个数
}