Как разобраться с деревьями в C#

@r2d24 · Регистрация: 17.06.2015

Начал изучать C#, знания нулевые.
Нужно создать дерево и определить, сколько вершин дерева, имеют только одного потомка.

Мне помогали товарищи ро учебе, но у них такие же знания как у меня.
Вот что мы сделали, прошу указать на ошибки:

C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Drevo drev = new Drevo(1);
            drev.Left = new Drevo(2);
            drev.Left.Left = new Drevo(2.1);
            drev.Left.Right = new Drevo(2.2);
            drev.Right = new Drevo(3);
            drev.Right.Left = new Drevo(3.1);
            drev.Right.Right = new Drevo(3.2);
            drev.Right.Right.Right = new Drevo(4);
            drev.Left.Left.Left = new Drevo(5);
            Console.WriteLine(@"
          {0}    
      {1}       {2}  
   {3}  {4}  {5}  {6}
{7}                  {8}", drev.Data, drev.Left.Data, drev.Right.Data, drev.Left.Left.Data, drev.Left.Right.Data, drev.Right.Left.Data, drev.Right.Right.Data, drev.Right.Right.Right.Data, drev.Left.Left.Left.Data);
 
            Console.WriteLine(drev.Count());
            Console.ReadKey();
        }
    class Drevo
    {
        
         public double Data { get; set; }
            public Drevo Left { get; set; }
            public Drevo Right { get; set; }
        }
 
        public void Drevo(double data)
        {
            this.Data = data;
        }
        public int Count()
        {
            
            if ((Left != null && Right == null) || (Left == null && Right != null))  
            {
                int result = Left.Count() + Right.Count();
                return result;
            }
          return 0;
        }
    }       
   }
}

@MinoMoto · 17.06.2015, 22:40

1)Что должно делать твое дерево?
2)Тебе нужно бинарное дерево?
3)Если не бинарное дерево, то по какому принципу должны добавляться элементы в дерево?

@Storm23 · 17.06.2015, 23:43

Сообщение от r2d24

Нужно создать дерево и определить, сколько вершин дерева, имеют только одного потомка.

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
namespace ConsoleApplication196
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var root = new TreeNode<int> { Value = 11 };
            root.Add(12).Add(13);
            root.Add(14);
            root.Add(15).Add(16);
 
            var count = root.ThisAndAllChilds.Where(n=>n.Count == 1).Count();
 
            Console.WriteLine("Count: " + count);
 
            Console.ReadLine();
        }
    }
 
    public class TreeNode<T> : List<TreeNode<T>>
    {
        public T Value { get; set; }
 
        public TreeNode<T> Add(T value)
        {
            var node = new TreeNode<T> { Value = value };
            Add(node);
            return node;
        }
 
        public IEnumerable<TreeNode<T>> ThisAndAllChilds
        {
            get
            {
                yield return this;
 
                foreach (var child in this)
                foreach (var c in child.ThisAndAllChilds)
                    yield return c;
            }
        }
    }
}

@MrCold · 18.06.2015, 00:18

Не по теме:

и ещё удивила запись

Сообщение от Storm23

public class TreeNode<T> : List<TreeNode<T>>

@r2d24 · 18.06.2015, 10:28 **[ТС]**

За задачу спасибо, только мне не понятно, почему, если задать дерево

C#

root.Add(12).Add(13);
            root.Add(12).Add(13).Add(19);
            root.Add(12).Add(13).Add(20);
            root.Add(14);
            root.Add(15).Add(16);
            root.Add(15).Add(16).Add(17);
            root.Add(15).Add(16).Add(18);

То количество, выдает 10. Насколько я понял, должно быть 6 ?

@Storm23 · 18.06.2015, 12:17

r2d24, вы неправильно создаете дерево. Каждый(!) вызов Add создает новую вершину (даже если вы передаете то же самое число).
То дерево, которое вы пытаетесь создать должно выглядеть так:

C#

var node12 = root.Add(12);
var node13 = node12.Add(13);
node13.Add(19);
node13.Add(20);
root.Add(14);
var node15 = root.Add(15);
var node16 = node15.Add(16);
node16.Add(17);
node16.Add(18);

Добавлено через 11 минут
Добавил вывод дерева в консоль, что бы легче было ориентироваться:

C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleApplication196
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var root = new TreeNode<int> { Value = 11 };
            var node12 = root.Add(12);
            var node13 = node12.Add(13);
            node13.Add(19);
            node13.Add(20);
            root.Add(14);
            var node15 = root.Add(15);
            var node16 = node15.Add(16);
            node16.Add(17);
            node16.Add(18);
 
            Console.WriteLine("Tree:");
            Console.WriteLine(root.GetAsString());
 
            var count = root.ThisAndAllChilds.Where(n => n.Count == 1).Count();
 
            Console.WriteLine();
            Console.WriteLine("Count: " + count);
 
            Console.ReadLine();
        }
    }
 
    public class TreeNode<T> : List<TreeNode<T>>
    {
        public T Value { get; set; }
 
        public TreeNode<T> Add(T value)
        {
            var node = new TreeNode<T> { Value = value };
            Add(node);
            return node;
        }
 
        public IEnumerable<TreeNode<T>> ThisAndAllChilds
        {
            get
            {
                yield return this;
 
                foreach (var child in this)
                    foreach (var c in child.ThisAndAllChilds)
                        yield return c;
            }
        }
 
        public string GetAsString(int intend = 0)
        {
            var sb = new StringBuilder();
            sb.AppendLine(new string(' ', intend) + Value);
            foreach (var child in this)
                sb.Append(child.GetAsString(intend + 2));
 
            return sb.ToString();
        }
    }
}

В данном примере одного потомка имеют только вершины 12 и 15. Соответственно программа выдает 2.

@MinoMoto 5 / 5 / 2 Регистрация: 25.10.2014 Сообщений: 29
	17.06.2015, 22:40	2
	1)Что должно делать твое дерево? 2)Тебе нужно бинарное дерево? 3)Если не бинарное дерево, то по какому принципу должны добавляться элементы в дерево? 0

@MrCold
	18.06.2015, 00:18 #4
	Не по теме: и ещё удивила запись Сообщение от Storm23 public class TreeNode<T> : List<TreeNode<T>> 0

Опции темы

Как разобраться с деревьями в C#

Решение