View difference between Paste ID: PArqe1Tq and F9SUNQ9m
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.