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. |