二叉树的前序、中序、后序遍历详解

二叉树的前序、中序、后序遍历详解

引用

CSDN

1.

https://m.blog.csdn.net/weixin_62803673/article/details/142871517

二叉树的遍历是数据结构和算法中的基础知识，包括前序、中序和后序三种遍历方式。本文将通过详细的规则说明和实例图解，帮助读者理解这三种遍历方式的实现过程，并探讨已知两种遍历序列如何重建二叉树的问题。

前序遍历

遍历规则

1. 先遍历根节点
2. 再遍历左节点
3. 最后遍历右节点

前序遍历的用例图（中**——>左——>右**）

二叉树如图所示
先遍历根节点1
再遍历左子树

左子树的先序顺序为2——>4——>5（中——>左——>右）
最后遍历右子树

右子树的先序顺序为3——>6——>7（中——>左——>右）
最后可得出先序顺序为1——>2——>4——>5——>3——>6——>7

中序遍历

遍历规则

1. 先遍历左节点
2. 再遍历根节点
3. 最后遍历右节点

中序遍历的图解流程（左——>中——>右）

二叉树如图所示
先遍历左子树
左子树的中序顺序为4——>2——>5（中——>左——>右）
再遍历根节点1
最后遍历右子树
右子树的中序顺序为6——>3——>7（左——>中——>右）
最后可得出中序顺序为4——>2——>5——>1——>6——>3——>7

后序遍历

遍历规则

1. 先遍历左节点
2. 再遍历由节点
3. 最后遍历根节点

后序遍历的图解流程（左——>右——>中）

二叉树如图所示
先遍历左子树
左子树的后序顺序为4——>5——>2（左——>右——>中）
再遍历右子树
右子树的后序顺序为6——>7——>3（左——>右——>中）
最遍历根节点1
最后可得出后序顺序为4——>5——>2——>6——>7——>3——>1

前中后序遍历的转换

已知前序和中序——————可得唯一二叉树

• 首先根据前序（中——>左——>右）确定根节点即前序的第一个节点。
• 根据中序（左——>中——>右）可将中序分割成左子树和右子树
• 然后对左子树和右子树重复以上操作即可

eg:
先序顺序为1——>2——>4——>5——>3——>6——>7
中序顺序为4——>2——>5——>1——>6——>3——>7

• 根据前序（中——>左——>右）确定根节点即1
• 划分左子树中序顺序为4——>2——>5所以先序顺序为2——>4——>5
• 左子树根节点为2，左节点为4，右节点为5
• 再划分右子树中序顺序为6——>3——>7所以先序顺序为3——>6——>7
• 右子树根节点为3，左节点为6，右节点为7

已知前序和后序——————不可得唯一二叉树

已知中序和后序——————可得唯一二叉树

• 首先根据后序（左——>右——>中）确定根节点即后序的最后一个节点。
• 根据中序（左——>中——>右）可将中序分割成左子树和右子树
• 然后对左子树和右子树重复以上操作即可

eg:
后序顺序为4——>5——>2——>6——>7——>3——>1
中序顺序为4——>2——>5——>1——>6——>3——>7

• 根据后序（左——>右——>中）确定根节点即1
• 划分左子树中序顺序为4——>2——>5所以后序顺序为4——>5——>2
• 左子树根节点为2，左节点为4，右节点为5
• 再划分右子树中序顺序为6——>3——>7所以后序顺序为6——>7——>3
• 右子树根节点为3，左节点为6，右节点为7