Найти высоту заданного узла - 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);
- }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д