利用二叉树的层次顺序概念进行垂直顺序遍历

Question

我想垂直遍历二叉树。我在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++的精确副本

异常:字典中已存在键

编辑：

添加此检查后，逻辑仍无法提供正确的输出

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[]所做的工作时，我们发现

如果k与容器中元素的键匹配，则函数返回对其映射值的引用。

更重要的是，

如果k与容器中任何元素的键都不匹配，则函数将插入具有该键的新元素

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

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

Answer 2

 /// <summary>
    /// We must calculate horizontal distance.
    /// Each node along with its hd shall be queued.
    /// Add hd and values in one hashset.
    /// </summary>
    /// <param name="root"></param>
    public void VerticalOrderTraversal(Node<T> root)
    {
        if (root == null)
            return;

        int hd = 0;
        Queue<Tuple<Node<T>,int>> q = new Queue<Tuple<Node<T>,int>>();
        Dictionary<int, HashSet<T>> ht = new Dictionary<int, HashSet<T>>();
        q.Enqueue(new Tuple<Node<T>, int>(root,hd));
        ht[hd] = new HashSet<T>();
        ht[hd].Add(root.Data);
        while (q.Count > 0)
        {
            Tuple<Node<T>, int> current = q.Peek();
            q.Dequeue();

            if (current.Item1.leftNode != null)
            {
                if (!ht.ContainsKey(current.Item2 -1))
                {
                    ht[current.Item2 - 1] = new HashSet<T>();
                    ht[current.Item2 - 1].Add(current.Item1.leftNode.Data);
                }
                else
                {
                    ht[current.Item2 - 1].Add(current.Item1.leftNode.Data);
                }
                q.Enqueue(new Tuple<Node<T>, int>(current.Item1.leftNode, current.Item2 - 1));


            }
            if (current.Item1.rightNode != null)
            {
                if (!ht.ContainsKey(current.Item2 + 1))
                {
                    ht[current.Item2 + 1] = new HashSet<T>();
                    ht[current.Item2 + 1].Add(current.Item1.rightNode.Data);
                }
                else
                {
                    ht[current.Item2 + 1].Add(current.Item1.rightNode.Data);
                }
                q.Enqueue(new Tuple<Node<T>, int>(current.Item1.rightNode, current.Item2 + 1));

            }
        }

        foreach (int key in ht.Keys)
        {
            foreach (T data in ht[key])
            {
                Console.WriteLine("Vertical Level " + key + " value " + data);
            }
        }
    }

Answer 3

我对原始代码做了一些修改：

1. 如果字典中已经存在level (hd)，我们需要将节点添加到列表的末尾，而不是插入level和list的新元组。所以我添加了if语句if (dict.ContainsKey(hd))

1. 最好使用排序字典，以便从最低层打印，而不是从插入的第一层打印。

1. 在原始代码中，列表是在插入字典时创建的，这是一个问题，因为node.data将被视为列表的容量，而不是列表中的数据。

public void VerticalOrderTraverse(BstNode根){ //基例if (根== null)返回；//在SortedDictionary dict =新SortedDictionary()；//使用排序字典hd = 0；Queue> que =新Queue>()；Que.Enqueue(新Tuple (根，hd))；while (que.Count != 0) { Tuple临时= que.Peek()；que.Dequeue()；hd = temp.Item2；BstNode节点= temp.Item1；if (dict.ContainsKey(hd)) //不需要尝试创建新列表，将其添加到现有列表(node.data)；否则{ dict.Add(hd，新建列表())；dicthd.Add(node.data)；} if (node.left != null) que.Enqueue(new Tuple(node.left，hd - 1))；if (node.right != null) que.Enqueue(new Tuple(node.right，hd + 1))；} foreach (字典中的变量项) foreach (item.Value中的变量)Console.WriteLine(站点)；}