iphone - 我怎样才能做到这一点？不

Question

有没有可能的方法

我知道乍一看没有意义，但我能以某种方式做到吗？

p

Answer 1

一般树的 InOrder 遍历实际上没有意义。由于没有您应该访问当前节点的“顺序”。InOrder 仅对二叉树有意义。

为了使 InOrder 对一般树有意义，您必须定义应该以什么顺序访问当前节点。因为唯一有意义的两个选择是首先访问当前节点（即 Pre-Order）或最后访问（这是后订单）。因此，一般树的 InOrder 并没有多大意义。

当然，如果您的通用树具有特定的结构，那么 InOrder 就很有意义。如果你总是留下前 3 个孩子，而其他所有孩子都是对的，那么你的算法看起来像这样......

inorder(node)
  if node == null then return
  inorder(node.first)
  inorder(node.second)
  inorder(node.third)
  visit(node)
  foreach (remainingNode in RemainingNodes)
     inorder(remainingNode)

通用代码作为扩展方法...

    static public IEnumerable<Node<T>> InOrder<T>(this Node<T> thisNode)
    {
        var list = new List<Node<T>>();
        IEnumerable<Node<T>> leftNodes;
        IEnumerable<Node<T>> rightNodes;
        if (thisNode.Children == null)
        {
            leftNodes = new List<Node<T>>();
            rightNodes = new List<Node<T>>();
        }
        else
        {
            leftNodes = thisNode.Children.Take((int)Math.Ceiling(thisNode.Children.Count() / 2.0)).ToList();
            rightNodes = thisNode.Children.Skip(leftNodes.Count()).ToList();
        }
        if (leftNodes.Any())
        {
            foreach (var child in leftNodes)
            {
                list.AddRange(child.InOrder());
            }
        }
        list.Add(thisNode);
        if (rightNodes.Any())
        {
            foreach (var child in rightNodes)
            {
                list.AddRange(child.InOrder());
            }
        }
        return list;
    }

Answer 2

有序遍历要求按顺序访问节点

1. 剩下
2. 这个
3. 正确的

对于非二叉树，这种行为没有意义，因为没有左右专用节点。正如 Kevin 所说，只有执行前序或后序遍历才真正有意义；但是，如果要执行按顺序遍历，则可以访问一半的子节点、该节点，然后访问另一半。不过，这并不真正符合有序遍历的精神。

例如，假设您的节点有 5 个子节点。这将使按顺序遍历：

1. 孩子 1
2. 孩子 2
3. 孩子 3
4. 这个
5. 孩子 4
6. 孩子 5

（只是为了争论。从技术上讲，孩子 3 和 this 可以互换，但会出现同样的问题）

如果子 5 然后被删除，则按顺序遍历将是：

1. 孩子 1
2. 孩子 2
3. 这个
4. 孩子 3
5. 孩子 4

并且固有的顺序发生了变化。

但是，如果您要维护两个孩子列表：一个是 your leftChildren，另一个是rightChildren，那么按顺序遍历将与在二叉树中一样有意义。但是，如何选择哪个孩子进入哪个列表完全是另一个问题。

编辑：由于您似乎想继续进行此操作，因此可以使用以下方法进行操作：

public IEnumerable<Node<T>> InOrder()
{
    if (Children != null)
    {
        for (int i = 0; i < Children.length; i++)
        {
            if (i == Children.length / 2)
            {
                yield return this;
            }

            foreach (var node in Children[i].InOrder())
            {
                yield return node;
            }
        }
    }
}