从中序和先序遍历创建树的程序（迭代方法？）

Question

我一直在尝试编写一个程序来根据给定的中序和预序 char 数组创建树。我可以很容易地通过递归程序做到这一点。但我无法以迭代方式转换它。请有人帮我解决这个问题。

代码。

    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;
            }

Answer 1

您的评论

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" instead of the "Binary Search tree"。

那么如何构建匹配给定 inorder 和 preorder 的二叉树呢？这个想法基于原始答案中提到的二叉搜索树的 preorder 和 inorder 的属性。特别是：

如果您按照 preorder 中的顺序将值插入到 BST 中，您将获得具有该预序的树
对于BST inorder遍历排序顺序中的节点

因此，构建这样一个 BT 的一种简单方法是将其构建为 BST，按 preorder 的顺序插入值，并且（这里是棘手的一点）使用 inorder 作为他们的排序顺序。换句话说，您忘记了任何 "natural" 排序并使用了一个完全反映 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 代替 "natural" char 顺序。我还留下了 non-recursive 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
H B F E A C D G I

原始答案（BST）

注意：这个初始答案假定术语 "Binary Tree" here actually means "Binary Search tree" 即排序的。

您确定要同时从 pre-order 和有序构建一棵树吗？如果您查看链接问题中的 answer ，您可能会发现仅 pre-order 就完全指定了树：您只需按照给定的顺序将通常的插入数据树。然后你只能检查它是否匹配给定的顺序。您不能使用相同的 pre-order 构建任何其他树。但实际上你可以只检查 inorder 是否排序：如果排序 - 它会匹配。如果它没有排序 - 它不是任何树的有效顺序。

至于中序，有一种非常简单的方法可以构建一个非常低效但在技术上仍然有效的二叉树：将第一个值放入根中，然后将每个下一个值添加到它的右边child。这棵树显然符合顺序。这实际上与使用中序作为其 pre-order.

构建树相同

实际上，您可以对中序数组中的数据进行任意随机打乱，然后按该顺序插入它们（就像 pre-order 一样）。问题是任何具有相同内容的有效二叉树（即所有节点中的相同值集但可能不同的内部结构）将仅根据中序的定义具有相同的中序。

从中序和先序遍历创建树的程序（迭代方法？）

Program to create tree from inorder and preorder traversals(iterative approach?)

c#

iteration

algorithm

recursion

binary-tree

原始答案（BST）