swust oj 981

统计利用二叉树存储的森林中树的棵数

1000(ms)

10000(kb)

2919 / 5436

普通树及其构成的森林均可转换成相应的二叉树，反之亦然。故而可以根据相应的转换方法去统计某一二叉树对应的森林中树的棵数。相应的二叉树可利用先序递归遍历算法创建。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符"#"时表示该结点不需要创建，否则创建该结点。最后再统计该二叉树对应的森林中树的棵数。需要注意输入数据序列中的"#"字符和非"#"字符的序列及个数关系，这会最终决定创建的二叉树的形态（序列里面允许无效字符但需要正确处理）。

输入

输入为接受键盘输入的由大写英文字符和"#"字符构成的一个字符串（用于创建对应的二叉树）。

输出

输出该用例对应的二叉树表示的森林中树的棵数。

样例输入

A#B#CD###
ABC####
AB##C##
ABCD###EF##G##H##
A##B##

样例输出

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<cstdio>
  6 typedef char Datetype;
  7 using namespace std;
  8 int x;
  9 
 10 typedef struct link{
 11     Datetype date;
 12     struct link *lchild;
 13     struct link *rchild;
 14 }tree;
 15 
 16 typedef struct queue{
 17     tree *data;
 18     struct queue *next;
 19 }que;
 20 
 21 typedef struct {
 22     que *front;
 23     que *rear;
 24 }lin;
 25 
 26 void Initqueue(lin *&L)
 27 {
 28     L=(lin *)malloc(sizeof(lin));
 29     L->front=L->rear=NULL;
 30 }
 31 
 32 void destroyed(lin *&L)
 33 {
 34     que *p=NULL,*r=NULL;
 35     p=L->front;
 36     while(p!=NULL)
 37     {
 38         r=p;
 39         p=p->next;
 40         free(r);
 41     }
 42     free(L);
 43 }
 44 
 45 bool pop(lin *&L, tree *&e)
 46 {
 47     que *p;
 48     if(L->rear==NULL)
 49         return false;
 50     p=L->front;
 51     if(L->rear==L->front)
 52         L->front=L->rear=NULL;
 53     else
 54         L->front=p->next;
 55     e=p->data;
 56     free(p);
 57     return true;
 58 }
 59 
 60 int empty(lin *&L)
 61 {
 62     return (L->rear==NULL);
 63 }
 64 
 65 void push(lin *&L,tree *e)
 66 {
 67     que *p;
 68     p = (que *)malloc(sizeof(que));
 69     p->data=e;
 70     p->next=NULL;
 71     if(L->rear==NULL)
 72     {
 73         L->front=p;
 74         L->rear=p;
 75     }
 76     else
 77     {
 78         L->rear->next=p;
 79         L->rear=p;
 80     }
 81 }
 82 
 83 void creattree(tree *&L)
 84 {
 85     char c;
 86     cin>>c;
 87     if(c=='#')
 88         L=NULL;
 89     else
 90     {
 91         L = (tree *)malloc(sizeof(tree)) ;
 92         L->date=c;
 93         creattree(L->lchild);
 94         creattree(L->rchild);
 95     }
 96 }
 97 
 98 void find(tree *L)
 99 {
100     if(L!=NULL)
101     {
102         x++;
103         find(L->rchild);
104     }
105 }
106 
107 void destroytree(tree *&L)
108 {
109     if(L!=NULL)
110     {
111         destroytree(L->lchild);
112         destroytree(L->rchild);
113         free(L);
114     }
115 }
116 
117 int deep(tree *L)
118 {
119     int ldep,rdep,max;
120     if(L!=NULL)
121     {
122         ldep=deep(L->lchild);
123         rdep=deep(L->rchild);
124         max=ldep>rdep?ldep+1:rdep+1;
125         return max;
126     }
127     else
128         return 0;
129 }
130 
131 void run(tree *L)
132 {
133     tree *p=L;
134     lin *qu;
135     Initqueue(qu);
136     if(L!=NULL)
137         push(qu,p);
138     while(!empty(qu))
139     {
140         pop(qu,p);
141         cout<<p->date;
142         if(p->lchild!=NULL)
143             push(qu,p->lchild);
144         if(p->rchild!=NULL)
145             push(qu,p->rchild);
146     }
147     destroyed(qu);
148 }
149 
150 int main()
151 {
152     tree *L = NULL;
153     x=0;
154     creattree(L);
155     find(L);
156     cout<<x;
157     destroytree(L);
158     return 0;
159 }