C++-二叉树

二叉树遍历:前序遍历、中序遍历、后序遍历、层序遍历

二叉树图

前序遍历(根左右)

操作

1.访问根节点

2.遍历左子树

3.遍历右子树

步骤

以下步骤使用根左右原则

1.分析第一层根结点F,写出先序遍历顺序FCE

先序遍历顺序:FCE

2.分析第二层,C、A、D和E、G组成小二叉树,写出先序遍历顺序CAD、EG

先序遍历顺序:FC(AD)E(G)

3.分析第三层,D、B和G、H、P组成小二叉树,写出先序遍历顺序DB、GHP

先序遍历顺序:FC(AD(B)E(G(HP))

4.去括号

先序遍历顺序:FCADBEGHP

中序遍历(左根右)

操作

1.遍历左子树

2.访问根节点

3.遍历右子树

步骤

以下步骤使用左根右原则

1.分析第一层根结点F,写出先序遍历顺序CFE

先序遍历顺序:CFE

2.分析第二层,A、C、D和E、G组成小二叉树,写出先序遍历顺序ACD、EG

先序遍历顺序:(A)C(D)FE(G)

3.分析第三层,B、D和H、G、P组成小二叉树,写出先序遍历顺序BD、HGP

先序遍历顺序:(A)C((B)D)FE((H)G(P))

4.去括号

先序遍历顺序:ACBDFEHGP

后序遍历(左右根)

操作

1.遍历左子树

2.遍历右子树

3.访问根节点

步骤

以下步骤使用左右根原则

1.分析第一层根结点F,写出先序遍历顺序CEF

先序遍历顺序:CEF

2.分析第二层,A、D、C和G、E组成小二叉树,写出先序遍历顺序ADC、GE

先序遍历顺序:(AD)C(G)EF

3.分析第三层,B、D和H、P、G组成小二叉树,写出先序遍历顺序BD、HPG

先序遍历顺序:(A(B)D)C((HP)G)EF

4.去括号

先序遍历顺序:ABDCHPGEF

层序遍历

操作

按层从上往下从左往右遍历

第二层

第三层

步骤

以下步骤使用层序遍历原则

1.分析第一层根结点F,写出层序遍历顺序F

层序遍历顺序:F

2.分析第二层,写出层序遍历顺序CE

层序遍历顺序:FCE

3.分析第三层,写出先序遍历顺序ADG

层序遍历顺序:FCEADG

4.分析第三层,写出先序遍历顺序BHP

层序遍历顺序:FCEADGBHP