.NET 4.x Бинарное дерево. Добавить вывод вершин и нумерацию - C#
Формулировка задачи:
Вообщем есть такая программа. Сюда нужно добавить методы, которые выводят на екран все вершины дерева(по 1 разу),и метод который нумерует его вершины в соответствии с порядком прямого обхода этого дерева. Буду очень благодарен людям, которые мне помогут
using System;
using System.Collections.Generic;
namespace BST
{
class Program
{
static void Main(string[] args)
{
try
{
Tree bst = new Tree(new List<int> { 5, 1, 7, 10, 13, 17 });
bst.Add(6);
bst.Add(8);
bst.Add(2);
Console.WriteLine("Way between {0}, {1}, {2}", 10, 17, bst.WayExists(10, 17));
Console.WriteLine("Way between {0}, {1}, {2}", 5, 2, bst.WayExists(5, 2));
Console.WriteLine("Way between {0}, {1}, {2}", 2, 5, bst.WayExists(2, 5));
Console.WriteLine(bst.CLRDetailed());
List<int> values = bst.LCR();
foreach (int element in values) Console.Write(element + " ");
Console.WriteLine("Minimal value: {0}", bst.GetMin());
bst.DelNode(1);
Console.WriteLine(bst.CLRDetailed());
Console.WriteLine("Minimal value: {0}", bst.GetMin());
Console.ReadKey();
}
catch (Exception exc)
{
Console.WriteLine(exc.Message);
Console.ReadKey();
}
}
}
public class Tree
{
private List<int> listRes = new List<int>();
private string stringRes = string.Empty;
private TreeNode root;
public class TreeNode
{
public int value;
public TreeNode left = null;
public TreeNode right = null;
public TreeNode(int value)
{
this.value = value;
}
}
public Tree()
{ }
public Tree(List<int> list) : this()
{
foreach (int element in list) Add(element);
}
public void Add(int value)
{
AddRecursion(ref root, value);
}
public int GetMin()
{
int min = int.MaxValue;
List<int> nodeValues = new List<int>(CLR());
foreach (int element in nodeValues) if (element < min) min = element;
return min;
}
public void DelNode(int value)
{
DelNode(ref root, value);
}
public List<int> CLR()
{
listRes.Clear();
return CLR(root);
}
public List<int> LCR()
{
listRes.Clear();
return LCR(root);
}
public List<int> RCL()
{
listRes.Clear();
return RCL(root);
}
public string CLRDetailed()
{
stringRes = string.Empty;
return CLRDetailed(root);
}
public string LCRDetailed()
{
listRes.Clear();
return LCRDetailed(root);
}
public string RCLDetailed()
{
listRes.Clear();
return RCLDetailed(root);
}
public List<int> BFS()
{
listRes.Clear();
return BFS(root);
}
public bool WayExists(int start, int goal)
{
return Search(Search(start), goal) != null;
}
public TreeNode Search(int value)
{
return Search(root, value);
}
private void AddRecursion(ref TreeNode node, int value)
{
if (node == null) node = new TreeNode(value);
else
{
if (value < node.value) AddRecursion(ref node.left, value);
else if (value > node.value) AddRecursion(ref node.right, value);
}
}
private List<int> CLR(TreeNode node)
{
if (node != null)
{
listRes.Add(node.value);
CLR(node.left);
CLR(node.right);
}
return listRes;
}
private List<int> LCR(TreeNode node)
{
if (node != null)
{
LCR(node.left);
listRes.Add(node.value);
LCR(node.right);
}
return listRes;
}
private List<int> RCL(TreeNode node)
{
if (node != null)
{
RCL(node.right);
listRes.Add(node.value);
RCL(node.left);
}
return listRes;
}
private string CLRDetailed(TreeNode node)
{
if (node != null)
{
stringRes += "Отримали значення:" + node.value.ToString() + Environment.NewLine;
stringRes += "Обходження лiвого пiддерева:" + Environment.NewLine;
CLRDetailed(node.left);
stringRes += "Обходження правого пiддерева:" + Environment.NewLine;
CLRDetailed(node.right);
}
else stringRes += "Значення вiдсутнє - NULL" + Environment.NewLine;
return stringRes;
}
private string LCRDetailed(TreeNode node)
{
if (node != null)
{
stringRes += "Обходження лiвого пiддерева:" + Environment.NewLine;
LCRDetailed(node.left);
stringRes += "Отримали значення:" + node.value.ToString() + Environment.NewLine;
stringRes += "Обходження правого пiддерева:" + Environment.NewLine;
LCRDetailed(node.right);
}
else stringRes += "Значення вiдсутнє - NULL" + Environment.NewLine;
return stringRes;
}
private string RCLDetailed(TreeNode node)
{
if (node != null)
{
stringRes += "Обходження правого пiддерева:" + Environment.NewLine;
RCLDetailed(node.right);
stringRes += "Отримали значення:" + node.value.ToString() + Environment.NewLine;
stringRes += "Обходження лівого пiддерева:" + Environment.NewLine;
RCLDetailed(node.right);
}
else stringRes += "Значення вiдсутнє - NULL" + Environment.NewLine;
return stringRes;
}
private List<int> BFS(TreeNode node)
{
var queue = new Queue<TreeNode>();
listRes.Add(node.value);
queue.Enqueue(node);
while (queue.Count != 0)
{
if (queue.Peek().left != null)
{
listRes.Add(queue.Peek().left.value);
queue.Enqueue(queue.Peek().left);
}
if (queue.Peek().right != null)
{
listRes.Add(queue.Peek().right.value);
queue.Enqueue(queue.Peek().right);
}
listRes.Add(queue.Peek().value);
queue.Dequeue();
}
return listRes;
}
private TreeNode Search(TreeNode node, int value)
{
if (node != null)
{
if (value == node.value) return node;
else if (value < node.value) return Search(node.left, value);
else return Search(node.right, value);
}
else return node;
}
private void DelNode(ref TreeNode node, int value)
{
if (node != null)
{
if (node.value < value) DelNode(ref node.right, value);
else if (node.value > value) DelNode(ref node.left, value);
else if (node.left == null && node.right == null) node = null;
else if (node.left == null) node = node.right;
else if (node.right == null) node = node.left;
else node = node.left;
}
}
}
}Решение задачи: «.NET 4.x Бинарное дерево. Добавить вывод вершин и нумерацию»
textual
Листинг программы
protected static string ShowTree(Node<T> root) {
if (root == null) {
throw new Exception("ПУСТО В ОГОРОДЕ НЕ ГУСТО");
}
if (root.Left == null && root.Right == null) {
return root.Value.ToString();
}
if (root.Left != null && root.Right == null) {
return root.Value + "(" + ShowTree(root.Left) + ",_)";
}
if (root.Left == null && root.Right != null) {
return root.Value + "(_," + ShowTree(root.Right) + ")";
}
return root.Value + "(" + ShowTree(root.Left) + ", " + ShowTree(root.Right) + ")";
}
public static string ST(BinaryTree<T> s){
return ShowTree(s.root);
}