c - 从C中的字符串构建一棵树(在二叉树中定义)
问题描述
我在 CI 中构建树时遇到问题,尝试使用堆栈来处理嵌套括号,但我构建的树是错误的。我发现堆栈pionter有问题,太难了,我无法修复错误。
树是这样构建的:
#include <stdio.h>
#include<iostream>
#define MaxSize 30
using namespace std;
typedef char ElemType;
typedef struct Tnodes
{
ElemType data;
struct Tnodes* FirstChild;
struct Tnodes* NextSibling;
} TNode;
void CreateTree(TNode*& Family, char* str)
{
TNode* St[MaxSize], * p = NULL;
int top = -1;
bool k = true; //if FirstChild or NextSibling
Family = NULL;
int j = 0;
char ch = *(str + j);
while (ch != '\0')
{
switch (ch)
{
case '(':top++; St[top] = p; k = true; break; //if FirstChild,k=true
case ')':top--; break;
case ',':k = false; St[top] = p; break; //NextSibling ,k=false
default:
p = (TNode*)malloc(sizeof(TNode)); //pcreat a new node p
p->data = ch; p->FirstChild = p->NextSibling = NULL;
if (Family == NULL)
Family = p; //run for the first node
else if (k)
St[top]->FirstChild = p;
else if (!k)
St[top]->NextSibling = p;
}
j++;
ch = str[j];
}
}
//print the tree
void print_family(TNode* b, int i) {
int cnt;
if (b) {
for (cnt = 1; cnt < i; cnt++)
cout << " ";
cout << b->data << endl;
print_family(b->FirstChild, i + 1);
print_family(b->NextSibling, i);
}
}
int main()
{
char s[] = "a(b(d,e),c(g(s),f))";
TNode* Family;
CreateTree(Family, s);
print_family(Family, 5);
}
解决方案
在我的 c++ 实现中,我在这里使用了两个堆栈,尽管空间补偿仍然是 O(N)。
#include<bits/stdc++.h>
using namespace std;
struct node {
char data;
struct node* FirstChild;
struct node* NextSibling;
node(char data_) {
data = data_;
FirstChild = nullptr;
NextSibling = nullptr;
}
};
node *root = nullptr;
node *make_node(char data) {
node *n = new node(data);
if(root == nullptr) {
root = n;
//cout<<"rt "<<n->data<<endl;
}
return n;
}
void print_family(node* b, int i) {
int cnt;
if (b) {
for (cnt = 1; cnt < i; cnt++)
cout << " ";
cout << b->data << endl;
print_family(b->FirstChild, i + 1);
print_family(b->NextSibling, i);
}
}
void make_tree(string s) {
stack<node*> st;
stack<node*> parent;
for(int i = 0; i < s.length(); i++) {
if(s[i+1] == '(') {
node *n = make_node(s[i]);
st.push(n);
parent.push(n);
else if(s[i] == ')') {
vector<node*> pipe;
while(1) {
if(st.top()->data == parent.top()->data){
break;
}
pipe.push_back(st.top());
st.pop();
}
if(pipe.size() <= 2) {
parent.top()->FirstChild = pipe[0];
if(pipe.size() == 2){
parent.top()->FirstChild->NextSibling = pipe[1];
}
}
parent.pop();
}
else{
if(s[i] != ',' and s[i] != '(')
st.push(make_node(s[i]));
}
}
}
int main() {
string s = "a(b(d,e),c(g(s),f))";
make_tree(s);
print_family(root,5);
}
推荐阅读
- ruby-on-rails - Rails websocket 连接ID存储
- date - 日期选择器:如何在 UI5 中将日历的焦点更改为今天的日期?
- sql - 存储 SQL 元数据
- c# - 无法将类型“WindowsFormsApp2.tbl_user”隐式转换为“WindowsFormsApp2.BLL.User”
- python - 在python中处理包含标点编码的数据文件中的字符串
- powershell - PowerShell 无法识别命令 Resolve-DnsName
- c# - SQLite EF6 异步 API 抛出 InvalidCastException
- ios - Firebase 重置密码 IOS App xcode
- pandas - 将数据帧的标头保存到熊猫中的 csv 文件
- c# - 一旦满足条件并且在满足条件后仍然保持真实,我如何将布尔值设为真?