Найти высоту заданного узла - C#

Узнай цену своей работы

Формулировка задачи:

Есть реализация высоты дерева:
Листинг программы
  1. public static void HeigthTree(Node t, ref int count, ref int heigth)
  2. {
  3. if (t!=null) // если текущий узел не пустой
  4. {
  5. if (count > heigth) //и длина пути от корня до текущего узла больше высоты дерева, то
  6. {
  7. heigth=count; // полагаем в качестве высоты дерева длину пути до текущего узла
  8. }
  9. count++; // в любом случае увеличиваем длину пути от корня до текущего узла
  10. HeigthTree(t.left, ref count, ref heigth); //обходим левое поддерево
  11. HeigthTree(t.rigth, ref count, ref heigth); //обходим правое поддерево
  12. count--; //после чего уменьшаем длину пути от корня до текущего узла
  13. }
  14. }
Высота узла-это длина пути от этого узла к самому нижнему листу.Вопрос,как реализовать эту самую высоту...

Решение задачи: «Найти высоту заданного узла»

textual
Листинг программы
  1. class Node
  2.     {
  3.         public string Name { get; set; }
  4.         public Node Left { get; private set; }
  5.         public Node Right { get; private set; }
  6.  
  7.         public Node(string name)
  8.         {
  9.             Name = name;
  10.         }
  11.  
  12.         public Node(Node left=null, Node right=null)
  13.         {
  14.             Left = left;
  15.             Right = right;
  16.         }
  17.  
  18.  
  19.         public Node SetLeftNode(string name)
  20.         {
  21.             if (string.IsNullOrEmpty(name)) throw new ArgumentException(nameof(name));
  22.             Left = new Node(name);
  23.             return Left;
  24.         }
  25.  
  26.         public Node SetRightNode(string name)
  27.         {
  28.             if (string.IsNullOrEmpty(name)) throw new ArgumentException(nameof(name));
  29.             Right = new Node(name);
  30.             return Right;
  31.         }
  32.  
  33.         public static void HeigthTree(Node t, ref int count, ref int heigth, ref int targetNodeHeight)
  34.         {
  35.             if (t == null) return;
  36.                  
  37.                 if (count > heigth) //и длина пути от корня до текущего узла больше высоты дерева, то
  38.                 {
  39.                    heigth = count; // полагаем в качестве высоты дерева длину пути до текущего узла
  40.                 }
  41.  
  42.                 count++; // в любом случае увеличиваем длину пути от корня до текущего узла
  43.                 HeigthTree(t.Left, ref count, ref heigth, ref targetNodeHeight); //обходим левое поддерево
  44.                 HeigthTree(t.Right, ref count, ref heigth, ref targetNodeHeight); //обходим правое поддерево
  45.                 count--; //после чего уменьшаем длину пути от корня до текущего узла
  46.         }
  47.  
  48.         public override string ToString()
  49.         {
  50.             return Name;
  51.         }
  52.  
  53.  
  54.         public void OutputTreeInfo()
  55.         {
  56.             int count = 0, height = 0, targetNodeHeight = 0;
  57.             HeigthTree(this, ref count, ref height, ref targetNodeHeight);
  58.             Console.WriteLine($"Tree with root Node: {Name}. Height: {height}");
  59.             Console.WriteLine($"{Environment.NewLine}All nodes enumeration:{Environment.NewLine}");
  60.             OutputTreeInfoRecursive(this, height, this);
  61.         }
  62.  
  63.  
  64.         public static void OutputTreeInfoRecursive(Node root, int treeHeight, Node targetNode = null)
  65.         {
  66.             int count = 0, height = 0, targetNodeHeight = 0;
  67.  
  68.             if (targetNode == null)
  69.                 return;
  70.  
  71.             Console.WriteLine($"{targetNode.Name}:  Height: {targetNode.GetHeight(treeHeight, root)}");
  72.            
  73.             OutputTreeInfoRecursive(root, treeHeight, targetNode.Left);
  74.             OutputTreeInfoRecursive(root, treeHeight, targetNode.Right);
  75.         }
  76.  
  77.  
  78.         public int GetHeight(int treeHeight, Node rootNode)
  79.         {
  80.             int height = 0, count = 0, targetHeight = 0;
  81.             GetTargetNodeHeightRecursively(ref count, ref height, ref targetHeight, rootNode, this);
  82.             return treeHeight - targetHeight;
  83.         }
  84.  
  85.         private void GetTargetNodeHeightRecursively(ref int count, ref int height, ref int targetHeight,  Node currentNode, Node targetNode)
  86.         {
  87.             if (currentNode == null)
  88.                  return;
  89.  
  90.             if (count > height)
  91.                 height = count;
  92.            
  93.             if (currentNode.Equals(targetNode))
  94.                targetHeight = count;
  95.            
  96.             count++;
  97.             GetTargetNodeHeightRecursively(ref count, ref height, ref targetHeight, currentNode.Left, targetNode);
  98.             GetTargetNodeHeightRecursively(ref count, ref height, ref targetHeight, currentNode.Right, targetNode);
  99.             count--;
  100.         }
  101.     }
  102.  
  103. //...
  104. static void Main(string[] args)
  105.         {
  106.             var root = new Node("Root");
  107.             var l1 = root.SetLeftNode("NestedLeft1");
  108.             var l2= root.SetRightNode("NestedRight1");
  109.             l1.SetLeftNode("NestedLeft2-1");
  110.             l1.SetRightNode("NestedRight2-1");
  111.  
  112.             var left23 = l2.SetLeftNode("NestedLeft2-2");
  113.             l2.SetRightNode("NestedRight2-2");
  114.             var subTerminal = left23.SetLeftNode("SubTerminal list");
  115.             subTerminal.SetRightNode("Terminal");
  116.  
  117.             root.OutputTreeInfo();
  118.             Console.ReadKey(true);
  119.         }

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


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

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

11   голосов , оценка 4.182 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы