程序控

IPPP (Institute of Penniless Peasent-Programmer) Fellow

:: :: :: :: :: :: :: ::
 77 随笔 :: 0 文章 :: 442 评论 :: 0 引用

Background背景

Trees are fundamental in many branches of computer science. Current state-of-the art parallel computers such as Thinking Machines' CM-5 are based on fat trees. Quad- and octal-trees are fundamental to many algorithms in computer graphics.

This problem involves building and traversing binary trees.

The Problem问题

Given a sequence of binary trees, you are to write a program that prints a level-order traversal of each tree. In this problem each node of a binary tree contains a positive integer and all binary trees have have fewer than 256 nodes.

In a level-order traversal of a tree, the data in all nodes at a given level are printed in left-to-right order and all nodes at level k are printed before all nodes at level k+1.

For example, a level order traversal of the tree

is: 5, 4, 8, 11, 13, 4, 7, 2, 1.

In this problem a binary tree is specified by a sequence of pairs (n,s) where n is the value at the node whose path from the root is given by the string s. A path is given be a sequence of L's and R's where L indicates a left branch and R indicates a right branch. In the tree diagrammed above, the node containing 13 is specified by (13,RL), and the node containing 2 is specified by (2,LLR). The root node is specified by (5,) where the empty string indicates the path from the root to itself. A binary tree is considered to be completely specified if every node on all root-to-node paths in the tree is given a value exactly once.

The Input输入

The input is a sequence of binary trees specified as described above. Each tree in a sequence consists of several pairs (n,s) as described above separated by whitespace. The last entry in each tree is (). No whitespace appears between left and right parentheses.

All nodes contain a positive integer. Every tree in the input will consist of at least one node and no more than 256 nodes. Input is terminated by end-of-file.

The Output输出

For each completely specified binary tree in the input file, the level order traversal of that tree should be printed. If a tree is not completely specified, i.e., some node in the tree is NOT given a value or a node is given a value more than once, then the string "not complete" should be printed.

Sample Input输入示例

(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()

Sample Output输出示例

5 4 8 11 13 4 7 2 1
not complete

Solution解答

#include <iostream>
#include <list>
#include <string>
#include <sstream>
using namespace std;
//节点结构体，存储节点的值及左右子节点
struct NODE {int nVal; NODE *pL; NODE *pR;}
//NullNode为空节点标本
const NullNode = {0, 0, 0};
//删除树
void DeleteTree(NODE *pPar) {
if (pPar != NULL) {
//深度遍例删除左右子节点
DeleteTree(pPar->pL), DeleteTree(pPar->pR);
}
delete pPar;
}
//为树增加节点
NODE* AddChild(NODE *pPar, int nVal, const char *pPath) {
//如果父为空，则建立父节点
if (pPar == 0) {
pPar = new NODE(NullNode);
}
//根据当前路径字符串做不同操作
switch (*pPath) {
//遇到右括号，说明路径结束，为当前父节点赋值
case ')': pPar->nVal = (pPar->nVal == 0 && nVal != 0) ? nVal : -1; break;
//继续建立左/右子节点
case 'L': pPar->pL = AddChild(pPar->pL, nVal, pPath + 1); break;
case 'R': pPar->pR = AddChild(pPar->pR, nVal, pPath + 1); break;
}
return pPar;
}
//主函数
int main(void) {
//树的根结点
NODE *pRoot = 0;
//循环处理输入的每一个节点数据
for (string strToken; cin >> strToken;) {
//获得节点数据字符串指针
const char *pStr = strToken.c_str();
int nLen = strToken.length(), nVal = 0;
//如果第二个字符不是右括号，则添加节点后继续输入
if (pStr[1] != ')') {
//将字符串转为数字
for (; isdigit(*++pStr); nVal = nVal * 10 + *pStr - '0');
if (*pStr != ',') while(true);
//在树中添加该节点
continue;
} //如果第二字符是右括号，说明一棵树输入结束，进行遍例
list<NODE*> Level(1, pRoot);
stringstream ssResult;
//依次遍例每一层。用Level存储一层的节点，Level非空则继续遍例
for (list<NODE*>::iterator i = Level.begin(); !Level.empty();
//如果一层遍例结束，则回到起点
i = (i == Level.end() ? Level.begin() : i)) {
//移除当前节点
NODE *pTemp = *i;
i = Level.erase(i);
//如果该节点为空，则直接继续进行下一个节点
if (pTemp == 0) {
continue;
}//否则在原位置上增加子节点
//如果该节点的值小于或等于0，说明其重复定义或未定义
if (pTemp->nVal <= 0) {
//清空数据，返回错误。
Level.clear();
ssResult.str("");
break;
}//正确的结点
//输入其值，并在原位置上插入其子节点
ssResult << pTemp->nVal << ' ';
i = Level.insert(i, pTemp->pL), ++i;
i = Level.insert(i, pTemp->pR), ++i;
}
//删除原树，避免内存泄露。
DeleteTree(pRoot);
pRoot = 0;
strToken = ssResult.str();
//如果结果为空，说明所给数据有错
if (strToken.empty()) {
strToken = "not complete";
} //对于正确结果要去掉最后的一个空格
else {
strToken.erase(strToken.end() - 1);
}
//输出结果
cout << strToken << endl;
}
return 0;
}
posted on 2010-08-15 19:15  Devymex  阅读(...)  评论(...编辑  收藏