代码之家 › 专栏 › 技术社区 › Unbreakable

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

tree-traversal c++ c#

Unbreakable · 技术社区 · 8 年前

以下是我的尝试:

// 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));

3 回复 | 直到 8 年前

AustinWBryan ravenspoint 8 年前

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

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

当我们往里看的时候 documentation std::map::operator[] 是的,我们找到了

重要的是,

的索引器 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));

Gaurav Bhushan 8 年前

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

Pritam Banerjee Ashish Karnavat 6 年前

我对原始代码做了一些更改:

如果level(hd)已经存在于Dict中,我们需要将节点添加到列表的末尾,而不是插入level和list的新元组。所以我添加了if语句(集装箱(高清))]

在原始代码中,列表是在插入Dict时创建的,这是一个问题,因为节点数据将被视为清单的容量,而不是清单中的数据。

 public void VerticalOrderTraverse(BstNode root)
         {
             // Base case
             if (root == null)
                 return;

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

             Queue<Tuple<BstNode, int>> que = new Queue<Tuple<BstNode, int>>();
             que.Enqueue(new Tuple<BstNode, int>(root, hd));
             while (que.Count != 0)
             {
                 Tuple<BstNode, int> temp = que.Peek();
                 que.Dequeue();
                 hd = temp.Item2;
                 BstNode node = temp.Item1;

                 if (dict.ContainsKey(hd))  //No need to try creating a new list, add it to the existing 
                     dict[hd].Add(node.data);
                 else
                 {
                     dict.Add(hd, new List<int>()); 
                     dict[hd].Add(node.data);
                 }
                 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);
         }
     }
 }
}