求二叉树的深度、总结点数和叶子结点数

二叉树的二叉链表的存储结构：

---

typedef   char   TElemType;

typedef   struct    BiTNode

{

             TElemType data;//数据元素

             BiTNode  *  lchild;//指向左孩子

              BiTNode  *  rchild;//指向右孩子

}BiTNode,* BiTree;

---

---

一、二叉树的深度

如果二叉树为空，结点的深度为0；

如果二叉树只有一个结点G为例，其中，它的左右子树的深度为0；而这种情况二叉树的深度为1。

如果二叉树有两个结点D，G为例，其中，以D为根结点的二叉树的左子树的深度为0，右子树的深度为（0+1）；而这种情况二叉树的深度为2。

…………

如果二叉树有n个结点,二叉树的深度为二叉树左右子树深度的最大值+1。

代码：

int Depth(BiTree T)

{

                     int m,n;

                     if(!T)                                                   return 0;

                     if(!T->lchild && !T->rchild)           return 1;

                     else

                     {

                                    m = Depth(T->lchild);

                                    n = Depth(T->rchild);

                                     return 1+(m>n?m:n);

                        }

}

---

二、二叉树的叶子结点数

如果二叉树为空，二叉树的叶子结点数为0；

如果二叉树只有一个结点G（左右子树为空）为例，而这种情况二叉树的叶子结点数为1。

如果二叉树有两个结点D（右子树为非空），G（左右子树为空）为例，其中，以D为根结点的二叉树的左子树的叶子结点数为0，右子树的叶子结点数为1；而这种情况二叉树的叶子结点数为1。

…………

如果二叉树有n个结点,二叉树的叶子结点数为二叉树左右子树叶子结点数的和。

代码：

int CountLeaf(BiTree T)

{

                             int m,n;

                             if(!T)                                                             return 0;

                              if(!T->lchild && !T->rchild)                   return 1;

                              else

                             {

                                            m = CountLeaf(T->lchild);

                                             n = CountLeaf(T->rchild);

                                             return m+n;

                                }

}

---

三、二叉树的结点数

如果二叉树为空，二叉树的结点数为0；

如果二叉树只有一个结点G（左右子树为空）为例，而这种情况二叉树的结点数为1。

如果二叉树有两个结点D（右子树为非空），G（左右子树为空）为例，其中，以D为根结点的二叉树的左子树的结点数为0，右子树的结点数为1；而这种情况二叉树的结点数为2。

…………

如果二叉树有n个结点,二叉树的结点数为二叉树左右子树结点数的和+1（根结点）。

代码：

int Count(BiTree T)

{

                       int m,n;

                       if(!T)                                                      return 0;

                        if(!T->lchild && !T->rchild)            return 1;

                        else

                       {

                                    m = Count(T->lchild);

                                    n = Count(T->rchild);

                                    return m+n+1;

                      }

}