二叉树到数学表达式

本文关键字:表达式 二叉树 | 更新日期: 2023-09-27 18:33:23

我有一个包含数学表达式的二叉树。我使用数组将二叉树保存在内存中。我将运算符(如 + 或 tan)保存为数组中的字符串。对于每个 I 节点,左节点索引为 2*i+1,右节点索引为 2*i+2。每个节点都可以是操作数或运算符。我想将二叉树转换为字符串形式的数学表达式,例如:"2+tan(tan(10))"。如何在 C# 中将二叉树转换为数学表达式?

  +
 / '
2  tan
   / '               ===>      "2+tan(tan(10))"
 tan  
 / ' / '
10  

这是我的二叉树代码:

public class Tree
{
    private readonly List<Node> _nodes;
    public Tree(int size)
    {
        _nodes = new List<Node>();
        for (var i = 0; i < size; i++)
        {
            _nodes.Add(new Node(i, null));
        }
        for (var i = 0; i < size; i++)
        {
            if (2*i+1 > size-1 || 2*i+2 > size-1)
                break;
            _nodes[i].Left = _nodes[2*i + 1];
            _nodes[i].Right = _nodes[2*i + 2];
        }
    }
     ...
}

二叉树到数学表达式

你可以递

归地做到这一点 - 编写一个返回字符串的方法,并做以下三件事:

  • 当两个子树都为 null 时,返回节点的内容
  • 当只有一个子树为非 null 时,递归调用该方法,然后返回节点的内容,后跟括号中递归调用的结果
  • 当两个子树都为非空时,对左子树和 Rift 子树进行递归调用,并返回左结果,后跟此节点的内容,然后返回右结果。