Бинарное дерево. Обход в ширину - C#
Формулировка задачи:
Господа, добрый день. Прошу, помогите написать обход в ширину, с обходом в глубину разобрался, а вот с этим проблемы. Прикрепляю файл с тем, что уже есть, буду так же благодарен, если поможете с реализацией класса поиска элемента и поиска предыдущего элемента, а так же, удаления элемента.
-----------------------------------------------------------------------------------------------------------
//Сам узел
---------------------------------------------------------------------------------------
И обходы в глубину (Прямой, обратный, симметричный)
Прикрепить не вышло, поэтому вот так
//это прописано в Main
namespace Tree { /// <summary> /// Interaction logic for Window1.xaml /// </summary> public partial class Window1 : Window { public Window1() { InitializeComponent(); } void button1_Click(object sender, RoutedEventArgs e) { MessageBox.Show (""); } public class Tree<T> where T: IComparable { protected Node<T> Root;//Корень дерева с инкапсуляцией Root public void AddNode(T newData) { if (Root == null) //Добавление первого элемента { Root = new Node<T>(newData); return; } AddNodeRecursion(Root, newData); } private static void AddNodeRecursion(Node<T>currentNode, T newData) { if (currentNode.Data.CompareTo(newData) < 0) { if (currentNode.Right == null) currentNode.Right = new Node<T>(newData); else AddNodeRecursion(currentNode.Right, newData); } else { if ( currentNode.Left == null ) currentNode.Left = new Node<T>(newData); else AddNodeRecursion(currentNode.Left, newData); } } } } }
namespace Tree { /// <summary> /// Description of Class1. /// </summary> public class Node <T> where T : IComparable { public T Data { get; set; } public Node<T> Left { get; set; } public Node<T> Right { get; set; }//ссылка на правую ветвь public Node(T data) //конструктор { Data = data; } }// Конец класса Node<T> }
namespace Tree { /// <summary> /// Description of TreeObh. /// </summary> public class TreeObh: Tree<int> { //Прямой обход дерева public string TreeTraversalDirect() { string s = TreeTraversalDirectRecursion(Root); return s; } private static string TreeTraversalDirectRecursion(Node<T> currentNode) { string s =""; if (currentNode != null) { s = Convert.ToString(currentNode.Data) + " "; s+=TreeTraversalDirectRecursion(currentNode.Left); s+=TreeTraversalDirectRecursion(currentNode.Right); } return s; } //Симметричный обход дерева public string TreeTraversalDirect() { string s = TreeTraversalDirectRecursion(Root); return s; } private static string TreeTraversalDirectRecursion(Node<T> currentNode) { string s =""; if (currentNode != null) { s+=TreeTraversalDirectRecursion(currentNode.Left); s += Convert.ToString(currentNode.Data) + " "; s+=TreeTraversalDirectRecursion(currentNode.Right); } return s; } //Обратный public string TreeTraversalDirect() { string s = TreeTraversalDirectRecursion(Root); return s; } private static string TreeTraversalDirectRecursion(Node<T> currentNode) { string s =""; if (currentNode != null) { s+=TreeTraversalDirectRecursion(currentNode.Left); s+=TreeTraversalDirectRecursion(currentNode.Right); s += Convert.ToString(currentNode.Data) + " "; } return s; } } }
Решение задачи: «Бинарное дерево. Обход в ширину»
textual
Листинг программы
using System; using System.Collections.Generic; namespace ConsoleApplication1 { class Program { int n = 5; int[,] matrix; static Random rnd = new Random(); static void Main(string[] args) { new Program().Foo(); } void Foo() { Fill(); string tmp = string.Empty; int?[,] rib = new int?[n, n]; Queue<int> quene = new Queue<int>(); List<int> loocedVertex = new List<int>(); quene.Enqueue(0); while (quene.Count != 0) { int index = quene.Dequeue(); for (short i = 0; i < n; i++) { if (matrix[index, i] != 0) { if (!quene.Contains(i) && !loocedVertex.Contains(i)) { quene.Enqueue(i); rib[index, i] = 1; } } else rib[index, i] = 0; } tmp += " -> " + (index + 1); loocedVertex.Add(index); } Console.WriteLine("Прохождение графа в ширину:"); Console.WriteLine(tmp); Console.ReadLine(); } private void Fill() { matrix = new int[n, n]; for (short i = 0; i < n; i++) { for (short j = 0; j < n; j++) { int tmp = rnd.Next(0, 2); matrix[i, j] = tmp; Console.Write(tmp + " "); } Console.WriteLine(); } Console.WriteLine(); } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д