Advertisement
Tvor0zhok

СиАКОД Деревья 2

Feb 22nd, 2022
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.12 KB | None | 0 0
  1. using System;
  2. using System.IO;
  3.  
  4. namespace Program
  5. {
  6. class Program
  7. {
  8. static void Main()
  9. {
  10. BinaryTree tree = new BinaryTree();
  11.  
  12. using (StreamReader fileIn = new StreamReader("C:/Users/Acer/Desktop/input.txt"))
  13. {
  14. string line = fileIn.ReadToEnd();
  15. string[] data = line.Split(' ');
  16.  
  17. foreach (string item in data)
  18. {
  19. tree.Add(int.Parse(item));
  20. }
  21. }
  22.  
  23. Console.WriteLine("Прямой обход:");
  24. tree.Preorder();
  25.  
  26. Console.WriteLine("Симметричный обход:");
  27. tree.Inorder();
  28.  
  29. Console.WriteLine("Обратный обход:");
  30. tree.Postorder();
  31.  
  32. Console.Write("Введите целое число k (k >= 1): ");
  33. int k = int.Parse(Console.ReadLine());
  34.  
  35. Console.WriteLine("Кол-во узлов на k-ом уровне дерева равно: {0}", tree.countOfNodes(k));
  36. }
  37. };
  38.  
  39. public class BinaryTree
  40. {
  41. private class Node
  42. {
  43. public object inf; // инф. часть
  44. public Node left; // ссылка на лев. поддерево
  45. public Node right; // ссылка на прав. поддерево
  46.  
  47. // конструктор (создание узла)
  48. public Node(object nodeInf)
  49. {
  50. inf = nodeInf;
  51. left = null;
  52. right = null;
  53. }
  54.  
  55. // добавление узла в дерево
  56. public static void Add(ref Node r, object nodeInf)
  57. {
  58. if (r == null) r = new Node(nodeInf);
  59. else if (((IComparable)(r.inf)).CompareTo(nodeInf) > 0)
  60. Add(ref r.left, nodeInf);
  61. else
  62. Add(ref r.right, nodeInf);
  63. }
  64.  
  65. // подсчет узлов в дереве, расположенных на k-ом уровне
  66. public static int countOfNodes(Node r, int l)
  67. {
  68. if (r == null) return 0;
  69. else if (l == 1) return 1;
  70. else return countOfNodes(r.left, l - 1) + countOfNodes(r.right, l - 1);
  71. }
  72.  
  73. // прямой обход
  74. public static void Preorder(Node r)
  75. {
  76. if (r != null)
  77. {
  78. Console.Write("{0} ", r.inf);
  79. Preorder(r.left);
  80. Preorder(r.right);
  81. }
  82. }
  83.  
  84. // симметричный обход
  85. public static void Inorder(Node r)
  86. {
  87. if (r != null)
  88. {
  89. Inorder(r.left);
  90. Console.Write("{0} ", r.inf);
  91. Inorder(r.right);
  92. }
  93. }
  94.  
  95. // обратный обход
  96. public static void Postorder(Node r)
  97. {
  98. if (r != null)
  99. {
  100. Postorder(r.left);
  101. Postorder(r.right);
  102. Console.Write("{0} ", r.inf);
  103. }
  104. }
  105. };
  106.  
  107. Node tree; // ссылка на корень
  108.  
  109. // конструктор (создание дерева)
  110. public BinaryTree()
  111. {
  112. tree = null;
  113. }
  114.  
  115. public void Add(object nodeInf)
  116. {
  117. Node.Add(ref tree, nodeInf);
  118. }
  119.  
  120. public int countOfNodes(int l)
  121. {
  122. return Node.countOfNodes(tree, l);
  123. }
  124.  
  125. public void Preorder()
  126. {
  127. Node.Preorder(tree);
  128. Console.Write("\n");
  129. }
  130.  
  131. public void Inorder()
  132. {
  133. Node.Inorder(tree);
  134. Console.Write("\n");
  135. }
  136.  
  137. public void Postorder()
  138. {
  139. Node.Postorder(tree);
  140. Console.Write("\n");
  141. }
  142. };
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement