SHOW:
|
|
- or go back to the newest paste.
1 | program InOrderTraversal; | |
2 | ||
3 | {$APPTYPE CONSOLE} | |
4 | ||
5 | uses | |
6 | SysUtils; | |
7 | ||
8 | type | |
9 | TNodeEnumerator<T> = class; | |
10 | ||
11 | TNode<T> = class | |
12 | strict private | |
13 | fLeft, fRight, fParent: TNode<T>; | |
14 | fValue: T; | |
15 | public | |
16 | constructor Create(const value: T; left, right: TNode<T>); | |
17 | destructor Destroy; override; | |
18 | ||
19 | function InOrder: TNodeEnumerator<T>; | |
20 | ||
21 | property Left: TNode<T> read fLeft; | |
22 | property Right: TNode<T> read fRight; | |
23 | property Parent: TNode<T> read fParent; | |
24 | property Value: T read fValue; | |
25 | end; | |
26 | ||
27 | TNodeEnumerator<T> = class | |
28 | protected | |
29 | fNode: TNode<T>; | |
30 | fStarted: Boolean; | |
31 | function GetCurrent: T; | |
32 | public | |
33 | constructor Create(node: TNode<T>); | |
34 | function GetEnumerator: TNodeEnumerator<T>; | |
35 | function MoveNext: Boolean; virtual; | |
36 | property Current: T read GetCurrent; | |
37 | end; | |
38 | ||
39 | TInOrderEnumerator<T> = class(TNodeEnumerator<T>) | |
40 | private | |
41 | function Next(node: TNode<T>): TNode<T>; | |
42 | public | |
43 | function MoveNext: Boolean; override; | |
44 | end; | |
45 | ||
46 | { TNode<T> } | |
47 | ||
48 | constructor TNode<T>.Create(const value: T; left, right: TNode<T>); | |
49 | begin | |
50 | fValue := value; | |
51 | fLeft := left; | |
52 | if Assigned(fLeft) then | |
53 | fLeft.fParent := Self; | |
54 | fRight := right; | |
55 | if Assigned(fRight) then | |
56 | fRight.fParent := Self; | |
57 | end; | |
58 | ||
59 | destructor TNode<T>.Destroy; | |
60 | begin | |
61 | fLeft.Free; | |
62 | fRight.Free; | |
63 | inherited; | |
64 | end; | |
65 | ||
66 | function TNode<T>.InOrder: TNodeEnumerator<T>; | |
67 | begin | |
68 | Result := TInOrderEnumerator<T>.Create(Self); | |
69 | end; | |
70 | ||
71 | { TNodeEnumerator<T> } | |
72 | ||
73 | constructor TNodeEnumerator<T>.Create(node: TNode<T>); | |
74 | begin | |
75 | fNode := node; | |
76 | end; | |
77 | ||
78 | function TNodeEnumerator<T>.GetCurrent: T; | |
79 | begin | |
80 | Result := fNode.Value; | |
81 | end; | |
82 | ||
83 | function TNodeEnumerator<T>.GetEnumerator: TNodeEnumerator<T>; | |
84 | begin | |
85 | Result := Self; | |
86 | end; | |
87 | ||
88 | - | parent: TNode<T>; |
88 | + | |
89 | begin | |
90 | Result := False; | |
91 | end; | |
92 | ||
93 | { TInOrderEnumerator<T> } | |
94 | ||
95 | function TInOrderEnumerator<T>.Next(node: TNode<T>): TNode<T>; | |
96 | begin | |
97 | if Assigned(node.Right) then | |
98 | begin | |
99 | Result := node.Right; | |
100 | while Assigned(Result.Left) do | |
101 | Result := Result.Left; | |
102 | end | |
103 | else | |
104 | begin | |
105 | Result := node.Parent; | |
106 | while Assigned(Result) do | |
107 | begin | |
108 | if Result.Left = node then | |
109 | Break; | |
110 | node := Result; | |
111 | Result := node.Parent; | |
112 | end; | |
113 | end; | |
114 | end; | |
115 | ||
116 | function TInOrderEnumerator<T>.MoveNext: Boolean; | |
117 | begin | |
118 | if not Assigned(fNode) then | |
119 | Exit(False); | |
120 | if not fStarted then | |
121 | begin | |
122 | while Assigned(fNode.Left) do | |
123 | fNode := fNode.Left; | |
124 | fStarted := True; | |
125 | end | |
126 | else | |
127 | fNode := Next(fNode); | |
128 | Result := Assigned(fNode); | |
129 | end; | |
130 | ||
131 | procedure Main; | |
132 | var | |
133 | root: TNode<Integer>; | |
134 | i: Integer; | |
135 | begin | |
136 | root := TNode<Integer>.Create(1, | |
137 | TNode<Integer>.Create(2, | |
138 | TNode<Integer>.Create(4, | |
139 | TNode<Integer>.Create(7, nil, nil), | |
140 | nil), | |
141 | TNode<Integer>.Create(5, nil, nil) | |
142 | ), | |
143 | TNode<Integer>.Create(3, | |
144 | - | for i in TInOrderEnumerator<Integer>.Create(root) do |
144 | + | |
145 | TNode<Integer>.Create(8, nil, nil), | |
146 | TNode<Integer>.Create(9, nil, nil) | |
147 | ), nil | |
148 | ) | |
149 | ); | |
150 | ||
151 | for i in root.InOrder do | |
152 | Writeln(i); | |
153 | ||
154 | root.Free; | |
155 | end; | |
156 | ||
157 | begin | |
158 | try | |
159 | Main; | |
160 | except | |
161 | on E: Exception do | |
162 | Writeln(E.ClassName, ': ', E.Message); | |
163 | end; | |
164 | Readln; | |
165 | ReportMemoryLeaksOnShutdown := True; | |
166 | end. |