.net - 如何解析树数据结构？

Question

我有一个由节点组成的树数据结构，我需要将其解析为表达式树。我的节点看起来像这样（简化）：

    public class Node
    {
        public Node Left { get; set; }
        public Node Right { get; set; }
        public Operation OperationType { get; set; }
        public object Value { get; set; }
    }

找到树的底部并向后构建表达式树的最佳/正确方法是什么？你先解析左还是右？

Answer 1

如果您想首先到达树的底部，那么您可以进行“按顺序”或“后序”搜索。“按顺序”搜索将首先找到底部最左侧的节点，然后是该节点的父节点，然后是父节点的右侧子节点。“后序”搜索将在访问父节点之前“访问”左子节点和右子节点。

考虑表达式'x + y'。有序搜索将产生：

'x', '+', 'y'

而订单后搜索会产生：

'x', 'y', '+'

Answer 2

如前所述，你先去哪里并不重要。但是最常用的树遍历算法。如果这棵树按照我的想法组织，推荐使用 inorder：

（来自维基百科）要按顺序遍历非空二叉树，在每个节点递归执行以下操作：

1. 遍历左子树。
2. 访问根。
3. 遍历右子树。

（这也称为对称遍历。）

Answer 3

我认为您首先穿越哪个方向并不重要。然而，在从左到右的语言占主导地位的世界里，如果你先向左走，别人会更直观地理解你的代码。