Бинарное дерево. Обход в ширину - 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();
        }
    }
}

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


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

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

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