Question

求 数据结构(C语言版) 二叉树叶子结点总数和二叉树结点总数（分两题）

明天就要交作业了。求大家。要代码列出来啊，或者传我也可以，Q404031515.

Answer 1

完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。 更确切地说，如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。 可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0＝n2＋1，则n= n0＋n1＋n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1－1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合并成一个公式：n0＝?（n＋1）/2 ?，就可根据完全二叉树的结点总数计算出叶子结点数。

Answer 2

typedef char DataType;//定义DataType类型 typedef struct node{ DataType data; struct node *lchild, *rchild;//左右孩子子树 }BinTNode; //结点类型 typedef BinTNode *BinTree;//二叉树类型 int Node(BinTree T) { //算结点数 if(T) return Node(T->lchild ) + Node ( T->rchild )+1; else return 0; } int Leaf(BinTree T) { if(T) { if ((T->lchild==NULL )&&( T->rchild==NULL ) ) return 1; else return Leaf(T->lchild ) +Leaf ( T->rchild ); } else return 0; }