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