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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
' Challenge 094
'
' TASK #2 � Binary Tree to Linked List
' Submitted by: Mohammad S Anwar
' You are given a binary tree.
'
' Write a script to represent the given binary tree as an object and flatten
' it to a linked list object. Finally print the linked list object.
'
' Example:
' Input:
'
' 1
' / \
' 2 3
' / \
' 4 5
' / \
' 6 7
'
' Output:
'
' 1 -> 2 -> 4 -> 5 -> 6 -> 7 -> 3
' input lines
Dim Shared lines() as String
' tree node
Type NodeType
value as Integer
left_node as NodeType Ptr
right_node as NodeType Ptr
End Type
' read lines from stdin
Sub read_lines()
Dim i as Integer
Open Cons for Input as #1
i = 0
Do Until Eof(1)
Redim Preserve lines(i) as String
Line Input #1, lines(i)
i = i+1
Loop
Close #1
End Sub
' parse lines, produce a tree
Function parse_subtree(row as Integer, col as Integer) as NodeType Ptr
Dim node as NodeType Ptr
'parse root
node = Callocate(1, Sizeof(NodeType))
If node=0 Then End -1
node->value = Val(Mid(lines(row), col, 1))
'parse children
if row+2 <= UBound(lines) Then
If col-2 >= 1 And Mid(lines(row+1), col-1, 1) = "/" Then
node->left_node = parse_subtree(row+2, col-2)
End If
If col+2 <= Len(lines(row+2)) And Mid(lines(row+1), col+1, 1) = "\" Then
node->right_node = parse_subtree(row+2, col+2)
End If
End If
parse_subtree = node
End Function
Function parse_tree() as NodeType Ptr
Dim root as String, col as Integer
root = Trim(lines(0)) ' remove spaces, leave only root number
col = InStr(lines(0), root) ' find its column
parse_tree = parse_subtree(0, col)
End Function
Sub delete_tree(node as NodeType Ptr)
if node->left_node Then delete_tree(node->left_node)
if node->right_node Then delete_tree(node->right_node)
Deallocate(node)
End Sub
' flatten a tree
Sub flatten_tree(root as NodeType Ptr)
Dim left_node as NodeType Ptr, right_node as NodeType Ptr, node as NodeType Ptr
If root <> 0 Then
left_node = root->left_node: flatten_tree(left_node)
right_node = root->right_node: flatten_tree(right_node)
root->left_node = 0
root->right_node = left_node
node = root
Do While node->right_node <> 0
node = node->right_node
Loop
node->right_node = right_node
End If
End Sub
Sub print_tree(root as NodeType Ptr)
Dim node as NodeType Ptr
node = root
Do While node <> 0
If node <> root Then Print " -> ";
Print Trim(Str(node->value));
node = node->right_node
Loop
Print
End Sub
' main
Dim tree as NodeType Ptr
read_lines
tree = parse_tree
flatten_tree tree
print_tree tree
delete_tree tree
|
