回 帖 发 新 帖 刷新版面

主题:[原创]二叉树的层次遍历。。。急!!


哪位高手能解释一下,最好能给出代码

回复列表 (共6个回复)

沙发

前序,中序,后序
都是先左后右,前中后的区别是访问根结点的顺序。
前:先访问根结点,其次访问左子树,最后访问右子树。
中:先访问左子树,其次访问根结点,最后访问右子树。
后:先访问左子树,其次访问右子树,最后访问根结点。


代码:
procedure bianli(p);
begin
  if p.left<>null then bianli(p.left);
  visit(p.num);
  if p.right<>null then bianli(p.right);
end;

这个是前序遍历,其他两个遍历同理可得。
过程的参数是一个节点类型,visit指的是访问这个节点的数据。

还有什么看不明白的再说吧。

板凳

procedure pro(p:link);
begin
  if p^.left<>nil then pro(p^.left);
  writeln(p^.data);
  if p^.right<>nil then pro(p^.right);
end;

3 楼

宽搜一下就行了

4 楼

注意是层次遍历啊啊啊啊~~~
{层序遍历
使用一个先进先出的循环队列作为辅助手段
}
PROCEDURE LevelWays(t : Btree);
    var
        p : Btree;  {p表示当前结点}
        queue : array [0..MAX] of Btree; {循环队列queue[]用来存储结点}
        front, rear : integer;
    begin
        front := -1;
        rear := -1;
        if t <> nil then {先判断是否为空树}
        begin
            rear := 0;
            queue[rear] := t; {入队}
        end; {if}

        while front <> rear do {队列非空}
        begin
            front := (front + 1) mod MAX;{出队列,并输出结点}
            p := queue[front];
            write(p^.data:WIDTH);
            if p^.lc <> nil then {左孩子非空则入列}
            begin
                rear := (rear + 1) mod MAX;
                queue[rear] := p^.lc;
            end; {if}
            if p^.rc <> nil then {右孩子非空则入列}
            begin
                rear := (rear + 1) mod MAX;
                queue[rear] := p^.rc;
            end; {if}
        end; {while}
    end; {LevelWays}
{层序遍历:可以输出层号
使用循环队列记录结点的层次,设levelUp为上次打印结点层号,level为本层打印结点层号
}
PROCEDURE LevelPrint(t : Btree);
    type
        levelNode = record
                        level : integer;
                        pointer : Btree;
                    end;
    var
        p : Btree;  {p表示当前结点}
        queue : array [0..MAX] of levelNode; {循环队列queue[]用来存储levelNode结点}
        front, rear, levelUp, level : integer;
    begin
        front := -1;
        rear := -1;
        levelUp := 0;
        if t <> nil then {先判断是否为空树}
        begin
            rear := 0;
            queue[rear].level := 1; {结点层号入队}
            queue[rear].pointer := t; {结点内容入队}
        end; {if}

        while front <> rear do {队列非空}
        begin
            front := (front + 1) mod MAX;{出队列,并输出结点}
            level := queue[front].level; {记录当前结点的层号}
            p := queue[front].pointer; {记录当前结点的内容}
            if level = levelUp then {和上次输出的结点在同一层,只输出结点}
                write(p^.data:WIDTH)
            else {和上次输出的结点不在同一层,换行后输出结点并修改levelUp的值}
            begin
                writeln;
                write(p^.data:WIDTH);
                levelUp := level;
            end; {else}
            if p^.lc <> nil then {左孩子非空则入列}
            begin
                rear := (rear + 1) mod MAX;
                queue[rear].level := level + 1; {左孩子层号入列}
                queue[rear].pointer := p^.lc;  {左孩子结点入列}
            end; {if}
            if p^.rc <> nil then {右孩子非空则入列}
            begin
                rear := (rear + 1) mod MAX;
                queue[rear].level := level + 1; {右孩子层号入列}
                queue[rear].pointer := p^.rc;  {右孩子结点入列}
            end; {if}
        end; {while}
    end; {LevelPrint}

5 楼

我们正好今天学二叉树
谢谢了哦

6 楼


[em4]谢了·

我来回复

您尚未登录,请登录后再回复。点此登录或注册