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

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

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

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

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

textual
Листинг программы
class Node
    {
        public string Name { get; set; }
        public Node Left { get; private set; }
        public Node Right { get; private set; }
 
        public Node(string name)
        {
            Name = name;
        }
 
        public Node(Node left=null, Node right=null)
        {
            Left = left;
            Right = right;
        }
 
 
        public Node SetLeftNode(string name)
        {
            if (string.IsNullOrEmpty(name)) throw new ArgumentException(nameof(name));
            Left = new Node(name);
            return Left;
        }
 
        public Node SetRightNode(string name)
        {
            if (string.IsNullOrEmpty(name)) throw new ArgumentException(nameof(name));
            Right = new Node(name);
            return Right;
        }
 
        public static void HeigthTree(Node t, ref int count, ref int heigth, ref int targetNodeHeight)
        {
            if (t == null) return;
                 
                if (count > heigth) //и длина пути от корня до текущего узла больше высоты дерева, то
                {
                   heigth = count; // полагаем в качестве высоты дерева длину пути до текущего узла
                }
 
                count++; // в любом случае увеличиваем длину пути от корня до текущего узла
                HeigthTree(t.Left, ref count, ref heigth, ref targetNodeHeight); //обходим левое поддерево
                HeigthTree(t.Right, ref count, ref heigth, ref targetNodeHeight); //обходим правое поддерево
                count--; //после чего уменьшаем длину пути от корня до текущего узла
        }
 
        public override string ToString()
        {
            return Name;
        }
 
 
        public void OutputTreeInfo()
        {
            int count = 0, height = 0, targetNodeHeight = 0;
            HeigthTree(this, ref count, ref height, ref targetNodeHeight);
            Console.WriteLine($"Tree with root Node: {Name}. Height: {height}");
            Console.WriteLine($"{Environment.NewLine}All nodes enumeration:{Environment.NewLine}");
            OutputTreeInfoRecursive(this, height, this);
        }
 
 
        public static void OutputTreeInfoRecursive(Node root, int treeHeight, Node targetNode = null)
        {
            int count = 0, height = 0, targetNodeHeight = 0;
 
            if (targetNode == null)
                return;
 
            Console.WriteLine($"{targetNode.Name}:  Height: {targetNode.GetHeight(treeHeight, root)}");
            
            OutputTreeInfoRecursive(root, treeHeight, targetNode.Left);
            OutputTreeInfoRecursive(root, treeHeight, targetNode.Right);
        }
 
 
        public int GetHeight(int treeHeight, Node rootNode)
        {
            int height = 0, count = 0, targetHeight = 0;
            GetTargetNodeHeightRecursively(ref count, ref height, ref targetHeight, rootNode, this);
            return treeHeight - targetHeight;
        }
 
        private void GetTargetNodeHeightRecursively(ref int count, ref int height, ref int targetHeight,  Node currentNode, Node targetNode)
        {
            if (currentNode == null)
                 return;
 
            if (count > height)
                height = count;
            
            if (currentNode.Equals(targetNode))
               targetHeight = count;
            
            count++;
            GetTargetNodeHeightRecursively(ref count, ref height, ref targetHeight, currentNode.Left, targetNode);
            GetTargetNodeHeightRecursively(ref count, ref height, ref targetHeight, currentNode.Right, targetNode);
            count--;
        }
    }
 
//...
static void Main(string[] args)
        {
            var root = new Node("Root");
            var l1 = root.SetLeftNode("NestedLeft1");
            var l2= root.SetRightNode("NestedRight1");
            l1.SetLeftNode("NestedLeft2-1");
            l1.SetRightNode("NestedRight2-1");
 
            var left23 = l2.SetLeftNode("NestedLeft2-2");
            l2.SetRightNode("NestedRight2-2");
            var subTerminal = left23.SetLeftNode("SubTerminal list");
            subTerminal.SetRightNode("Terminal");
 
            root.OutputTreeInfo(); 
            Console.ReadKey(true);
        }

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


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

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

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