(37)王道数据结构-树和森林的遍历
树的遍历
先根遍历
先根遍历。若树非空,先访问根结点,再依次对每棵子树进行先根遍历
代码逻辑
1 |
|
遍历序列
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 |
|
后根遍历
后根遍历。若树非空,先依次对每棵子树进行后根遍历,最后再访问根结点。
代码逻辑
1 |
|
遍历序列
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 |
|
层次遍历
使用队列实现,采用的是广度优先遍历
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 |
|
中序遍历
若森林为非空,按照如下规则进行遍历:
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 |
|
(37)王道数据结构-树和森林的遍历
https://www.eldpepar.com/iecore/51496/