(37)王道数据结构-树和森林的遍历

树的遍历

先根遍历

先根遍历。若树非空,先访问根结点,再依次对每棵子树进行先根遍历

代码逻辑
1
2
3
4
5
6
7
8
9
//树的先根遍历
void PreOrder(ThreeNode *R) {
if (R != NULL) {
visit(R); //访问根结点
while(R还有下一个子树T) {
PreOrder(T); //先根遍历下一棵子树
}
}
}
遍历序列

graph TD;
   A(("A"));
    B(("B"));
    C(("C"));
    D(("D"));
    E(("E"));
    F(("F"));
    G(("G"));
    H(("H"));
    I(("I"));
    J(("J"));
    K(("K"));
    
    A-->B;
    A-->C;
    A-->D;

    B-->E;
    B-->F;
    C-->G;
    D-->H;
    D-->I;
    D-->J;

    E-->K;
    E-->N(( ));
    style N fill:#f100,stroke-width:0px
    linkStyle 10 stroke:#0ff,stroke-width:0px

树的先根遍历序列与这棵树相应二叉树的先序序列相同。


graph TD;
    A(("A"));
    B(("B"));
    C(("C"));
    D(("D"));
    E(("E"));
    F(("F"));
    G(("G"));
    H(("H"));
    I(("I"));
    J(("J"));
    K(("K"));
    
    A-->B;
    B-->E;
    B-->C;

    E-->K;
    E-->F;
    C-->G;
    C-->D;

    D-->H;
    D-->N1(( ));
    H-->N2(( ));
    H-->I;
    I-->N3(( ));
    I-->J;

    style N1 fill:#f100,stroke-width:0px
    style N2 fill:#f100,stroke-width:0px
    style N3 fill:#f100,stroke-width:0px
    linkStyle 8 stroke:#0ff,stroke-width:0px
    linkStyle 9 stroke:#0ff,stroke-width:0px
    linkStyle 11 stroke:#0ff,stroke-width:0px

1
2
3
A       B               C       D
A (B E F) (C G) (D H I J)
A (B (E K) F) (C G) (D H I J)

后根遍历

后根遍历。若树非空,先依次对每棵子树进行后根遍历,最后再访问根结点。

代码逻辑
1
2
3
4
5
6
7
8
9
//树的后根遍历
void PostOrder(TreeNode *R) {
if (R != NULL) {
while(R还要下一个子树T) {
PostOrder(T); //后根遍历下一棵子树
}
visit(R); //访问根结点
}
}
遍历序列

graph TD;
    A(("A"));
    B(("B"));
    C(("C"));
    D(("D"));
    E(("E"));
    F(("F"));
    G(("G"));
    H(("H"));
    I(("I"));
    J(("J"));
    K(("K"));
    
    A-->B;
    A-->C;
    A-->D;

    B-->E;
    B-->F;
    C-->G;
    D-->H;
    D-->I;
    D-->J;

    E-->K;
    E-->N(( ));
    style N fill:#f100,stroke-width:0px
    linkStyle 10 stroke:#0ff,stroke-width:0px

树的后根遍历序列与这棵树相应二叉树的中序序列相同


graph TD;
    A(("A"));
    B(("B"));
    C(("C"));
    D(("D"));
    E(("E"));
    F(("F"));
    G(("G"));
    H(("H"));
    I(("I"));
    J(("J"));
    K(("K"));
    
    A-->B;
    B-->E;
    B-->C;

    E-->K;
    E-->F;
    C-->G;
    C-->D;

    D-->H;
    D-->N(( ));
    H-->N1(( ));
    H-->I;
    I-->N2(( ));
    I-->J;
    style N fill:#f100,stroke-width:0px
    style N1 fill:#f100,stroke-width:0px
    style N2 fill:#f100,stroke-width:0px
    linkStyle 8 stroke:#0ff,stroke-width:0px
    linkStyle 9 stroke:#0ff,stroke-width:0px
    linkStyle 11 stroke:#0ff,stroke-width:0px

1
2
3
     B               C       D           A
