blob: fb4455fd53a4d43582303d6e891d3359f6e11f38 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
InvertTree←{
⍝ ⍵: Full binary tree in the format
⍝ Node number (ID), value, parent
⍝
⍝ 1
⍝ / \
⍝ 2 3
⍝ / \ / \
⍝ 4 5 6 7
⍝
⍝ For example, the above tree in depth-first pre-order traversal
⍝ n ← 0 1 2 3 4 5 6
⍝ v ← 1 2 4 5 3 6 7
⍝ p ← 0 0 1 1 0 4 4
(n v p)←⍵
TreeMatrix←{
⍝ Binary matrix for a full binary tree
⍝ Each row is a binary mask for elements on that row
⍝
⍝ For the example tree:
⍝ v⌿⍤1⍨ TreeMatrix p
⍝ 1 0 0 0
⍝ 2 3 0 0
⍝ 4 5 6 7
⍝
⎕IO←0
⍺←0
r←⍵(∨⌿∘.=)⍨,⍺
c←⍸r
0≡⍺:(↑1(0@0⊢r))⍪(1↓c)∇ ⍵
⍬≡c:⍬⍴⍨0,⍴⍵
r⍪(c ∇ ⍵)
}
InvertValues←{
⍝ Horizontally flip values at each level of the tree
⍵≡⍬⍴⍨0,⊃⌽⍴⍵:⍺ ⍝ No more rows: Return inverted values
(⌽@(⍸1⌷⍵)⊢⍺)∇ 1↓⍵ ⍝ Horizontal flip ∇ Recurse remaining levels / rows
}
iv←v InvertValues TreeMatrix p
(n iv p) ⍝ Return inverted tree
}
|
