例如 01*49**8**25**6** ABD***CE**FG*** 01*49**8**25**6*37*** 

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. #include<malloc.h>  
4. #define ERROR -1  
5. typedef char DataType;  
6. typedef struct TreeNode  
7. {  
8.     DataType elem;  
9.     struct TreeNode* rchild;  
10.     struct TreeNode* lchild;  
11. }TreeNode, *PTREE;  
12. //先序创建  
13. void CreatTree(PTREE *Root) {  
14.     char val = 0;//用于下面存放数据  
15.     val = getchar();//输入数据值  
16.     //如果输入'*'，则指向为空  
17.     if (val == '*'|| val == '#' || val == '.')  
18.         (*Root) = NULL;  
19.     //如果输入非'*'，则给数据域赋值  
20.     else {  
21.         (*Root) = (PTREE)malloc(sizeof(TreeNode));//申请内存空间  
22.         if ((*Root) == NULL) {  
23.             printf("创建结点失败，无法分配可用内存...");  
24.             exit(-1);  
25.         }  
26.         else {  
27.             (*Root)->elem = val;//给结点数据域赋值  
28.             CreatTree(&(*Root)->lchild);  
29.             CreatTree(&(*Root)->rchild);  
30.         }  
31.     }  
32. }  
33. //前序遍历  
34. void PreOrderTree(PTREE Root) {  
35.   
36.     if (Root == NULL)  
37.         return;  
38.     else {  
39.         putchar(Root->elem);  
40.         PreOrderTree(Root->lchild);  
41.         PreOrderTree(Root->rchild);  
42.   
43.     }  
44. }  
45. //结点个数01*49**8**25**6** ABD***CE**FG*** 01*49**8**25**6*37***  
46. int GetNodeNum(PTREE Tree)  
47. {  
48.     if (NULL == Tree)  
49.     {  
50.         return 0;  
51.     }  
52.     else  
53.     {  
54.         return GetNodeNum(Tree->lchild) + GetNodeNum(Tree->rchild) + 1;  
55.     }  
56. }  
57. //叶子结点个数  
58. int GetLeafNum(PTREE Tree)  
59. {  
60.     if (Tree == NULL)  
61.         return 0;  
62.     if (Tree->lchild == NULL&&Tree->rchild == NULL)  
63.         return 1;  
64.     return GetLeafNum(Tree->lchild) + GetLeafNum(Tree->rchild);  
65. }  
66. //度为1结点个数  
67. int GetNodde1Num(PTREE Tree)  
68. {  
69.     if (Tree == NULL)  
70.   
71.         return 0;  
72.   
73.     if (Tree->lchild == NULL&&Tree->rchild != NULL || Tree->rchild == NULL&&Tree->lchild != NULL)  
74.   
75.         return 1 + GetNodde1Num(Tree->lchild) + GetNodde1Num(Tree->rchild);  
76.     return GetNodde1Num(Tree->lchild) + GetNodde1Num(Tree->rchild);  
77. }  
78. //度为2结点个数  
79. int GetNodde2Num(PTREE Tree)  
80. {  
81.     if (Tree == NULL)  
82.         return 0;  
83.     if (Tree->lchild != NULL&&Tree->rchild != NULL)  
84.         return 1+ GetNodde2Num(Tree->lchild) + GetNodde2Num(Tree->rchild);  
85.     return GetNodde2Num(Tree->lchild) + GetNodde2Num(Tree->rchild);  
86. }  
87.   
88. int main(void)  
89. {  
90.     PTREE root;  
91.     printf("请输入前序 *或#或.为空\t");  
92.     CreatTree(&root);  
93.     printf("前序遍历 ：\t");  
94.     PreOrderTree(root);  
95.     printf("\n");  
96.     printf("递归求所有结点 %d\n", GetNodeNum(root));  
97.     printf("等式求所有结点 %d\n", GetLeafNum(root)+ GetNodde2Num(root) + GetNodde1Num(root));  
98.     printf("递归求所有叶子结点 %d\n", GetLeafNum(root));  
99.     printf("性质求所有叶子结点 %d\n", GetNodde2Num(root)+1);  
100.     printf("递归求所有度为1的结点 %d\n", GetNodde1Num(root));  
101.     printf("等式求所有度为1的结点 %d\n", GetNodeNum(root)- GetLeafNum(root)- GetNodde2Num(root));  
102.     printf("递归求所有度为2的结点 %d\n", GetNodde2Num(root));  
103.     printf("性质求所有度为2的结点 %d\n", GetLeafNum(root)-1);  
104.     printf("总结： 根据书中的性质3和一个等式，只要有两个数据（度2和度0算一个），其他数据都可以算出\n");  
105.     system("pause");  
106.     return 0;  
107. }  

 

档铺网——在线文档免费处理