⼆叉树的⼏种遍历⽅式
⼆叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问⼆叉树中所有的结点，使得每个结点被访问依次且仅被访问⼀次。
四种遍历⽅式分别为：先序遍历、中序遍历、后序遍历、层序遍历。
先序遍历
先序遍历(Pre-order)，按照根左右的顺序沿⼀定路径经过路径上所有的结点。在⼆叉树中，先根后左再右。巧记：根左右。
先序遍历也叫做先根遍历、前序遍历，可记做根左右（⼆叉树⽗结点向下先左后右）。
⾸先访问根结点然后遍历左⼦树，最后遍历右⼦树。在遍历左、右⼦树时，仍然先访问根结点，然后遍历左⼦树，最后遍历右⼦树，如果⼆叉树为空则返回。
先序中序后序遍历二叉树中序遍历
中序遍历（LDR）是⼆叉树遍历的⼀种，也叫做中根遍历、中序周游。在⼆叉树中，中序遍历⾸先遍历左⼦树，然后访问根结点，最后遍历右⼦树。
中序遍历⾸先遍历左⼦树，然后访问根结点，最后遍历右⼦树。若⼆叉树为空则结束返回，否则：
（1）中序遍历左⼦树
（2）访问根结点
（3）中序遍历右⼦树
后序遍历
后序遍历（LRD）是⼆叉树遍历的⼀种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和⾮递归算法两种。在⼆叉树中，先左后右再根，即⾸先遍历左⼦树，然后遍历右⼦树，最后访问根结点。
后序遍历⾸先遍历左⼦树，然后遍历右⼦树，最后访问根结点，在遍历左、右⼦树时，仍然先遍历左⼦树，然后遍历右⼦树，最后遍历根结点。即：
否则：
（1）后序遍历左⼦树
（2）后序遍历右⼦树
（3）访问根结点
后序遍历结果：DEBFCA
已知前序遍历和中序遍历，就能确定后序遍历。
层序遍历
层序遍历所要解决的问题很好理解，就是按⼆叉树从上到下，从左到右依次打印每个节点中存储的数据。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。