c# - 二叉树层序概念中的垂直序遍历

Question

我想垂直遍历一个二叉树。我在 Geeks for Geeks in C++ 中找到了一个工作代码。我想将它转换成 C#，但我做不到。请指导我。

下面是我的尝试:

// we always need the address of the Root Node come what may!
public class BstNode
{
    public int data      { get; set; }
    public BstNode left  { get; set; }
    public BstNode right { get; set; }

    public BstNode(int value) => data = value;
}

public class BstTree
{
    // For BST
    public BstNode Insert(BstNode root, int data)
    {
        if (root == null)
        {
            root       = new BstNode(data);
            root.left  = null;
            root.right = null;
        }
        else if (data > root.data)
             root.right = Insert(root.right, data);
        else root.left = Insert(root.left, data);

        return root;
    }
    // PROBLEM IN BELOW CODE
    public void VerticalOrderTraverse(BstNode root)
    {
        // Base case
        if (root == null)
            return;

        // Create a map and store vertical oder in
        Dictionary<int, List<int>> dict = new Dictionary<int, List<int>>();
        int hd = 0;

        // Create queue to do level order traversal.
        // Every item of queue contains node and
        // horizontal distance.
        Queue<Tuple<BstNode, int>> que = new Queue<Tuple<BstNode, int>>();
        que.Enqueue(new Tuple<BstNode, int>(root, hd));
        while (que.Count != 0)
        {
            // pop from queue front
            Tuple<BstNode, int> temp = que.Peek();
            que.Dequeue();
            hd = temp.Item2;
            BstNode node = temp.Item1;

            // insert this node's data in vector of hash
            dict.Add(hd, new List<int>(node.data)); // CONFUSED HERE

            if (node.left != null)
                que.Enqueue(new Tuple<BstNode, int>(node.left, hd - 1));
            if (node.right != null)
                que.Enqueue(new Tuple<BstNode, int>(node.right, hd + 1));
        }
        foreach (var item in dict)
            foreach (var ite in item.Value)
                Console.WriteLine(ite);
    }
}

class Program
{
    public static void Main()
    {
        BstNode root = null;
        BstTree bstTree = new BstTree();
        root = bstTree.Insert(root, 10);
        root = bstTree.Insert(root, 12);
        root = bstTree.Insert(root, 7);
        root = bstTree.Insert(root, 8);
        root = bstTree.Insert(root, 15);
        root = bstTree.Insert(root, 11);
        root = bstTree.Insert(root, 6);
        bstTree.VerticalOrderTraverse(root);
    }
}

请注意，我在“VerticalOrderTraversal”方法中遇到异常。这个 VerticalOrderTraversal 是 Vertical Order Traversal in C++ 的精确拷贝

Exception: Key already exists in dictionary

编辑:

添加此检查后逻辑仍然没有给出正确的输出

if (dict.ContainsKey(hd))
     dict[hd].Add(node.data);
else dict.Add(hd, new List<int>(node.data));

Answer 1

哪里有这个:

dict.Add(hd, new List<int>(node.data));

原文是这样的:

m[hd].push_back(node->key);

现在当我们在 documentation 中查找时什么运营商std::map::operator[]确实，我们发现

If k matches the key of an element in the container, the function returns a reference to its mapped value.

重要的是，

If k does not match the key of any element in the container, the function inserts a new element with that key

Dictionary<TKey, TValue>.Item 的索引器具有相同的功能(“集合操作创建具有指定键的新元素”)，但在 C++ 中，这意味着构建一个新 vector 作为新元素的值，C# 不创建 List<int> 的实例对我们来说，一个简单的解决方案可能是:

if (dict.ContainsKey(hd))
     dict[hd].Add(node.data);
else dict.Add(hd, new List<int>(node.data));