问题描述

完全二叉树的计算结点总数算法

/**

• 定义二叉树的结点如下
• struct TreeNode {
• int val;
• struct TreeNode *left;
• struct TreeNode *right;
• };
  /
  算法如下：
  int countNodes(struct TreeNode root) {
  if(root==NULL)//如果传进一棵空树
  return 0;
  if(root->left==NULL)//如果传进一棵只有根结点的树木
  return 1;
  if(root->right==NULL)//如果这颗树就只有一颗子树
  return 2;
  return (countNodes(root->left)+countNodes(root->right)+1);
  }
  该算法在OJ上面判断出错，说是算法时间超出限制，求解，这个算法错在哪里。

解决方案

int countNodes(struct TreeNode *root)
{

if(root!=NULL)
{
  if(root->left==NULL&&root->right==NULL)//叶子节点
      return 1;
  else //其中至少一个子树不为空，那就意味着可能有多个节点。
      //总节点数是左子树节点数+右子树节点数+1（自身节点）
      return countNodes(root->left)+countNodes(root->right)+1;

}else//如果为空，则说明不存在这个节点，故返回零。
    return 0;

}

您的算法有缺陷的，如楼上所述。
if(root->left==NULL)//如果传进一棵只有根结点的树木 return 1; if(root->right==NULL)//如果这颗树就只有一颗子树 return 2;

这两个if语句是不妥的。

解决方案二：

函数定义不对，应该用指针：int countNodes(struct TreeNode root)

解决方案三：

http://wenku.baidu.com/link?url=ebcfCOsXY-KZ8DnOipbGoqsZerG9Z8wCN6KMO8kuqaTq48ziiqRZTyiFML8nmn-XKICwsP2hnLvMDi3VhuJ4QRoB9hYfmf81yeBGJt8Zkwe

解决方案四：

其实我想要的是算法的分析，各位大神可不可以不要复制黏贴代码，小弟学习数据结构，想要的是解题思路，还有，我怎么看也看不出我的算法那有问题

解决方案五：

应该是分支没有写正确的原因， 三个if都在进行，而不是进入一个两外两个就不进行了，可能是这的问题。试试把代码改成这样

 int countNodes(struct TreeNode root)
{
    if(root==NULL)//如果传进一棵空
    {
        return 0;
    }
    else if(root->left==NULL)//如果传进一棵只有根结点的树木
    {
        return 1;
    }
    else if(root->right==NULL)//如果这颗树就只有一颗子树
    {
        return 2;
    }
    else
    {
        return (countNodes(root->left)+countNodes(root->right)+1);
    }
 }

解决方案六：

楼主 你的算法是有问题的，例如像这样一棵树

           0
            /
        0
       /
     0
     /
 0

只有左孩子，直接在判断右孩子为空的时候就return了。还是分支的问题。

解决方案七：

 #include<stdio.h>

struct BiTree{

    char data;

    struct BiTree *lchild;

    struct BiTree *rchild;

};

struct BiTree* CreatBiTree(){

    char x;

    struct BiTree* p;

    scanf("%c",&x); 

    if(x!='.'){

      p=(struct BiTree*)malloc(sizeof(struct BiTree));

      p->data=x;

      p->lchild=CreatBiTree();

      p->rchild=CreatBiTree();

}

    else

      p=NULL;

      return p;

}

int LeafNum(struct BiTree *T){

    if(!T)

      return 0;

    else

      if(!T->lchild&&!T->rchild)

        return 1;

      else

        return LeafNum(T->lchild)+LeafNum(T->rchild);

}

int main(){

   int num;

   struct BiTree* T;

   printf("Please input the tree(pre):
");

   T=CreatBiTree();

   while(T==NULL){

     printf("empoty,again:
");

       T=CreatBiTree();                                 

       }

   num=LeafNum(T);

   printf("
the sum of leaf is:%d
",num);

   getch();

}

解决方案八：

我觉得使用层次遍历更好。1、使用递归可能会使得超时，所以使用循环。2.对于层次遍历，循环是非常合适的，而对于深度遍历，递归是比较合适的。

解决方案九：

二叉树结点的计算
编写递归算法，计算二叉树中叶子结点的数目