Advertisement
sglienke

In-order tree traversal

Jun 24th, 2015
314
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. function TNodeEnumerator<T>.MoveNext: Boolean;
  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.       TNode<Integer>.Create(6,
  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.
Advertisement
RAW Paste Data Copied
Advertisement