logo标签列表

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

binary-treeternary-operatordata-conversion
9

我遇到了一个问题，其中使用了三元表达式（a?b:c），需要将其转换为二叉树结构。

     a?b:c 

       a
      / \
     b   c

  a?b?c:d:e

     a
    / \
   b   e
  / \
 c   d

我使用基于数组实现的二叉树算法：

父节点位于 - i 左孩子 - 2i 右孩子 - 2i+1

开始解析三元表达式，第一个字符将形成根节点，因此在数组中位置为1。如果下一个字符是“？”则其后面的字符将是它的子节点，因此左孩子（在本例中是b）将位于位置2。如果下一个字符是“：”，则我们已经找到了右孩子（在本例中是c），因此我们将其添加到位置3。

在第二种情况下，在b后面我们遇到了“？”，因此其后面的内容将成为其子节点，并分别添加到2j和2j+1 j是b在数组中的位置。现在我们遇到了“：”，我们检查当前节点的父节点是否有两个子节点，如果有，则我们回溯并检查上一个节点，直到找到一个缺少右子节点的节点。

还有其他方法可以做到这一点吗？希望我表述清楚了。

9个回答
11
以下是我的解决方案，已经经过了全面的测试。
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;
}
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;
}
我认为如果你保存一棵树的根节点的引用并返回它，可能会更好。只需在第三行后添加以下内容：NodeC root_node = n，而在结尾处，可以使用“return root_node”代替“return n;”。 - Kevin Zhao
时间复杂度是O(n)吗？ - Kevin Zhao
错误的解决方案。 - Kevman
2

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

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();
}
2
如果这是一个三元表达式 if this a?b:c?d?e:f:g?h:i?j:k，那么它的树形结构应该如下所示。
          a
         / \
        b   c
           /  \
          d    g
         / \  / \
        e   f 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;
    }
}
1

这个想法是从左到右开始解析字符串，当你遇到一个'?'时，你会深入树中，否则就返回新创建的节点。

下面是我的递归解决方案：

  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;
}
它会正确地添加树吗？我不这么认为。 - Prasad Shinde
1
我的解决方案： 每个树节点都没有父链接，因此我使用堆栈来保留它们。 这种解决方案的优点是，我只将根节点推入堆栈中，在(if x==':' {})语句中，没有while循环，也没有推送语句。
    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;
}
1
我使用树来实现以下内容，但未经全面测试：
当我看到一个'?'时，它是我的左子节点，因此添加到我的左边并向左移动。
如果我看到':', 那么：
1. 前往我的父节点 2. 如果右侧不为空且父节点不为空，则继续前往我的父节点 3. 我的右子节点为空。添加右侧。前往右侧。
注意：如果根节点有右子节点，则永远不会返回根节点。
    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;
0
 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;
}
0
以下是Python的实现，思路是从左到右遍历字符串，如果遇到'?'则将最近的节点推入堆栈并用它作为父节点，在遇到':'时从堆栈中弹出一个节点，并在其他情况下将当前节点分配给父指针的左侧或右侧。
from collections import deque

class Node:

    def __init__(self , left = None, right = None, val = None):
        self.left = left
        self.right = right
        self.val = val


def makeTree(s:str):
    stack = deque()
    root = Node(val = s[0])
    stack.append(root)
    prev = None
    for i,char in enumerate(s[1:]):
        if char == '?':
            if i != 0:
                stack.append(prev) 
            parent = stack[-1]
        elif char == ':':
            parent = stack.pop()
        else:

            if parent.left == None:
                parent.left = Node(val = char)
                prev = parent.left
           
             else:

                parent.right = Node(val=char)
                prev = parent.right
    return root

def preorder(root):
    if root == None:
        return

    print(root.val,end=' ')
    preorder(root.left)
    preorder(root.right)


ternary = 'a?b?d:e:c'
r=makeTree(ternary)
preorder(r)
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接