binary-tree - 如何将三元表达式转换为二叉树结构？

Question

我遇到了这个具有三元表达式 (a?b:c) 并且需要将三元表达式转换为二叉树结构的问题。

     a?b:c 

       a
      / \
     b   c

  a?b?c:d:e

     a
    / \
   b   e
  / \
 c   d

我使用使用数组实现的二叉树的方法:-

parent 居住在 - i
左子 - 2i
右 child - 2i+1

开始解析三元表达式，第一个字符将形成根节点，因此它将位于数组中的位置 1。如果下一个字符是“？”那么后面的字符将是它的 child ，所以左 child (在这种情况下 b 将在位置 2)。如果下一个字符是“:”，那么我们已经找到了右 child (在第一种情况下为 c)，因此我们将其添加到位置 3。

在第二种情况下，我们面临一个“？”在 b 之后，接下来的将是它的 child ，并将分别添加到 2j 和 2j+1 中，其中 j 是 b 在数组中的位置。现在我们面对一个 ":"我们检查当前 child 的父级是否有两个然后我们回溯并检查前一个节点，直到找到一个缺少右 child 的节点。

有没有其他方法可以做到这一点？希望我说得够清楚了。

Answer 1

以下是我经过彻底测试的解决方案。

class TreeNode {
    char c;
    TreeNode left;
    TreeNode right;

    TreeNode(char c) {
        this.c = c;
        left = null;
        right = null;
    }
}

public TreeNode tenaryToTree(String s) {
    if (s.length() == 0)
        return null;

    TreeNode root = new TreeNode(s.charAt(0));
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == '?') {
            TreeNode node = stack.peek();
            node.left = new TreeNode(s.charAt(i + 1));
            stack.push(node.left);
        } else if (s.charAt(i) == ':') {
            stack.pop();
            TreeNode node = stack.pop();
            node.right = new TreeNode(s.charAt(i + 1));
            stack.push(node.right);
        }
    }

    return root;
}