Delphi二叉树链表的建立及四种遍历方法

program BiTree;

{$APPTYPE CONSOLE}

uses
  SysUtils,Contnrs;

type
  {二叉树定义}
  PBiTree=^TBiTree;
  TBiTree = record
    Data  :Char;      //数据
    lChild:PBiTree;   //左孩子指针
    rChild:PBiTree;   //右孩子指针
  end;


//按前序遍历创建二叉树
function CreateTree(): PBiTree;
var
  ch: Char;
  root: PBiTree;
begin
 // Writeln('Please input the data,''#'' is the end.');
  Readln(ch);
  if ch = '#' then
  begin
    Result := nil;
    Exit;
  end
  else
  begin
    New(root);
    root^.Data := ch;
    root^.lChild := CreateTree();
    root^.rChild := CreateTree();
    Result := root;
  end;
  Writeln('OK!');   //输出此行代表一个树节点构建成功
end;


//前序遍历二叉树根左右 (由根开始，由左到右，第一次到达输出)
procedure PreOrder(root: PBiTree);
begin
  if Assigned(root) then
  begin
    Write(root^.Data);
    preorder(root^.lChild);
    preorder(root^.rChild);
  end;
end;


//中序遍历二叉树左根右  (由根开始，由左到右，第二次到达输出)
procedure InOrder(root: PBiTree);
begin
  if Assigned(root) then
  begin
    inorder(root^.lChild);
    Write(root^.Data);
    inorder(root^.rChild);
  end;
end;


//后序遍历二叉树左右根   (由根开始，由左到右，第三次到达输出)
procedure PostOrder(root: PBiTree);
begin
  if Assigned(root) then
  begin
    postorder(root^.lChild);
    postorder(root^.rChild);
    Write(root^.Data);
  end;
end;


//二叉树深度计算
function TreeDepth(root: PBiTree): Integer;
var
  depth, dl, dr: integer;
begin
  if not Assigned(root) then
    depth := 0
  else
  begin
    dl := TreeDepth(root^.lChild); //获取左子树深度
    dr := TreeDepth(root^.rChild); //获取右子树深度
    if dl > dr then
      depth := dl + 1
    else
      depth := dr + 1;
  end;
  Result := depth;
end;

//计算二叉树叶子数
function NumofLeaf(root: PBiTree): Integer;
var
  num, num1, num2: Integer;
begin
  if Assigned(root) then
  begin
    if (not Assigned(root^.lChild)) and (not Assigned(root^.rChild)) then
      num := 1
    else
    begin
      num1 := NumofLeaf(root^.lChild);  //获取左子树叶子数
      num2 := NumofLeaf(root^.rChild);  //获取右子树叶子数
      num := num1 + num2;
    end;
  end
  else
    num := 0;
  Result := num;
end;

//层序遍历二叉树，用到队列
procedure LevelOrder(root: PBiTree);
var
 Queue: TQueue;
 BiTreeDB:PBiTree;
begin
  if Assigned(root) then
  begin
    Queue:=TQueue.Create;
    Queue.Push(root);          //根节点进队列
    while Queue.Count>0 do     //队列不为空判断
    begin
      New(BiTreeDB);
      BiTreeDB:=Queue.Peek;
      Write(BiTreeDB^.Data);   //打印节点数据
      if BiTreeDB.lChild <>nil then  Queue.Push(BiTreeDB.lChild);   //如果有左孩子，入队列
      if BiTreeDB.rChild <>nil then  Queue.Push(BiTreeDB.rChild);   //如果有右孩子，入队列
      Queue.Pop;     //已经遍历过的节点出队列
    end;
    Dispose(BiTreeDB);
  end;
end;


var
  root: PBiTree;
  i: Integer;

begin
  Writeln('Please input Nodes of the BinTree,if input # is mean the child is empty.');
  root := CreateTree();
  if root = nil then
    Writeln('This is an empty tree!')
  else
  begin
    Writeln('1.前序遍历二叉树');
    PreOrder(root);
    Writeln;
    Writeln('2.中序遍历二叉树');
    InOrder(root);
    Writeln;
    Writeln('3.后序遍历二叉树');
    PostOrder(root);
    Writeln;
    Writeln('4.层序遍历二叉树');
    LevelOrder(root);
    Writeln;
  end;
  Writeln;
  Writeln('二叉树深度：  ', TreeDepth(root));
  Writeln('二叉树叶子数：  ', NumofLeaf(root));
  Readln;
end.

测试二叉树模型图：

程序运行结果图：