树的建立与基本操作

亦凉 2022-06-02 07:23 150阅读 0赞

在本实验中，程序的输入是一个表示树结构的广义表。假设树的根为 root ，其子树森林 F ＝ （ T1 ， T2 ， ... ， Tn ），设与该树对应的广义表为 L ，则 L ＝（原子，子表 1 ，子表 2 ， ... ，子表 n ），其中原子对应 root ，子表 i （ 1<i<=n ）对应 Ti 。例如：广义表 (a,(b,(c),(d)),(f,(g),(h ),(i))) 表示的树如图所示：

![zhong1.jpg][]

程序的输出为树的层次结构、树的度以及各种度的结点个数。

在输出树的层次结构时，先输出根结点，然后依次输出各个子树，每个子树向里缩进 4 个空格，如：针对上图表示的树，输出的内容应为：

Degree of tree: 3

Number of nodes of degree 0: 5

Number of nodes of degree 1: 0

Number of nodes of degree 2: 2

Number of nodes of degree 3: 1

**例：** （下面的黑体为输入）

**(a,(b),(c,(d),(e,(g),(h )),(f)))**

Degree of tree: 3

Number of nodes of degree 0: 5

Number of nodes of degree 1: 0

Number of nodes of degree 2: 2

Number of nodes of degree 3: 1

<table style="color:rgb(68,68,68); font-size:13px; line-height:25px; width:1615px; margin-bottom:20px; background-color:transparent"> 
 <thead> 
 <tr> 
 <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> &nbsp;</th> 
 <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 测试输入<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=input&amp;lang=zh_cn" title="关于“测试输入”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“测试输入”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></th> 
 <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 期待的输出<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=expectedoutput&amp;lang=zh_cn" title="关于“期待的输出”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“期待的输出”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></th> 
 <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 时间限制<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=timelimit&amp;lang=zh_cn" title="关于“时间限制”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“时间限制”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></th> 
 <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 内存限制<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=memlimit&amp;lang=zh_cn" title="关于“内存限制”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“内存限制”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></th> 
 <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 额外进程<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=nproc&amp;lang=zh_cn" title="关于“{$a} 个额外进程”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“{$a} 个额外进程”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 测试用例 1</td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64767&amp;test=82486&amp;type=in&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
 <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
 <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> (a,(b),(c,(d),(e,(g),(h)),(f)))↵</li> 
 </ol> 
 </div> </td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64767&amp;test=82486&amp;type=out&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
 <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
 <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> a↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;b↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;c↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;g↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Degree&nbsp;of&nbsp;tree:&nbsp;3↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;nodes&nbsp;of&nbsp;degree&nbsp;0:&nbsp;5↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;nodes&nbsp;of&nbsp;degree&nbsp;1:&nbsp;0↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;nodes&nbsp;of&nbsp;degree&nbsp;2:&nbsp;2↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;nodes&nbsp;of&nbsp;degree&nbsp;3:&nbsp;1↵</li> 
 </ol> 
 </div> </td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 1秒</td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 64M</td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 0</td> 
 </tr> 
 <tr> 
 <td style="padding:4px; line-height:20px; vertical-align:middle"> 测试用例 2</td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64767&amp;test=82487&amp;type=in&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
 <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
 <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> (a,(b,(c,(d),(e)),(f)),(g,(h),(i)),(j,(k,(m),(n),(o),(p,(r)))))↵</li> 
 </ol> 
 </div> </td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64767&amp;test=82487&amp;type=out&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
 <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
 <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> a↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;b↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;g↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;j↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;n↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;o↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Degree&nbsp;of&nbsp;tree:&nbsp;4↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;nodes&nbsp;of&nbsp;degree&nbsp;0:&nbsp;9↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;nodes&nbsp;of&nbsp;degree&nbsp;1:&nbsp;2↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;nodes&nbsp;of&nbsp;degree&nbsp;2:&nbsp;3↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;nodes&nbsp;of&nbsp;degree&nbsp;3:&nbsp;1↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;nodes&nbsp;of&nbsp;degree&nbsp;4:&nbsp;1↵</li> 
 </ol> 
 </div> </td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle"> 1秒</td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle"> 64M</td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle"> 0</td> 
 </tr> 
 <tr> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 测试用例 3</td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64767&amp;test=82488&amp;type=in&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
 <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
 <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> (a,(b),(c),(d,(m),(n)),(e,(o)),(f),(h))↵</li> 
 </ol> 
 </div> </td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64767&amp;test=82488&amp;type=out&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
 <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
 <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> a↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;b↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;c↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;d↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;n↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;e↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;o↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;f↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> &nbsp;&nbsp;&nbsp;&nbsp;h↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Degree&nbsp;of&nbsp;tree:&nbsp;6↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;nodes&nbsp;of&nbsp;degree&nbsp;0:&nbsp;7↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;nodes&nbsp;of&nbsp;degree&nbsp;1:&nbsp;1↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;nodes&nbsp;of&nbsp;degree&nbsp;2:&nbsp;1↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;nodes&nbsp;of&nbsp;degree&nbsp;3:&nbsp;0↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;nodes&nbsp;of&nbsp;degree&nbsp;4:&nbsp;0↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;nodes&nbsp;of&nbsp;degree&nbsp;5:&nbsp;0↵</li> 
 <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> Number&nbsp;of&nbsp;nodes&nbsp;of&nbsp;degree&nbsp;6:&nbsp;1↵</li> 
 </ol> 
 </div> </td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 1秒</td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 64M</td> 
 <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 0</td> 
 </tr> 
 </tbody> 
