c# - 从有序遍历和预遍历遍历创建树的程序(迭代方法？)

我一直在试图编写一个程序，从给定的有序和预有序字符数组创建树我可以通过递归程序轻松做到这一点但是我不能用迭代的方法来转换它。求你了，帮帮我。
代码。

    public BinaryTreeNode<char> ConstructTree(char[] preorder, char[] inorder, int start, int end)
            {
             Dictionary<char,int> InorderKeys = StoreInorderKeys(inorder);
                if(start>end)
                {
                    return null;
                }
                char key = preorder[preIndex];
                preIndex++;
                BinaryTreeNode<char> tr = new BinaryTreeNode<char>(key);
                if (start == end)
                {
                    return tr;
                }
                int rootNodeKey = InorderKeys[key]
                tr.left = ConstructTree(preorder, inorder, start, (rootNodeKey - 1));
                tr.right = ConstructTree(preorder, inorder, rootNodeKey + 1, end);
                return tr;
            }
     private Dictionary<char,int> StoreInorderKeys(char[] inorder)
            {
                Dictionary<char, int> d = new Dictionary<char, int>();
                for(int i=0;i<inorder.Length;i++)
                {
                    d[inorder[i]] = i;
                }
                return d;
            }

最佳答案

你的评论

char[] inorder = (new List<char>() { 'F','B','A','E','H','C','D','I','G'})
char[] preorder = (new List<char>() { 'H', 'B', 'F', 'E', 'A', 'C', 'D', 'G', 'I' })

尤其是inorder没有被重新引导这一事实表明，实际上您使用的是未排序的"Binary Tree"，而不是我最初的答案所暗示的"Binary Search tree"。
那么，如何构建与给定的inorder和preorder匹配的二叉树呢？该思想基于原答案中提到的二叉搜索树的preorder和inorder的属性。尤其：
如果您按照preorder中的come的顺序将值插入bst，您将得到一个具有该preorder的树。
对于bst in order，按排序顺序遍历节点
因此，构建这样一个BT的简单方法是将其构建为一个BST，按照preorder的顺序插入值，然后（这里是一个棘手的部分）使用inorder作为它们的排序顺序换句话说，您忘记了任何“自然”排序，而使用了一个完全反映inorder的伪排序。
外部迭代显然是迭代的。典型的插入值实现是尾部递归的，因此也很容易将其转换为迭代代码。这是完整的代码：

class BinaryTreeNode<T>
{
    public readonly T value;
    public BinaryTreeNode<T> left = null;
    public BinaryTreeNode<T> right = null;

    public BinaryTreeNode(T value)
    {
        this.value = value;
    }

    public void InsertValue(T newValue, Comparer<T> comparer)
    {
        InsertValueNR(this, newValue, comparer);
    }

    private static void InsertValueNR(BinaryTreeNode<T> start, T newValue, Comparer<T> comparer)
    {
        for (BinaryTreeNode<T> cur = start; ;)
        {
            int cmp = comparer.Compare(cur.value, newValue);
            if (cmp == 0)
                throw new InvalidOperationException("value '" + newValue + "' is duplicated in the tree");
            else if (cmp < 0)
            {
                if (cur.left == null)
                {
                    cur.left = new BinaryTreeNode<T>(newValue);
                    return;
                }
                else
                    cur = cur.left;
            }
            else
            {
                if (cur.right == null)
                {
                    cur.right = new BinaryTreeNode<T>(newValue);
                    return;
                }
                else
                    cur = cur.right;
            }

        }

    }

    private void InsertValueRecursive(T newValue, Comparer<T> comparer)
    {
        int cmp = comparer.Compare(value, newValue);
        if (cmp == 0)
            throw new InvalidOperationException("value '" + newValue + "' is duplicated in the tree");
        else if (cmp < 0)
        {
            if (left != null)
                left.InsertValueRecursive(newValue, comparer);
            else
                left = new BinaryTreeNode<T>(newValue);
        }
        else
        {
            if (right != null)
                right.InsertValueRecursive(newValue, comparer);
            else
                right = new BinaryTreeNode<T>(newValue);
        }
    }



    class OrderComparer<T> : Comparer<T>
    {
        private readonly Dictionary<T, int> positions;

        public OrderComparer(List<T> order)
        {
            positions = new Dictionary<T, int>();
            for (int i = 0; i < order.Count; i++)
            {
                positions[order[i]] = i;
            }
        }

        public override int Compare(T x, T y)
        {
            return -Comparer<int>.Default.Compare(positions[x], positions[y]);
        }
    }

    public static BinaryTreeNode<T> ConstructTree(List<T> preorder, List<T> inorder)
    {
        var comparer = new OrderComparer<T>(inorder);
        var root = new BinaryTreeNode<T>(preorder[0]);
        for (int i = 1; i < preorder.Count; i++)
        {
            root.InsertValue(preorder[i], comparer);
        }

        return root;
    }

    public void PrintPreOrder()
    {
        PreOrder(ch => Console.Write(ch + " "));
        Console.WriteLine();
    }

    public void PrintInOrder()
    {
        InOrder(ch => Console.Write(ch + " "));
        Console.WriteLine();
    }

    public void PreOrder(Action<T> visitor)
    {
        visitor(value);
        if (left != null)
            left.PreOrder(visitor);
        if (right != null)
            right.PreOrder(visitor);
    }

    public void InOrder(Action<T> visitor)
    {
        if (left != null)
            left.InOrder(visitor);
        visitor(value);
        if (right != null)
            right.InOrder(visitor);
    }

}

它最重要的部分是使用自定义OrderComparer而不是“自然”的char顺序。我还留下了非递归InsertValueNR和递归InsertValueRecursive来说明将后者转换为前者是多么容易。
测试示例：

var inorder = new List<char>() { 'F', 'B', 'A', 'E', 'H', 'C', 'D', 'I', 'G' };
var preorder = new List<char>() { 'H', 'B', 'F', 'E', 'A', 'C', 'D', 'G', 'I' };
var root = BinaryTreeNode<char>.ConstructTree(preorder, inorder);
root.PrintInOrder();
root.PrintPreOrder();

我明白了
F B A E H C D I G公司
汉堡包
原始答案（BST）
注：这个最初的答案假设这里的术语"Binary Tree"实际上是指"Binary Search tree"即排序的。
您确定要同时从pre-order和inorder构建树吗？如果您查看链接问题中的answer，您可能会发现仅预订单就完全指定了树：您只需按照给定的顺序在数据树中进行常规插入。然后您只能检查它是否与给定的顺序匹配。不能用相同的预订单构建任何其他树但实际上，您只需检查inorder是否已排序：如果已排序，它将匹配如果它没有排序-它不是任何树的有效顺序。
至于inorder，有一种非常简单的方法来构建一个效率非常低但技术上仍然有效的二叉树：将第一个值放入根中，然后将每个下一个值作为其正确的子值相加。很明显，这棵树符合顺序这实际上等同于使用inorder作为其预排序来构建树。
实际上，您只需对in order数组中的数据进行任意随机洗牌，然后按顺序插入它们（就好像这是一个预订单一样）问题是，任何具有相同内容的有效二叉树（即，所有节点中的相同值集，但可能存在不同的内部结构）都将具有相同的inorder。