| Copyright | Copyright (C) 2021 Yoo Chung |
|---|---|
| License | GPL-3.0-or-later |
| Maintainer | dev@chungyc.org |
| Safe Haskell | Safe-Inferred |
| Language | GHC2021 |
Problems.P64
Description
Part of Ninety-Nine Haskell Problems. Some solutions are in Solutions.P64.
Documentation
layoutInorder :: Tree a -> Tree (a, (Int, Int)) Source #
Let's say we want to draw a binary tree. In preparation, a layout algorithm is required to determine the position of each node in a rectangular grid. Several layout methods are conceivable. One of them is shown in the illustration below:
In this layout strategy, the position of a node \(v\) is obtained by the following two rules:
- \(x(v)\) is equal to the position of the node \(v\) in the in-order sequence.
- \(y(v)\) is equal to the depth of the node \(v\) in the tree.
Write a function to annotate each node of the tree with a position, where \((1,1)\) is the top left corner of the rectangle bounding the drawn tree.
Examples
>>>layoutInorder tree64Branch ('n',(8,1)) (Branch ('k',(6,2)) (Branch ('c',(2,3)) ...
Notes
In fact, the image was rendered to SVG using the return value of layoutInorder
with writeSVG. The images for Problems.P65 and Problems.P66
were also rendered similarly.