</table>

建这种一个节点有多棵子树的树时，可采用FirstChild-NextSibling Representation方法建树。具体的操作就是用到栈和队列来建树。这题我偷懒了，用的是C++的STL，老师课上应该栈和队列用纯C的函数来实现的。

#include<cstdio> 
 #include<string> 
 #include<map> 
 #include<queue> 
 #include<stack> 
 #include<math.h> 
 #include<iostream> 
 #define MAXN 200 
 using namespace std; 
 typedef char ElementType; 
 struct TreeNode 
 { 
 int degree; 
 int level; 
 ElementType Element; 
 struct TreeNode *FirstChild; 
 struct TreeNode *NextSibling; 
 }; 
 typedef struct TreeNode *Position, *Tree; 
 queue<Tree> Q; stack<Tree> S; 
 int ceng; 
 int Degree_Tree = 0; 
 int dgree[100]; 
 int Getmax(int a, int b) 
 { 
 return a > b ? a : b; 
 } 
 Tree CreatTree(Tree T, char letter[]) //用到了栈和队列
 { 
 int i = 0; 
 for (; letter[i]; i++) 
 { 
 if (letter[i] == '(') 
 { 
 ceng++; 
 continue; 
 } 
 else if (letter[i] == ',') 
 continue; 
 else if (letter[i] == ')') 
 { 
 ceng--; 
 continue; 
 } 
 else 
 { 
 Tree t = (Tree)malloc(sizeof (struct TreeNode)); 
 t->Element = letter[i]; 
 t->FirstChild = t->NextSibling = NULL; 
 t->level = ceng; 
 t->degree = 0; 
 Q.push(t); 
 } 
 } 
 while (!Q.empty()) 
 { 
 if (Q.front()->level > S.top()->level) 
 { 
 S.top()->FirstChild = Q.front(); 
 S.push(Q.front()); 
 Q.pop(); 
 } 
 else if (Q.front()->level == S.top()->level) 
 { 
 S.top()->NextSibling = Q.front(); 
 S.push(Q.front()); 
 Q.pop(); 
 } 
 else 
 { 
 //int num = 0; 
 while (Q.front()->level < S.top()->level) 
 { 
 S.pop();// num++; 
 } 
 //S.top()->degree += num; 
 } 
 } 
 return T; 
 } 
 void Printline(Tree T,int depth) 
 { 
 for (int i = 0; i < depth; i++) 
 printf(" "); 
 printf("%c\n", T->Element); 
 } 
 void ListTree(Tree T,int depth) 
 { 
 Tree C; 
 if (T) 
 { 
 Printline(T,depth); 
 if (T->FirstChild) 
 { 
 for (C = T->FirstChild; C; C = C->NextSibling) 
 { 
 ListTree(C, depth + 1); 
 (T->degree)++; 
 } 
 } 
 dgree[T->degree]++; 
 Degree_Tree=max(Degree_Tree, T->degree); 
 } 
 } 
 
 int main() 
 { 
 //freopen("1.txt", "r", stdin); 
 Tree t = (Tree)malloc(sizeof (struct TreeNode)); 
 t->FirstChild = t->NextSibling = NULL; 
 t->level = 0; 
 S.push(t); 
 char letter[200]; 
 gets(letter); 
 Tree root= CreatTree(t, letter)->FirstChild; 
 ListTree(root,0); 
 printf("Degree of tree: %d\n",Degree_Tree); 
 for (int i = 0; i <= Degree_Tree; i++) 
 { 
 printf("Number of nodes of degree %d: %d\n",i,dgree[i]); 
 } 
 }

[zhong1.jpg]: http://online.bit.edu.cn/moodle/pluginfile.php/161850/mod_programming/intro/zhong1.jpg