二叉树遍历
- 2022 年 3 月 25 日
- 笔记
目录
1.遍历二叉树算法
遍历二叉树(traversing binary tree)是指按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。访问的含义很广，可以是对结点做各种处理，包括输出结点的信息，对结点进行运算和修改等。遍历二叉树是二叉树最基本的操作，也是二叉树其他各种操作的基础，遍历的实质是对二叉树进行线性化的过程，即遍历的结果是将非线性结构的树中结点排成一个线性序列。由于二叉树的每个结点都可能有两棵子树，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。
回顾二叉树的递归定义可知，二叉树是由3个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。假如从L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。若限定先左后右，则只有前3种情况，分别称之为先(根)序遍历、中(根)序遍历和后(根)序遍历。基于二叉树的递归定义，可得下述遍历二叉树的递归算法定义。
简单的来说，就是二叉树前中后序的遍历。由于要考二级了，今天也复习到了二叉树，做到遍历题目，就浅谈一下自己的方法。
直接上题目会更直接！我们把根节点，左子树，右子树分别成为D，L，R。
1.1前序
参考图1.12，先序先访问根节点，左子树，右子树，显而易见，先序结果为：DLR。
图1.12
当我们会了最简单的二叉树遍历后，就可以尝试复杂一点的。
如图1.13我们先看以A为根节点，B为左子树，C为右子树的二叉树它们的先序为
A B C
在看以B为根节点，D为左子树，E为右子树的二叉树它们的先序为
B D E
最后看以C为根节点，F为左子树，G为右子树的二叉树它们的先序为
C F G
最终我们将它们组合在一起，得到先序结果：ABDECFG!
图1.13
1.2中序
参考图1.12，中序先访问左子树，根节点，右子树，显而易见，先序结果为：LDR。
看点复杂的，如图1.21
老样子先看A为根节点，BC为左右子树的二叉树，中序结果为：BAC，
再看B（后面都将缩写了，我太懒了！）中序结果为DB，
再看C，中序结果为EC，
再看E，中序结果为EF，
最终我们将它们组合起来DBAEFC。
图1.21
1.3后序
参考图1.12，后序先访问左右子树，根节点，显而易见，先序结果为：LRD。
上图！看1.31
都是上述一样的操作，说一下方法，结果看自己喽！
先看A 后序结果为BCA，
再看B，后序价格为DB，
再看C，后序结果为EC，
最后再看E，后序结果为FE
OK，最后看你组合，结果为******！！！！！
最后做个总结，我感觉这个方法最简单了，我脑子不行，不会绕，只能用这种了，有更好的，请立马私我！！！最后祝大家二级顺利过！
