unit1.pas

二叉树回溯

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, ComCtrls, ToolWin, StdCtrls, ExtCtrls, XPMan, Contnrs, ImgList;

type
  TForm1 = class(TForm)
    TreeView1: TTreeView;
    Splitter1: TSplitter;
    Memo1: TMemo;
    ToolBar1: TToolBar;
    ToolButton1: TToolButton;
    ImageList1: TImageList;
    procedure ToolButton1Click(Sender: TObject);
    procedure FormCreate(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
    procedure Visit(Node:TTreeNode; S:TStack);
    function LeftNode(Node:TTreeNode):TTreeNode;
    function RightNode(Node:TTreeNode):TTreeNode;
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

function TForm1.LeftNode(Node: TTreeNode): TTreeNode;
begin
  Result:=nil;
  if not Assigned(Node) then
  begin
    Exit;
  end;
  Result:=Node.getFirstChild;
end;

function TForm1.RightNode(Node: TTreeNode): TTreeNode;
begin
  Result:=nil;
  if not Assigned(Node) then
  begin
    Exit;
  end;
  if Node.Count<2 then
  begin
    Exit;
  end;
  Result:=Node.Item[1];
end;

procedure TForm1.ToolButton1Click(Sender: TObject);
var
  AStack:TStack;
begin
  Memo1.Clear;
  AStack:=TStack.Create;
  try
    Visit(Self.TreeView1.Items[0],AStack);
    Memo1.Lines.Add('-----[OVER]-----');
  finally
    AStack.Free;
  end;
end;

procedure TForm1.Visit(Node:TTreeNode; S:TStack);
var
  ANode:TTreeNode;
begin
  if not Assigned(Node) then
  begin
    while (s.Count>0)and(Integer(TTreeNode(S.Peek).Data)=2) do
    begin
      ANode:=TTreeNode(s.Pop);
      ANode.ImageIndex:=39;
      ANode.SelectedIndex:=39;
      Memo1.Lines.Add('<-出栈 '+ANode.Text);
      TreeView1.Refresh;
      Sleep(1000);
    end;
    if s.Count=0 then
    begin
      Exit;
    end;
    ANode:=TTreeNode(S.Peek);
    ANode.Data:=Pointer(2);
    Visit(RightNode(ANode),S);
  end
  else
  begin
    s.Push(Node);
    Node.ImageIndex:=40;
    Node.SelectedIndex:=40;
    Memo1.Lines.Add('进栈-> '+Node.Text);
    TreeView1.Refresh;
    Sleep(1000);
    Node.Data:=Pointer(1);
    Visit(LeftNode(Node),S);
  end;
end;

procedure TForm1.FormCreate(Sender: TObject);
var
  I:Integer;
begin
  for I := 0 to TreeView1.Items.Count-1 do
  begin
    TreeView1.Items[i].Expanded:=True;
  end;
  TreeView1.Selected:=nil;
end;

end.