设二叉树以二叉链表存储，根结点的指针为T，结点的结构为BiTree(child,datarchild),其中 lchild, rchild分别存储结点左、右孩子的地址，data域存放结点的数据信息、为int型数据。试设计算法求此二叉树上有孩子结点且数据域大于所有孩子结点数据域的结点个数，函数声明如下，并加入简要的注释或说明。(10分) int Count(BiTree T)

算法思路：

1. 对于一个结点，如果其不存在左右孩子，则返回0。

2. 如果其存在左右孩子，则分别递归处理左右子树。

3. 对于当前结点，判断其数据域是否大于左右孩子的数据域。如果是，则计数器加1。

4. 将左右子树的结果加起来，作为当前结点的子树中符合条件的结点个数。

5. 返回符合条件的结点总数。

算法实现：

int Count(BiTree T)
{
    if(T == NULL || (T->lchild == NULL && T->rchild == NULL)) //如果当前结点不存在孩子或只有一个孩子，返回0
    {
        return 0;
    }
    int count = 0; //符合条件的结点个数
    if(T->lchild != NULL && T->lchild->data < T->data) //判断左孩子是否符合条件
    {
        count++;
    }
    if(T->rchild != NULL && T->rchild->data < T->data) //判断右孩子是否符合条件
    {
        count++;
    }
    //递归处理左右子树，并将结果加起来
    return count + Count(T->lchild) + Count(T->rchild);
}

注：代码中的`BiTree`是结构体类型，函数返回类型应为`int`。

相关问题

设二叉树采用二叉链表存储结构，二叉链表的格式定义为

二叉链表存储结构的格式定义如下：

typedef struct BiTNode{
    TElemType data;             // 数据域
    struct BiTNode *lchild;     // 左孩子指针
    struct BiTNode *rchild;     // 右孩子指针
}BiTNode, *BiTree;

其中，`TElemType`为二叉树节点存储的数据类型，`lchild`和`rchild`分别指向节点的左孩子和右孩子。`BiTNode`为节点结构体类型，`BiTree`为指向节点的指针类型，也就是指向二叉树根节点的指针类型。

//算法5.6 统计二叉树中结点的个数 #include<iostream> using namespace std; //二叉树的二叉链表存储表示 typedef struct BiNode 1 char data; //结点数据域 struct BiNode *lchild,*rchild; //左右孩子指针 ] BiTNode,*BiTree; //用算法5.3建立二叉链表 void CreateBiTree(BiTree &T) //用算法5.3建立二叉链表 void CreateBiTree(BiTree &T) //按先序次序输入二叉树中结点的值(一个字符)，创建二叉链表表示的二叉树T char ch; cin >> ch; if(ch=='#') T=NULL; //递归结束，建空树 else T=new BiTNode; T->data=ch; //生成根结占 CreateBiTree(T->lchild). /递归创建左子树 CreateBiTree(T->rchild); /递归创建右子树 //else ) //CreateBiTree //else ) //CreateBiTree int NodeCount(BiTree T) if(T==NULL) return 0; 如果是空树，则结点个数为0，递归结束 else return NodeCount(T->lchild)+ NodeCount(T->rchild) +1; //否则结点个数为左子树的结点个数+右子树的结点个数+1 void main() void main() BiTree tree; cout<<"请输入建立二叉链表的序列：\n"； CreateBiTree(tree); cout<<"结点个数为： "<<NodeCount(tree)<<endl; )

这段代码是用来统计二叉树中结点个数的，使用的是二叉链表存储结构。其中CreateBiTree函数用来建立二叉树，按照先序遍历的顺序输入二叉树中结点的值，如果输入的是'#'代表该节点为空。NodeCount函数用来递归计算二叉树中结点的个数，如果是空树，返回0；否则返回左子树的结点个数+右子树的结点个数+1。最后在主函数中调用CreateBiTree和NodeCount函数，并输出结果。