将特定类型的字符串转换为二叉树

Question

我们有一个这种格式的输入字符串 "(1(2(4)(5))(3(6(8)(9))(7)))"
我们必须构建一个二叉树，使得 1 是根节点，第一个完整的括号包含 (2(4)(5)) 包含 1 的左 child
而(3(6(8)(9))(7))是根A右边child的家族。
最后树会变成这样。
Like this

我找不到编写转换这个算法的确切算法。提前致谢！

Answer 1

当然，我不能只在这里为您的作业编写代码 :-) 但我认为如果您将每个符号都视为一个操作可能会有所帮助，例如

( = down
1 = add
( = down
2 = add
( = down 
4 = add
) = up (goes to level of 2)
( = down
5 = add
) = up (goes to level of 2)
) = up (goes to level of 1)
( = down
3 = add
( = down
6 = add
( = down
8 = add
) = up (goes to level of 6)
( = down
9 = add
) = up (goes to level of 6)
) = up (goes to level of 3)
( = down
7 = add
) = up (goes to level of 3)
) = up (goes to level of 1)
) = up (leaves)

如果您从递归算法的角度考虑，您可能会将“下降”视为递归方法调用，将“上升”视为从递归方法调用返回（自动发生，然后方法本身完成).

我强烈建议你尝试解决这个问题，因为学习真的很重要。

但是，如果您仍然找不到解决方案，您可以在此处找到有关解决方法的一些详细说明。 https://www.geeksforgeeks.org/construct-binary-tree-string-bracket-representation/

Answer 2

想想堆栈。当您看到“(”时将元素压入堆栈，当您看到“)”时弹出堆栈，但将其作为 child 分配给堆栈的顶部元素。

那么让我们看一下示例 "( 1 ( 2 ( 4 ) ( 5 ) ) ( 3 ( 6 ( 8 ) ( 9 ) ) ( 7 ) ) )"

(1 -> 推 1
(2 -> 推 2
(4 -> 推 4
) -> 弹出 4，但将 4 作为 child 分配给堆栈顶部，即 2（查看左侧是否可用然后分配为左侧 child 否则右侧 child )

当前树：

(5 -> 推 5
) -> 弹出 5，堆栈顶部仍然是 2（左侧不可用，因此将其分配为右侧 child of 2）

当前树：

) -> 弹出 2，栈顶为 1（left of 1 可用，因此将 2 分配为 left child of 1)

当前树：

(3 -> 推 3
(6 -> 推 6
(8 -> 推 8
) -> 弹出 8，栈顶 6 的左边可用分配 8 作为 6
的左边

当前树：

(9 -> 推 9
) -> 弹出 9 -> 将其添加到堆栈右侧的顶部 child 即 6 的右侧 child 因为 6 的左侧被视为 8.

当前树：

) -> 弹出 6 -> 将它添加到堆栈顶部，即 3 的左边 child 因为它是可用的。

当前树：

(7 -> 推 7
) -> 弹出 7 -> 将其添加到堆栈顶部，即 3 的右边 child 因为 3 的左边 child 被视为 6.

) -> 弹出 3 -> 将其添加到堆栈顶部，即 1 的右边 child 因为 1 的左边 child 被视为 2.

当前树：

) -> pop 1 -> 现在堆栈中没有任何东西。完成。

Java 中使用堆栈实现的完整可运行示例是：

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        TreeNode root = buildTree("(1(2(4)(5))(3(6(8)(9))(7)))");
        levelOrder(root);
    }
    
    static class TreeNode {
        int val;
        TreeNode left, right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    
    private static TreeNode buildTree(String s) {
        Deque<TreeNode> dq = new ArrayDeque<>();
        TreeNode rootNode = null;
        for ( int i = 0; i < s.length(); i++ ) {
            if ( s.charAt(i) == '(' ) {
                Integer current = Integer.parseInt(String.valueOf(s.charAt(i+1)));
                dq.push(new TreeNode(current));
            } else if ( s.charAt(i) == ')' ) {
                TreeNode node = dq.pop();
                if ( dq.isEmpty() ) {
                    break;
                } else {
                    
                    rootNode = dq.peek();
                    if (rootNode.left == null) {
                        rootNode.left = node;
                    } else {
                        rootNode.right = node;
                    }
                }
            }
        }
        return rootNode;
    }
    
    private static void levelOrder(TreeNode root) {
        Deque<TreeNode> dq = new ArrayDeque<>();
        dq.offer(root);
        while(!dq.isEmpty()) {
            int sz = dq.size();
            
            for ( int i = 0; i < sz; i++ ) {
                TreeNode node = dq.poll();
                System.out.print(node.val + " ");
                if ( node.left != null ) {
                    dq.offer(node.left);
                }
                if ( node.right != null ) {
                    dq.offer(node.right);
                }
            }
            System.out.println();
        }
        
    }

}

Answer 3

该字符串按前序顺序列出了节点。因此，递归解决方案将是一个可能的选择。

在JavaScript中你可以这样写：

class Node {
    constructor(value) {
        this.value = value;
        this.children = [];
    }
}

function createTree(str) {
    // Extract numbers and parentheses from input into an array
    let tokens = str.match(/\d+|./g);
    if (!tokens) return null;
    let i = 1; // skip first character, as it must be a "("
    
    function recur() {
        let node = new Node(tokens[i++]);
        while (tokens[i++] != ")") {
            node.children.push(recur());
        }
        return node;
    }
    
    return recur();
}

// Demo run
let str = "(1(2(4)(5))(3(6(8)(9))(7)))";
let tree = createTree(str);
// Output the tree in JSON format
console.log(JSON.stringify(tree, null, 2));

请注意，此实现不对输入执行任何验证。假设输入的语法正确。

该算法将接受非二叉树的编码，因为这种格式可以对具有任意数量子节点的节点进行编码。

将特定类型的字符串转换为二叉树

Converting Specific kind of String to Binary Tree

string

algorithm

binary-tree

parentheses