Обход дерева в ширину - 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); } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д