将扁平线性树表示转为内存树及表达式字符串转层次树实现需求

嘿，我来帮你搞定这两个树结构实现的需求，下面是针对每个需求的详细思路和可直接运行的C#代码示例，完全贴合你给出的TreeNode和ITreeNode定义~

首先得明确，扁平线性树一般是用父节点关联的方式存储的（比如每个节点包含自身ID、父节点ID、表达式内容等）。咱们先定义一个扁平节点的类来模拟这种输入，然后通过遍历和字典映射来快速构建内存中的树结构。

实现步骤 #

• 先把所有扁平节点存入字典，便于通过ID快速查找；
• 遍历每个扁平节点，找到它的父节点（如果存在），把当前节点添加到父节点的Children列表中；
• 最后找出根节点（父ID为null或不存在的节点），返回即可。

代码示例 #

// 定义扁平节点类，模拟线性存储的树结构
public class FlatTreeNode
{
    public Guid Id { get; set; }
    public Guid? ParentId { get; set; }
    public string Expression { get; set; }
    public bool Terminal { get; set; }
}

public static class TreeConverter
{
    // 扁平树转内存树的方法
    public static ITreeNode ConvertFlatToHierarchical(List<FlatTreeNode> flatNodes)
    {
        if (flatNodes == null || !flatNodes.Any())
            return null;

        // 用字典存储节点，便于快速查找
        var nodeDict = new Dictionary<Guid, TreeNode>();
        ITreeNode root = null;

        foreach (var flatNode in flatNodes)
        {
            var treeNode = new TreeNode
            {
                Expression = flatNode.Expression,
                Terminal = flatNode.Terminal,
                Children = new List<ITreeNode>()
            };
            nodeDict.Add(flatNode.Id, treeNode);

            // 处理根节点（无父节点）
            if (!flatNode.ParentId.HasValue)
            {
                root = treeNode;
                continue;
            }

            // 找到父节点并添加为子节点
            if (nodeDict.TryGetValue(flatNode.ParentId.Value, out var parentNode))
            {
                parentNode.Children.Add(treeNode);
            }
        }

        return root;
    }
}

针对*b+a-aQa这种格式的字符串，咱们先明确解析规则：

• 操作符：假设是+、-、*这类非终端节点，每个操作符对应一个非终端节点，需要包含两个子节点；
• 终端节点：连续的非操作符字符（比如b、a、Qa），这类节点的Terminal设为true，Children为空；
• 解析逻辑：采用递归方式，从左到右遍历字符串，遇到操作符就创建非终端节点，然后递归解析它的两个子节点（第一个子节点如果是字符则为终端，第二个子节点继续解析剩余字符串）。

实现步骤 #

• 用一个索引变量跟踪当前遍历的位置；
• 遇到操作符：创建非终端节点，然后递归解析左子节点（下一个字符/表达式）和右子节点（剩余字符串）；
• 遇到非操作符：收集连续的非操作符字符作为终端节点的Expression，然后返回该节点。

代码示例 #

public static class ExpressionTreeParser
{
    private static int _currentIndex;

    public static ITreeNode ParseExpression(string expression)
    {
        if (string.IsNullOrEmpty(expression))
            throw new ArgumentNullException(nameof(expression));

        _currentIndex = 0;
        return ParseNode(expression);
    }

    private static ITreeNode ParseNode(string expression)
    {
        // 如果已经遍历到末尾，返回null
        if (_currentIndex >= expression.Length)
            return null;

        char currentChar = expression[_currentIndex];

        // 判断当前字符是否为操作符（这里定义+、-、*为操作符）
        if (IsOperator(currentChar))
        {
            _currentIndex++;
            // 创建非终端节点
            var operatorNode = new TreeNode
            {
                Expression = currentChar.ToString(),
                Terminal = false,
                Children = new List<ITreeNode>()
            };

            // 解析左子节点（终端节点或另一个操作符节点）
            operatorNode.Children.Add(ParseTerminal(expression));
            // 解析右子节点（递归处理剩余表达式）
            operatorNode.Children.Add(ParseNode(expression));

            return operatorNode;
        }
        else
        {
            // 解析终端节点
            return ParseTerminal(expression);
        }
    }

    private static ITreeNode ParseTerminal(string expression)
    {
        var terminalBuilder = new StringBuilder();

        // 收集连续的非操作符字符
        while (_currentIndex < expression.Length && !IsOperator(expression[_currentIndex]))
        {
            terminalBuilder.Append(expression[_currentIndex]);
            _currentIndex++;
        }

        return new TreeNode
        {
            Expression = terminalBuilder.ToString(),
            Terminal = true,
            Children = new List<ITreeNode>()
        };
    }

    private static bool IsOperator(char c)
    {
        return c == '+' || c == '-' || c == '*';
    }
}

使用示例 #

// 测试表达式解析
string inputExpr = "*b+a-aQa";
ITreeNode root = ExpressionTreeParser.ParseExpression(inputExpr);
// 此时root的结构为：
// 根节点Expression="*"，Terminal=false
//   左子节点：Expression="b"，Terminal=true
//   右子节点：Expression="+"，Terminal=false
//       左子节点：Expression="a"，Terminal=true
//       右子节点：Expression="-"，Terminal=false
//           左子节点：Expression="a"，Terminal=true
//           右子节点：Expression="Qa"，Terminal=true

内容的提问来源于stack exchange，提问作者cs0815