Обход дерева в ширину - C#

Узнай цену своей работы

Формулировка задачи:

Здравстуйте! Есть реализация класса с деревьями, не могу написать метод для поуровневого обхода дерева итерациями (т.е. в ширину), чтобы возвращал коллекцию узлов, т.е. Node и всё это с yield. Код класса прилагается: (в нём я уже сделал один метод из другого задания)
class Tree
    {
        /// <summary>
        /// /////// 15
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public int[] GetIntInRec()
        {
            List<int> nodesList = new List<int>();
            GetIntInRec(this.root, nodesList);
            return nodesList.ToArray();
        }
 
        public void GetIntInRec(Node node, List<int> nodesList)
        {
            nodesList.Add(node.value);
            if (node.left != null)
            {
                GetIntInRec(node.left, nodesList);
            }
            if (node.right != null)
            {
                GetIntInRec(node.right, nodesList);
            }
        }
        /// <summary>
        /// /////// end15
        /// </summary>
        public class Node
        {
            public Node left;
            public Node right;
            public Node parent;
            public int value;
 
            public Node(int value, Node left = null, Node right = null)
            {
                this.value = value;
 
                if (left != null)
                {
                    left.parent = this;
                }
                this.left = left;
 
                if (right != null)
                {
                    right.parent = this;
                }
                this.right = right;
            }
 
            //если отладчик глючит, когда наводите на переменную типа Node или Tree, 
            //то скорее всего в дереве циклическая ссылка, надо заккомментировать целиком этот метод (чтобы отладчик не падал), 
            //починить место, из-за которого циклическая ссылка и раскомментировать обратно
            public override string ToString()
            {
                //return ToStringMultiline(); // надо смотреть, повернув голову налево, в отладчике ничего непонятно
                return ToStringSingleLine(); // в одну строку
            }
 
            public string ToStringSingleLine()
            {
                return ToStringLinear(this);
            }
 
            public string ToStringMultiline()
            {
                return ToStringMultiline(this);
            }
 
            static string ToStringLinear(Node node)
            {
                if (node == null)
                {
                    return "_";
                }
                return string.Format("({0} {1} {2})",
                    ToStringLinear(node.left),
                    node.value,
                    ToStringLinear(node.right)
                );
            }
 
            static string ToStringMultiline(Node node, string indent = "")
            {
                if (node == null)
                {
                    return "";
                }
                return
                    ToStringMultiline(node.right, indent + "  ") +
                    string.Format("{0}{1}\n", indent, node.value) +
                    ToStringMultiline(node.left, indent + "  ");
            }
            
        }
 
        Node root;
 
        public Tree(Node root = null)
        {
            this.root = root;
        }
 
        public override string ToString()
        {
            if (root == null)
            {
                return "_";
            }
            return root.ToString();
        }
 
        public string ToStringMultiline()
        {
            if (root == null)
            {
                return "_";
            }
            return root.ToStringMultiline();
        }
 
        public void CheckParents()
        {
            if (root == null)
            {
                return;
            }
            if (root.parent != null)
            {
                throw new Exception("root node has parent");
            }
 
            Action<Node, Node> go = null;
            go = (parent, node) =>
            {
                if (node == null)
                {
                    return;
                }
                if (parent != node.parent)
                {
                    throw new Exception(string.Format("{0} has wrong parent", node.value));
                }
                go(node, node.left);
                go(node, node.right);
            };
 
            go(root, root.left);
            go(root, root.right);
        }
    }
 
    class TreeDebug
    {
        public void Debug()
        {
            DebugToString();
            DebugCheckParents();
        }
 
        static Tree.Node N(Tree.Node left, int value, Tree.Node right)
        {
            return new Tree.Node(value, left, right);
        }
 
        void DebugToString()
        {
            var root_node = N(N(null, 2, N(null, 3, null)), 4, N(N(null, 5, null), 6, null));
            var tree = new Tree(root_node);
            tree.CheckParents();
            Console.WriteLine(tree);
            Console.WriteLine(root_node.ToStringMultiline());
 
            var empty_tree = new Tree();
            empty_tree.CheckParents();
            Console.WriteLine(empty_tree);
 
            Console.WriteLine("15. in int array rec: ");
 
            int[] massiv = tree.GetIntInRec();
            for (int i = 0; i < massiv.Count(); i++)
            {
                Console.Write(massiv[i] + " ");
            }
        }
 
        void DebugCheckParents()
        {
            var root_node = N(N(null, 2, null), 1, null);
            root_node.left.parent = N(null, 23, null);
            var bad_tree = new Tree(root_node);
            try
            {
                bad_tree.CheckParents();
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
            }
        }
    }

Решение задачи: «Обход дерева в ширину»

textual
Листинг программы
public IEnumerable<Node> LevelOrderTraversal()
{
   if (root == null)
      yield break;
 
   var queue = new Queue<Node>();
   queue.Enqueue(root);
 
   while (queue.Count > 0) 
   {
      var node = queue.Dequeue();
      yield return node;
 
      if (node.left != null)
         queue.Enqueue(node.left);
      if (node.right != null)
         queue.Enqueue(node.right);
   }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

15   голосов , оценка 3.6 из 5
Похожие ответы