如何从带括号的中缀字符串构造二叉树？

Question

非空树定义为{L,a,R}，L为左子树，R为右子树。 {} 子树为空。例如，{{{{},3,{}},2,{{},1,{}}},4,{{{},5,{}},6,{}}} 构造一个二进制文件树像图片。tree constructed from the string

我发现了一个关于从带括号的前缀表达式构造二叉树的问题，但我仍然不知道该怎么做。

Answer 1

我没有收到关于您希望使用哪种数据结构或语言的回复，但这里是 JavaScript.

中递归解析器的实现

它使用正则表达式将输入标记为大括号和数据。

根据这些标记，它创建了典型的 Node class.

的实例

最后它以简单的旋转视图输出结构树：

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

Answer 2

感谢您回答我的问题。我终于自己想出了一个天真的方法。我使用递归函数来处理令牌和创建节点。它使用一个计数器来判断括号是否关闭。这是我的 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++;
                }
            }
        }
    }
}

如何从带括号的中缀字符串构造二叉树？

How to construct a binary tree from a infix string with brackets?

string

algorithm

stack

binary-tree

data-structures