按照先序序列创建二叉树T（结点值为字符型, 输入$表示空树），求二叉树的叶子结点数。 - C语言论坛

楼主

已结贴√ 问题点数：20 回复次数：3

按照先序序列创建二叉树T（结点值为字符型, 输入$表示空树），求二叉树的叶子结点数。

求源代码

搜索更多相关主题的帖子: 源代码　二叉树　叶子　

第 2 楼

得分:20

。。。貌似没有什么需要算法的东西。老老实实跟着题目的要求建立这颗二叉树，然后数一下有多少个结点就知道了。应该是没有捷径可走的。

φ(゜▽゜*)♪

第 3 楼

得分:0

回复 2楼书生牛犊

求叶子节点不会写，总是停止工作
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct Node
{
      int data;
      struct Node *lchild;
      struct Node *rchild;
}BiTree,*BiTNode;

BiTNode InitDSTable()
{
    char ch;
    BiTNode t;
    ch=getchar();
    if(ch=='$')
    {
         return NULL;
    }
    else
    {
      t=(BiTNode)malloc(sizeof(BiTree));
      t->data=ch;
      t->lchild=InitDSTable();
      t->rchild=InitDSTable();
    }
    return t;
}

//求叶子的结点数
int  n1=0;
void Count(BiTNode T)
{
     if((T->lchild=='$')&&(T->rchild=='$'))
              n1++;

     Count(T->lchild);
     Count(T->rchild);

}
int main()
{

      BiTNode T=InitDSTable();


      Count(T);
      printf("%d",n1);

      return 0;

}

第 4 楼

得分:0

回复 3楼 Ocean1

没测试数据。所以我就不改了。楼主自己看着注释想办法解决

程序代码：

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct Node
{
      int data;
      struct Node *lchild;
      struct Node *rchild;
}BiTree,*BiTNode;

BiTNode InitDSTable()
{
    char ch;
   

    ch=getchar();//你要提防getchar会不会读到‘\n’,这个字符可不能用于建树哦！

    if(ch=='$')
    { 

         return NULL;
    }
    else
    {BiTNode t=(BiTNode)malloc(sizeof(BiTree)); 

      t->data=ch;
      t->lchild=InitDSTable();
      t->rchild=InitDSTable();
      return t;
    }
   

}

//求叶子的结点数
int  n1=0;//C语言有一个叫做静态变量的东西，在Count里面定义一个static int n也可以计数。你现在用全局变量当然也没有错。我只是顺便提醒一下。
void Count(BiTNode T)
{
     if((T->lchild=='$')&&(T->rchild=='$'))//T的子节点怎么可能是个字符呢？T的子节点只能是个指针！要么为NULL要么是另一个结点！

              n1++;
        

     Count(T->lchild);//当T->lchild==NULL，汇发生什么事？ 你访问NULL->child会导致系统奔溃。

     Count(T->rchild);//而不断地访问NULL，也会导致Count函数不断递归，最终由于资源用尽死掉。


}


int main()
{    



      BiTNode T=InitDSTable();
     // PRD(T);//建议先序输出所先建立的二叉树，看看这棵树有没有建立正确。 如果建立正确，后面数数数错了我们也方便对症下药

    

      Count(T);
      printf("%d",n1);
    

      return 0;

}

φ(゜▽゜*)♪