(E F B) (C G) (H I J D) A
((K E) F B) (C G) (H I I D) A

层次遍历

使用队列实现,采用的是广度优先遍历
1.若树非空,则根结点入队
2.若队列非空,对头元素出对并访问,同时将该元素的孩子依次入队
3.重复2直到队列为空

森林遍历

森林是m(m≥0)棵互不相交树的集合。每棵树去掉根结点后,其各个子树又组成森林。

先序遍历

若森林为非空,按照如下规则进行遍历:
1.访问森林中第一棵树的根结点
2.先序遍历第一棵树中根结点的子树森林
3.先序遍历除去第一棵树之后剩余的树构成的森林

遍历序列

graph TD;
    B(("B"));
    C(("C"));
    D(("D"));
    E(("E"));
    F(("F"));
    G(("G"));
    H(("H"));
    I(("I"));
    J(("J"));
    K(("K"));
    L(("L"));
    M(("M"));
    
    B-->E;
    B-->F;
    E-->K;
    E-->L;

    C-->G;
    
    D-->H;
    D-->I;
    D-->J;
    H-->M;

效果等同于依次对各个树进行先序遍历


graph TD;
    B(("B"));
    C(("C"));
    D(("D"));
    E(("E"));
    F(("F"));
    G(("G"));
    H(("H"));
    I(("I"));
    J(("J"));
    K(("K"));
    L(("L"));
    M(("M"));
    
    B-->E;
    B-->C;
    
    E-->K;
    E-->F;
    C-->G;
    C-->D;

    K-->N1(( ));
    K-->L;
    D-->H;
    D-->N2(( ));

    H-->M;
    H-->I;

    I-->N3(( ));
    I-->J;

    style N1 fill:#f100,stroke-width:0px
    style N2 fill:#f100,stroke-width:0px
    style N3 fill:#f100,stroke-width:0px
    linkStyle 6 stroke:#0ff,stroke-width:0px
    linkStyle 9 stroke:#0ff,stroke-width:0px
    linkStyle 12 stroke:#0ff,stroke-width:0px

1
2
3
     B               C       D           A          
(E F B) (C G) (H I J D) A
((K E) F B) (C G) (H I I D) A

中序遍历

若森林为非空,按照如下规则进行遍历:
1.中序遍历森林中第一棵树的根结点的子树森林
2.访问第一棵树的根结点
3.中序遍历除去第一棵树之后剩余的树构成的森林

遍历序列

graph TD;
    B(("B"));
    C(("C"));
    D(("D"));
    E(("E"));
    F(("F"));
    G(("G"));
    H(("H"));
    I(("I"));
    J(("J"));
    K(("K"));
    L(("L"));
    M(("M"));
    
    B-->E;
    B-->F;
    E-->K;
    E-->L;

    C-->G;
    
    D-->H;
    D-->I;
    D-->J;
    H-->M;

效果等同于依次对各个树进行中序遍历


graph TD;
    B(("B"));
    C(("C"));
    D(("D"));
    E(("E"));
    F(("F"));
    G(("G"));
    H(("H"));
    I(("I"));
    J(("J"));
    K(("K"));
    L(("L"));
    M(("M"));
    
    B-->E;
    B-->C;
    
    E-->K;
    E-->F;
    C-->G;
    C-->D;

    K-->N1(( ));
    K-->L;
    D-->H;
    D-->N2(( ));

    H-->M;
    H-->I;

    I-->N3(( ));
    I-->J;

    style N1 fill:#f100,stroke-width:0px
    style N2 fill:#f100,stroke-width:0px
    style N3 fill:#f100,stroke-width:0px
    linkStyle 6 stroke:#0ff,stroke-width:0px
    linkStyle 9 stroke:#0ff,stroke-width:0px
    linkStyle 12 stroke:#0ff,stroke-width:0px

1
2
3
     B               C       D           
(E F B) (G C) ( H I J D)
((K L E) F B) (C G) ((M H) I J D)

(37)王道数据结构-树和森林的遍历
https://www.eldpepar.com/iecore/51496/
作者
EldPepar
发布于
2022年8月10日
许可协议