设计算法求二叉树所包含的度为1的结点的数目。(给出设计思想，再用代码实现)

Question

急用啊！！！谢谢各位大侠，要详细昂....

Answer 1

1、先序遍历的方式创建一棵二叉树

2、先序遍历的方式查找该二叉树，如果结点的度为1，则counts++。

3、代码如下：

　　#include<stdio.h>#include<malloc.h>

　　#define Max_size 1000

　　struct Tree{//存节点信息

　　 char ch;

　　 Tree *l,*r;

};

 

　　Tree *root;

　　struct Queue{//队列

　　 Tree *data;

}ar[Max_size];

 

　　void set(Tree *&t){//开辟空间

　　 t=(Tree *)malloc(sizeof(Tree));

　　 t->l=NULL;

　　 t->r=NULL;

}

 

　　char k[10];

　　void BuildTwoTree(Tree *p,char ch){//前序建树

　　 p->ch=ch;

　　 printf("%c的左儿子的值是（0为空）:",ch);

　　 scanf("%s",k);

　　 if(k[0]!='0'){

　　  set(p->l);

　　  BuildTwoTree(p->l,k[0]);

　　 }

　　 printf("%c的右儿子的值是（0为空）:",ch);

　　 scanf("%s",k);

　　 if(k[0]!='0'){

　　  set(p->r);

　　  BuildTwoTree(p->r,k[0]);

　　 }

}

 

　　int node1(Tree *p)

　　{

　　 int nodes = 0;

　　 int counts = 0;

　　 if(p == NULL)

　　  return 0;

　　 if(p->l!=NULL)

　　 {

　　  nodes++;

　　  counts+=node1(p->l);

　　 }

　　 if(p->r!=NULL)

　　 {

　　  nodes++;

　　  counts+=node1(p->r);

　　 }

　　 if(nodes == 1)

         counts++;

 

　　 return counts;

}

　　int main(){

　　 set(root);

　　 printf("先序创建二叉树，输入0表示该结点为空)。。。。。。\n");

　　 printf("根节点的值为(0表示根结点为空):");

　　 scanf("%s",k);

　　 BuildTwoTree(root,k[0]);

        printf("此二叉树中度为1的结点的数目为:%d\n",node1(root));

 

　　 return 0;

}

4、运行效果如下：