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

Question

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

     a?b:c 

       a
      / \
     b   c

  a?b?c:d:e

     a
    / \
   b   e
  / \
 c   d

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

Parent 位于 - i 左 child - 2i 右 child - 2i+1

开始解析三元表达式，第一个字符将构成根节点，因此它将位于数组中的位置 1。如果下一个字符是 '?'那么后面的字符将是它的 children so left child （在这种情况下，b 将位于位置 2）。如果下一个字符是“:”，那么我们找到了正确的 child（第一种情况下为 c），因此我们将其添加到位置 3。

在第二种情况下，我们面临一个“？”在 b 之后，接下来的内容将是它的 children，并将分别添加到 2j 和 2j+1，其中 j 是 b 在 array.Now 中的位置，我们面对一个“:”，我们检查 [=当前 child 的 31=] 如果它有两个 children 那么我们回溯并检查前一个节点，直到我们找到一个缺少正确的节点 child.

还有其他方法吗？希望我表达得足够清楚。

Answer 1

我用树想到了这样的东西。未彻底测试：

当我看到“?”时，它是我的左边 child，所以添加到我的左边然后向左走。

如果我看到“:”，则：

转到我的parent
如果right不为空且parent不为空，继续我的parent
我的右边child是空的。加对了。向右走。

注意：如果它有权限，您将永远不会回到根目录 child。

    public NodeC convertTtoBT (char[] values) {
    NodeC n = new NodeC (values[0]);

    for (int i = 1; i < values.length; i += 2) {
        if (values[i] == '?') {
            n.left = new NodeC (values[i + 1]);
            n = n.left;
        }
        else if (values[i] == ':') {
            n = n.parent;
            while (n.right != null && n.parent != null ) {
                n = n.parent;
            }                    
            n.right = new NodeC (values[i + 1]);
            n = n.right;
        }
    }
    return n;

Answer 2

这个不使用父节点。但是使用堆栈。

    public NodeC convertTtoBT (char[] values) {
    char xx = values[0];
    NodeC n = new NodeC(xx);
    Stack<NodeC> a =  new Stack<NodeC>();
    for (int i = 1; i < values.length; i += 2) {
        if (values[i] == '?') {
            n.left = new NodeC (values[i + 1]);
            a.add(n);
            n = n.left;

        }
        else if (values[i] == ':') {
            n = a.pop();
            while (n.right != null) {
                n = a.pop();
            }             
            n.right = new NodeC (values[i + 1]);
            a.add(n);
            n = n.right;
        }
    }
    return n;
}

Answer 3

想法是从左到右开始解析字符串，当您遇到 '?' 时，您会深入树中，否则只是 return 创建了新节点。

这是我的递归解决方案：

  struct node{
    char val;
    node *left;
    node *right;
    node(char v):val(v),left(NULL),right(NULL){
    }
};

    node* create_tree(string input, int &current){
    if(current>=(int)input.size()){
        return NULL;
    }
    node *temp = new node(input[current]);
    current+=2;
    if(current<(int)input.size()){
        if(input[current-1]=='?'){
            temp->left=create_ternary_tree(input,current);
            temp->right=create_ternary_tree(input,current);
        }
    }
    return temp;
}

Answer 4

以下是我经过全面测试的解决方案。

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;
}

Answer 5

我的解决方案：每个树节点都没有父节点 link，所以我使用堆栈来保存它们。这个解决方案的优点是我只将 root 压入堆栈，因此在 (if x==':' {}) 语句中，没有 while 循环，没有 push 语句。

    public  static TreeNode convert(String ternary) {
    char[] chs = ternary.toCharArray();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode cur=new TreeNode(chs[0]);
    TreeNode root= cur;
    for (int i=1; i<chs.length; i+=2) {
        if (chs[i]=='?') {
            stack.push(cur);
            TreeNode node = new TreeNode(chs[i+1]);
            cur.left = node;
            cur = node;
        }
        else if (chs[i]==':') {
            cur = stack.pop();
            TreeNode node = new TreeNode(chs[i+1]);
            cur.right = node;
            cur = node;

        }
    }
    return root;
}

Answer 6

 public static TreeNode convert_loop(char[] expr) {
    if (expr == null || expr.length < 1) {
        return null;
    }
    if (expr.length == 1) {
        return new TreeNode(expr[0]);
    }
    if ((expr.length - 1) % 4 != 0) {
        throw new InputMismatchException("wrong expression");
    }
    int start = 0, end = expr.length - 1;

    TreeNode<Character> root = new TreeNode<>(expr[start]);
    root.right = new TreeNode<>(expr[end]);

    start += 2;
    end -= 2;
    TreeNode<Character> cur = root;

    while (start != end) {
        TreeNode<Character> node = new TreeNode<>(expr[start]);
        node.right = new TreeNode<>(expr[end]);

        cur.left = node;
        cur = node;

        start += 2;
        end -= 2;
    }
    cur.left = new TreeNode(expr[start]);// care
    return root;
}

Answer 7

从右到左遍历表达式，将任何字母作为节点推入堆栈。如果您看到“？”，则不要压入下一个字母，而是将其作为根节点，从堆栈中弹出最后两个节点作为左右根节点的子节点，然后将根节点推回堆栈中。

public TreeNode ternaryToTree(char[] exp) {
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();

    for (int i = exp.length-1; i >= 0; i--) {
        if (exp[i] == ':') continue;
        if (exp[i] == '?') {
            TreeNode node = new TreeNode(exp[--i]);
            node.left = stack.pop();
            node.right = stack.pop();
            stack.push(node);
        } else {
            stack.push(new TreeNode(exp[i]));
        }
    }

    return stack.isEmpty() ? null : stack.pop();
}

Answer 8

如果这个 a?b:c?d?e:f:g?h:i?j:k 是三元表达式那么树会像这样

下面是Java解决方案...

private static TreeNode convertTernaryExpression(String s) 
{

    Stack<TreeNode> stack = new Stack<>();

    int length = s.length();
    int index = 0;
    TreeNode rootNode = null;
    while(index < length)
    {
        while(s.charAt(index) != ':')
        {
            if(s.charAt(index) == '?' && stack.peek().right != null)
            {
                TreeNode temp = stack.pop();
                if(rootNode == null)
                {
                    rootNode = temp;
                }
                stack.push(temp.right);
            }
            stack.push(new TreeNode(s.charAt(index++)));
        }

        TreeNode left = stack.pop();
        TreeNode questionMark = stack.pop();
        TreeNode root = stack.pop();
        index++;
        TreeNode right = new TreeNode(s.charAt(index++));

        root.left = left;
        root.right = right;

        stack.push(root);
    }

    if(rootNode == null)
    {
        return stack.pop();
    }
    else
    {
        return rootNode;
    }
}

class TreeNode
{
    TreeNode left;
    TreeNode right;
    char val;
    public TreeNode(char val) 
    {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

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

How to convert a Ternary expression to a Binary tree structure?

binary-tree

ternary-operator

data-conversion