Advertisement
Guest User

Untitled

a guest
Apr 4th, 2020
185
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. function BinaryTree(value, left = null, right = null) { // Деревом, по сути, будет узел со сзначением и двумя детьми, которые по дефолту null
  2.     this.value = value;           // Следует оставить либо эти 3 строчки, либо 3 строчки после этих
  3.     this.left = left;
  4.     this.right = right;
  5.     this.getValue = () => value;  // Вот тут мы укрываем значения от внешнего пользователя кода и даём ему только геттеры,
  6.     this.getLeft = () => left;    // потому что у меня с жавы такая привычка, так к нашим полям не будет прямого доступа
  7.     this.getRight = () => right;
  8. }
  9.  
  10. BinaryTree.prototype.toString = function () {  // Если имеются дети, то есть они не null'ы, то мы добавляем их к выводу
  11.     let leftPart = this.getLeft() === null ? "" : (this.getLeft().toString() + ' '); // Пробелы добавляем на этом этапе, а не на этапе return'а, шобы не было лишних пробелов при отсутствии детей
  12.     let rightPart = this.getRight() === null ? "" : (' ' + this.getRight().toString());
  13.     return leftPart + this.getValue() + rightPart; // В чём идея: часто бинарные деревья являются деревьсями поиска, так что
  14.     // значение в левом ребёнке < значение в родителе < значение в правом ребёнке
  15.     // Если нас попросят нати х, то мы смотрим в узел, если не совпадает, то сравниваем
  16.     // если х меньше значения в узле, обращаемся к левому ребёнку, иначе - к правому.
  17.     // Так вот. Если иходить из того, что дерево имеет такой вид, то данный способ выведет значения в дереве в отсортированном порядке
  18.     // Я хз, чё именно в этом задании хочут
  19. };
  20.  
  21. function printTree(binaryTree, depth = 0) { // Эта версия отражает иерархию. Глубина имеет дефолтное значение, которое ей присвоится, если мы не передадим другое
  22.     let dots = ""; // Мне кажется, точки маленько помогут осознать, кто чей ребёнок
  23.     for(let i = 0; i< depth; i++){
  24.         dots += '.';
  25.     }
  26.     console.log(dots, binaryTree.getValue()); //Сначала печатаем родителя, а потом двух детей
  27.     if(binaryTree.getLeft() !== null) printTree(binaryTree.getLeft(), depth + 1); // Тут не уверен в правильности проверки на undefined
  28.     if(binaryTree.getRight() !== null) printTree(binaryTree.getRight(), depth + 1);
  29. }
  30.  
  31. function printTree1(binaryTree){
  32.     console.log(binaryTree.toString());
  33. }
  34.  
  35. // Пример использования кода:
  36. let tree = new BinaryTree(7, new BinaryTree(4, new BinaryTree(2), new BinaryTree(6)), new BinaryTree(11));
  37. // Тут как раз дерево поиска, шоб продемонстрировать отсортированность вывода
  38. /*
  39.                 7
  40.               /  \
  41.              4    11
  42.            /  \
  43.           2    6
  44.  */
  45. printTree(tree);
  46. printTree1(tree);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement