A non-empty tree is defined as {L,a,R}, L is left subtree, and R is Right subtree. {} for subtree is empty. for example, {{{{},3,{}},2,{{},1,{}}},4,{{{},5,{}},6,{}}} constructs an binary tree like the picture.tree constructed from the string
I have found a question for constructs an binary tree from a prefix expression with brackets, but I still have no idea for how to doing this.
CodePudding user response:
I did not get a reply on which data structure or language you expect to use, but here is an implementation of a recursive parser in JavaScript.
It uses a regular expression to tokenise the input into braces and data.
From those tokens it creates instances of a typical Node
class.
Finally it outputs that structured tree in a simple, rotated view:
class Node {
constructor(left, value, right) {
this.left = left;
this.value = value;
this.right = right;
}
toString() {
return (this.right ? this.right.toString().replace(/^/gm, " ") "\n" : "")
this.value
(this.left ? "\n" this.left.toString().replace(/^/gm, " ") : "");
}
}
function createTree(s) {
const tokens = s.matchAll(/,([^{},] ),|[{}]|(.)/g);
function getToken(expect) {
let [all, value, error] = tokens.next().value;
value ||= all;
if (error || expect && !expect.includes(all)) throw "Unexpected '" all "'";
return value;
}
function dfs(readOpening) {
if (readOpening) getToken("{");
if (getToken("{}") == "}") return null;
const node = new Node(dfs(), getToken(), dfs(true));
getToken("}");
return node;
}
return dfs(true);
}
// Demo
const s = "{{{{},3,{}},2,{{},1,{}}},4,{{{},5,{}},6,{}}}";
const root = createTree(s);
console.log(root.toString()); // rotated view, with root at the left
CodePudding user response:
Thanks for answerign my question. I finally came up with an naive method by myself. I used recursive function to deal with token and create nodes. It used a counter to judge whether brackets is closed. Here is my code in C .
createTree(string inp){
int leftBracket = 0,rightBracket = 0;
if (inp.length() <= 2) {
return nullptr;
}
else {
for (int i = 1;;i ) {
if (leftBracket == rightBracket && inp[i] >= '0' && inp[i] <= '9') {
treeNode* newNode = new treeNode(inp[i]-'0', createTree(inp.substr(1, i - 2)), createTree(inp.substr(i 2, inp.length() - i - 3)));
nodeCounter ;
return newNode;
}
else {
if (inp[i] == '{') {
leftBracket ;
}
else if (inp[i] == '}') {
rightBracket ;
}
}
}
}
}