Dr. K. L. Metlov (dr_klm) wrote,
Dr. K. L. Metlov
dr_klm

рисуем деревья на J

На первый взгляд может показаться, что с деревьями в J работать неудобно (без указателей то !). Но оказывается, что упаковочных массивов для представления деревьев и работы с ними более чем достаточно. Другое дело, что стандартное их отображение не очень напоминает дерево. Точнее, напоминает дерево, как будто оно полу-прозрачное, мы держим его над головой и смотрим со стороны корней, что не очень привычно... Поэтому я и написал небольшую программку, позволяющую изображать деревья "обычным образом". Правда не любые, а только деревья в которых узлы помечены целыми числами (для меня этого вполне достаточно, а расширить программу на другой случай будет несложно). Программу можно скачать здесь (версия с DOS концами строк).

   load '~user/treeutils.ijs'   NB. загружаем программу при условии,
                                NB. что ее поместили в $JHOME/user/ .
NB. Теперь порисуем (в рамке слева стандартное отображение J соответст-
NB. вующей упаковки, справа -- отображение той-же упаковки программой):
   (; drawtree) <1                  NB. Дерево из одного узла
┌───┬──┐
│┌─┐│1 │
││1││  │
│└─┘│  │
└───┴──┘
   (; drawtree) 1;<<2               NB. из узла и под-узла
┌───────┬───┐
│┌─┬───┐│ 1 │
││1│┌─┐││ │ │
││ ││2│││ │ │
││ │└─┘││ 2 │
│└─┴───┘│   │
└───────┴───┘
   (; drawtree) 1;<2;<<3            NB. из трех узлов ;-)
┌───────────┬───┐
│┌─┬───────┐│ 1 │
││1│┌─┬───┐││ │ │
││ ││2│┌─┐│││ │ │
││ ││ ││3││││ 2 │
││ ││ │└─┘│││ │ │
││ │└─┴───┘││ │ │
│└─┴───────┘│ 3 │
└───────────┴───┘
   (; drawtree) 1;(<3);<<4          NB. снова из трех узлов ;-)
┌───────────┬────┐
│┌─┬───┬───┐│ 1  │
││1│┌─┐│┌─┐││┌┴┐ │
││ ││3│││4││││ │ │
││ │└─┘│└─┘││3 4 │
│└─┴───┴───┘│    │
└───────────┴────┘
      (; drawtree) 1;(3;(<5);<<6);<(4;(<7);<<8)   NB. двоичное
┌───────────────────────────┬────────┐
│┌─┬───────────┬───────────┐│   1    │
││1│┌─┬───┬───┐│┌─┬───┬───┐││ ┌─┴─┐  │
││ ││3│┌─┐│┌─┐│││4│┌─┐│┌─┐│││ │   │  │
││ ││ ││5│││6││││ ││7│││8││││ 3   4  │
││ ││ │└─┘│└─┘│││ │└─┘│└─┘│││┌┴┐ ┌┴┐ │
││ │└─┴───┴───┘│└─┴───┴───┘│││ │ │ │ │
│└─┴───────────┴───────────┘│5 6 7 8 │
└───────────────────────────┴────────┘
   (; drawtree) 1;(3;(<9);(<10);(5;(<11);<<12);<<6);<(4;(<7);<<8)
┌──────────────────────────────────────────────┬─────────────────┐
│┌─┬──────────────────────────────┬───────────┐│         1       │
││1│┌─┬───┬────┬─────────────┬───┐│┌─┬───┬───┐││     ┌───┴────┐  │
││ ││3│┌─┐│┌──┐│┌─┬────┬────┐│┌─┐│││4│┌─┐│┌─┐│││     │        │  │
││ ││ ││9│││10│││5│┌──┐│┌──┐│││6││││ ││7│││8││││     3        4  │
││ ││ │└─┘│└──┘││ ││11│││12│││└─┘│││ │└─┘│└─┘│││┌──┬─┴─┬───┐ ┌┴┐ │
││ ││ │   │    ││ │└──┘│└──┘││   ││└─┴───┴───┘│││  │   │   │ │ │ │
││ ││ │   │    │└─┴────┴────┘│   ││           ││9 10   5   6 7 8 │
││ │└─┴───┴────┴─────────────┴───┘│           ││      ┌┴─┐       │
│└─┴──────────────────────────────┴───────────┘│      │  │       │
│                                              │     11 12       │
└──────────────────────────────────────────────┴─────────────────┘

Для сравнения: программа на Схеме, на Руби. И конечно-же классика -- программа на C ! Интересно, кто-нибудь скажет, что программа на C понятнее ? ;-))
Tags: j
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 8 comments