从 C++ 中的 s 表达式构造二叉树
Construct binary tree from s-expression in c++
empty tree ::= ()
tree ::= empty tree | (w tree tree)
ex:
()
empty tree
(99(5()())(35(-5()())()))
99
/ \
5 35
/
-5
class Node
{
public:
int weight; // weight can be negative!
Node *left, *right;
Node():weight(0),left(NULL),right(NULL){}
Node(int d):weight(d),left(NULL),right(NULL){}
};
根据给定条件构造二叉树
我在构造它时遇到问题,我的程序会崩溃,我不知道为什么会这样,以下是我的代码,我打印出一些信息进行调试,取 (99(5()()) (35(-5()())())) 作为测试用例,它将打印出 99(5( 并且粉碎,我认为可能问题出在我处理的地方 ) 其中我 return 节点是NULL,但我找不到问题。顺便说一句,这棵树预计每棵树中有数百个节点,并且每个测试用例最多包含一万棵树,我会 运行 这个程序没时间了或者我需要做什么?谢谢你的时间
Node* MyBinaryTreeOps::constructTree(Node *root, std::string treeStr)const
{
int idex = 1;//always look at the treeStr[1]
Node *cur=NULL;//use to pass in recursive call
if(treeStr[idex]!='('&&treeStr[idex]!=')'){//meet number create new node
stringstream ss;
while(treeStr[idex]!='('){
ss<<treeStr[idex];
if(treeStr.size()>1){//if size > 1 then remove the treeStr[1],to let treeStr[1] become next char in treeStr
treeStr.erase(1,1);
}
}
int num=0;
ss>>num;
std::cout<<num<<std::endl;//print out just for debug
std::cout<<treeStr[idex]<<std::endl;//print out just for debug
root = new Node(num);
}
if(treeStr[idex]==')'){//meet ')' return subtree constructed
if(treeStr.size()>1){
treeStr.erase(1,1);
}
return root;
}
if(treeStr[idex]=='('){//meet first '(' then construct left subtree
if(treeStr.size()>1){
treeStr.erase(1,1);
}
root->left = constructTree(cur,treeStr);
}
if(treeStr[idex]=='('){ //meet second '(' then construct right subtree
if(treeStr.size()>1){
treeStr.erase(1,1);
}
root->right = constructTree(cur,treeStr);
}
if(treeStr[idex]==')'){ //meet ')' return subtree constructed
if(treeStr.size()>1){
treeStr.erase(1,1);
}
return root;
}
}
我自己试过这个问题,这是我写的函数。
算法步骤:
-
找到表示当前节点权重的序列的一部分。将其转换为 int 并分配给节点。
-
切片字符串以删除重量,开始和结束大括号。
-
遍历序列以找到分隔子节点的两个括号之间的点。
-
将子字符串拆分为两个序列(我们可以对起始树进行切片并将其重新用作子节点之一的序列)。
-
如果子节点有权重(其序列长度大于 2),则创建新节点并递归算法。
此外,这是我的程序,其中包含一些测试示例和一些扩展节点 class:
Node* constructTree(Node* root, std::string& treeString) {
// Find the weight of this node.
auto weightLeft = treeString.find_first_of("(") + 1;
auto weightRight = treeString.find_first_of("()", weightLeft);
auto weightString = treeString.substr(weightLeft, weightRight - weightLeft);
// Optional, we check if there is any weight, if there is not we leave zero
// weight from constructor.
// Works for something like that: ((1)(2)) -> (0(1)(2))
if (weightString.length() > 0) {
root->weight = std::stoi(weightString);
}
// Slice string to contain only children sequences.
treeString.erase(0, weightRight);
treeString.erase(treeString.length() - 1, 1);
// Looking for index in string where a left child ends and a right child starts.
// This point(index) is located where count of left braces and for braces
// is the same and the counts are not zero.
int splitPoint = -1;
int leftBraces = 0, rightBraces = 0;
for (int index = 0; index < treeString.length(); index++) {
char c = treeString[index];
if (c == '(') {
++leftBraces;
}
if (c == ')') {
++rightBraces;
}
if (leftBraces == rightBraces) {
splitPoint = index + 1;
break;
}
}
// If split point has been found then it means that this node has children.
if (splitPoint != -1) {
auto leftChildString = treeString.substr(0, splitPoint);
auto rightChildString = treeString.erase(0, splitPoint);
// Check for length so construct will stop if there is no child.
if (leftChildString.length() > 2) {
root->left = new Node();
constructTree(root->left, leftChildString);
}
if (rightChildString.length() > 2) {
root->right = new Node();
constructTree(root->right, rightChildString);
}
}
return root;
}
empty tree ::= ()
tree ::= empty tree | (w tree tree)
ex:
()
empty tree
(99(5()())(35(-5()())()))
99
/ \
5 35
/
-5
class Node
{
public:
int weight; // weight can be negative!
Node *left, *right;
Node():weight(0),left(NULL),right(NULL){}
Node(int d):weight(d),left(NULL),right(NULL){}
};
根据给定条件构造二叉树
我在构造它时遇到问题,我的程序会崩溃,我不知道为什么会这样,以下是我的代码,我打印出一些信息进行调试,取 (99(5()()) (35(-5()())())) 作为测试用例,它将打印出 99(5( 并且粉碎,我认为可能问题出在我处理的地方 ) 其中我 return 节点是NULL,但我找不到问题。顺便说一句,这棵树预计每棵树中有数百个节点,并且每个测试用例最多包含一万棵树,我会 运行 这个程序没时间了或者我需要做什么?谢谢你的时间
Node* MyBinaryTreeOps::constructTree(Node *root, std::string treeStr)const
{
int idex = 1;//always look at the treeStr[1]
Node *cur=NULL;//use to pass in recursive call
if(treeStr[idex]!='('&&treeStr[idex]!=')'){//meet number create new node
stringstream ss;
while(treeStr[idex]!='('){
ss<<treeStr[idex];
if(treeStr.size()>1){//if size > 1 then remove the treeStr[1],to let treeStr[1] become next char in treeStr
treeStr.erase(1,1);
}
}
int num=0;
ss>>num;
std::cout<<num<<std::endl;//print out just for debug
std::cout<<treeStr[idex]<<std::endl;//print out just for debug
root = new Node(num);
}
if(treeStr[idex]==')'){//meet ')' return subtree constructed
if(treeStr.size()>1){
treeStr.erase(1,1);
}
return root;
}
if(treeStr[idex]=='('){//meet first '(' then construct left subtree
if(treeStr.size()>1){
treeStr.erase(1,1);
}
root->left = constructTree(cur,treeStr);
}
if(treeStr[idex]=='('){ //meet second '(' then construct right subtree
if(treeStr.size()>1){
treeStr.erase(1,1);
}
root->right = constructTree(cur,treeStr);
}
if(treeStr[idex]==')'){ //meet ')' return subtree constructed
if(treeStr.size()>1){
treeStr.erase(1,1);
}
return root;
}
}
我自己试过这个问题,这是我写的函数。
算法步骤:
- 找到表示当前节点权重的序列的一部分。将其转换为 int 并分配给节点。
- 切片字符串以删除重量,开始和结束大括号。
- 遍历序列以找到分隔子节点的两个括号之间的点。
- 将子字符串拆分为两个序列(我们可以对起始树进行切片并将其重新用作子节点之一的序列)。
- 如果子节点有权重(其序列长度大于 2),则创建新节点并递归算法。
此外,这是我的程序,其中包含一些测试示例和一些扩展节点 class:
Node* constructTree(Node* root, std::string& treeString) {
// Find the weight of this node.
auto weightLeft = treeString.find_first_of("(") + 1;
auto weightRight = treeString.find_first_of("()", weightLeft);
auto weightString = treeString.substr(weightLeft, weightRight - weightLeft);
// Optional, we check if there is any weight, if there is not we leave zero
// weight from constructor.
// Works for something like that: ((1)(2)) -> (0(1)(2))
if (weightString.length() > 0) {
root->weight = std::stoi(weightString);
}
// Slice string to contain only children sequences.
treeString.erase(0, weightRight);
treeString.erase(treeString.length() - 1, 1);
// Looking for index in string where a left child ends and a right child starts.
// This point(index) is located where count of left braces and for braces
// is the same and the counts are not zero.
int splitPoint = -1;
int leftBraces = 0, rightBraces = 0;
for (int index = 0; index < treeString.length(); index++) {
char c = treeString[index];
if (c == '(') {
++leftBraces;
}
if (c == ')') {
++rightBraces;
}
if (leftBraces == rightBraces) {
splitPoint = index + 1;
break;
}
}
// If split point has been found then it means that this node has children.
if (splitPoint != -1) {
auto leftChildString = treeString.substr(0, splitPoint);
auto rightChildString = treeString.erase(0, splitPoint);
// Check for length so construct will stop if there is no child.
if (leftChildString.length() > 2) {
root->left = new Node();
constructTree(root->left, leftChildString);
}
if (rightChildString.length() > 2) {
root->right = new Node();
constructTree(root->right, rightChildString);
}
}
return root;
}