Реализовать обход бинарного дерева в ширину - C#
Формулировка задачи:
необходимо реализовать обход вот этого бинарного дерева в ширину
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; namespace BinaryTree { /// <summary> /// Класс "Бинарное поисковое дерево" /// </summary> public class Tree { public int Value; public int Count = 0; Tree Left; Tree Right; /// <summary> /// Класс "узел БПД" /// </summary> private class Item { /// <summary> /// info - значение, хранящееся в узле /// lSon, rSon, father - ссылки на левого, правого сына и отца /// </summary> public int info; public Item lSon, rSon, father; /// <summary> /// Конструктор узла БПД /// </summary> /// <param name="x">значение, хранящееся в узле</param> public Item(int x) { info = x; lSon = rSon = father = null; } } /// <summary> /// ссылка на корень дерева /// </summary> private Item root; /// <summary> /// конструктор дерева /// </summary> public Tree() { root = null; } /// <summary> /// внутренняя процедура поиска /// </summary> /// <param name="x">искомое значение</param> /// <param name="p">ели найдено - ссылка на соответствующий узел, иначе - ссылка на то место, где остановились</param> /// <returns>нашли или нет</returns> private bool Find(int x, out Item p) { p = root; Item q = p; while (q != null) { p = q; if (q.info == x) return true; if (q.info < x) q = q.rSon; else q = q.lSon; } return false; } /// <summary> /// внешняя процедура поиска /// </summary> /// <param name="x">искомое значение</param> /// <returns>нашли или нет</returns> public bool Find(int x) { Item p; return Find(x, out p); } /// <summary> /// втавка в БПД /// </summary> /// <param name="x">вставляемое значение</param> /// <returns>смогли вставить или нет</returns> public bool Insert(int x) { Item r, p; if (root == null) { r= new Item(x); root = r; return true; } if (Find(x, out r)) return false; p = new Item(x); p.father = r; if (r.info < x) r.rSon = p; else r.lSon = p; return true; } /// <summary> /// удалить вершину (оборвать все ссылки) /// </summary> /// <param name="x">удаляемая вершина</param> private void deleteItem(Item x) { if (x.father == null) if (x.lSon != null) { root = x.lSon; x.lSon.father = null; } else { root = x.rSon; if (x.rSon != null) x.rSon.father = null; } else if (x.father.lSon == x) if (x.lSon != null) { x.father.lSon = x.lSon; x.lSon.father = x.father; } else { x.father.lSon = x.rSon; if (x.rSon != null) x.rSon.father = x.father; } else if (x.lSon != null) { x.father.rSon = x.lSon; x.lSon.father = x.father; } else { x.father.rSon = x.rSon; if (x.rSon != null) x.rSon.father = x.father; } x.father = x.lSon = x.rSon = null; } /// <summary> /// Удалить вершину по значению /// </summary> /// <param name="x">удаляемое значение</param> /// <returns>смогли удалить или нет</returns> public bool Delete(int x) { Item r, p; if (!Find(x, out r)) return false; if ((r.lSon == null) || (r.rSon == null)) { deleteItem(r); return true; } p = r.lSon; while (p.rSon != null) p = p.rSon; r.info = p.info; deleteItem(p); return true; } } }
Решение задачи: «Реализовать обход бинарного дерева в ширину»
textual
Листинг программы
public IEnumerable<int> TraverseLevelOrder() { if (root == null) yield break; var queue = new Queue<Item>(); queue.Enqueue(root); while (queue.Count > 0) { var node = queue.Dequeue(); yield return node.info; if (node.lSon != null) queue.Enqueue(node.lSon); if (node.rSon != null) queue.Enqueue(node.rSon); } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д