5、3_1_二叉树的先中后序遍历_20200905124535.pdf

《5、3_1_二叉树的先中后序遍历_20200905124535.pdf》由会员分享，可在线阅读，更多相关《5、3_1_二叉树的先中后序遍历_20200905124535.pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2020/6/23王道考研/1本节内容二叉树先/中/后序遍历王道考研/CSKAOYAN.COM1王道考研/CSKAOYAN.COM知识总览知识总览22020/6/23王道考研/2王道考研/CSKAOYAN.COM什么是遍历什么是遍历遍历：按照某种次序把所有结点都访问一遍a1a2a3a4a5124365先/中/后序遍历：基于树的递归特性确定的次序规则根左子树右子树层次遍历：基于树的层次特性确定的次序规则线性结构第1层第2层第3层3王道考研/CSKAOYAN.COM二叉树的遍历二叉树的遍历根左子树右子树先序遍历：根左右（NLR）中序遍历：左根右（LNR）后序遍历：左右根（LRN）二叉树的递归特性：

2、要么是个空二叉树要么就是由“根节点+左子树+右子树”组成的二叉树空二叉树非空二叉树根左子树右子树42020/6/23王道考研/3王道考研/CSKAOYAN.COM二叉树的遍历二叉树的遍历先序遍历：根左右（NLR）中序遍历：左根右（LNR）后序遍历：左右根（LRN）ABC先序遍历：ABC中序遍历：BAC后序遍历：BCAABCDEFG先序遍历：A BCDEGFABCDEFGA后序遍历：中序遍历：BD ECFG先序遍历：AB中序遍历：BA后序遍历：BAAB右子树为空树A左子树为空树C先序遍历：AC中序遍历：AC后序遍历：CA5王道考研/CSKAOYAN.COM二叉树的遍历（手算练习）二叉树的遍历（手

3、算练习）ABCDEFGAGCDBFAEG DCFAGFBEDCEB根左右根(根左右) (根 左)根(根 (根 右)右) (根 左)左根右(左根 右)根(左根)(根右)根 右)根(左根)左右根(左右根) (左 根)根(右 根)右根) (左 根)根先序遍历：中序遍历：后序遍历：ABCAFBEDCACBACDBFEACBAEDCFB分支结点逐层展开法62020/6/23王道考研/4王道考研/CSKAOYAN.COM-+a/e*fb-cda + b * ( c d ) e / f算数表达式的“分析树”先序遍历 前缀表达式中序遍历 中缀表达式（需要加界限符）后序遍历 后缀表达式二叉树的遍历（手算练习）二

4、叉树的遍历（手算练习）7王道考研/CSKAOYAN.COM先序遍历（代码）先序遍历（代码）先序遍历（PreOrder）的操作过程如下：1. 若二叉树为空，则什么也不做；2. 若二叉树非空：访问根结点；先序遍历左子树；先序遍历右子树。ABDGECF82020/6/23王道考研/5中序遍历（InOrder）的操作过程如下：1. 若二叉树为空，则什么也不做；2. 若二叉树非空：中序遍历左子树；访问根结点；中序遍历右子树。王道考研/CSKAOYAN.COM中序遍历（代码）中序遍历（代码）ABDGECF9后序遍历（InOrder）的操作过程如下：1. 若二叉树为空，则什么也不做；2. 若二叉树非空：后序

5、遍历左子树；后序遍历右子树；访问根结点。王道考研/CSKAOYAN.COM后序遍历（代码）后序遍历（代码）ABDGECF102020/6/23王道考研/6王道考研/CSKAOYAN.COM先序遍历（代码）先序遍历（代码）ABDGCF123函数调用栈T=AT=BT=DPreOrder：PreOrder：PreOrder：#126#126#126T=NULLPreOrder：EEEE11王道考研/CSKAOYAN.COM先序遍历（代码）先序遍历（代码）ABDGECF1234函数调用栈T=AT=BT=DPreOrder：PreOrder：PreOrder：#126#126#127T=GPreOrde

6、r：#126T=NULLPreOrder：122020/6/23王道考研/7王道考研/CSKAOYAN.COM先序遍历（代码）先序遍历（代码）ABDGECF1234函数调用栈T=AT=BT=DPreOrder：PreOrder：PreOrder：#126#126#127T=GPreOrder：#127T=NULLPreOrder：13王道考研/CSKAOYAN.COM先序遍历（代码）先序遍历（代码）ABDGECF12345函数调用栈T=AT=BPreOrder：PreOrder：#126#127T=EPreOrder：142020/6/23王道考研/8王道考研/CSKAOYAN.COM先序遍历

7、（代码）先序遍历（代码）ABDGECF1234567函数调用栈T=APreOrder：#127T=CPreOrder：#126T=FPreOrder：15王道考研/CSKAOYAN.COM先序遍历（代码）先序遍历（代码）ABDGECF1234567函数调用栈T=APreOrder：#127T=CPreOrder：#127T=NULLPreOrder：空间复杂度：O(h)162020/6/23王道考研/9王道考研/CSKAOYAN.COM求先序遍历序列求先序遍历序列先序遍历（PreOrder）的操作过程如下：1. 若二叉树为空，则什么也不做；2. 若二叉树非空：访问根结点；先序遍历左子树；先序遍

8、历右子树。ABDGECF1234567脑补空结点，从根节点出发，画一条路：如果左边还有没走的路，优先往左边走走到路的尽头（空结点）就往回走如果左边没路了，就往右边走如果左、右都没路了，则往上面走先序遍历第一次路过时访问结点每个结点都会被路过3次图示说明：第一次路过第二次路过第三次路过17王道考研/CSKAOYAN.COM求中序遍历序列求中序遍历序列中序遍历（InOrder）的操作过程如下：1. 若二叉树为空，则什么也不做；2. 若二叉树非空：中序遍历左子树；访问根结点；中序遍历右子树。ABDGECF5312476脑补空结点，从根节点出发，画一条路：如果左边还有没走的路，优先往左边走走到路的尽头

9、（空结点）就往回走如果左边没路了，就往右边走如果左、右都没路了，则往上面走中序遍历第二次路过时访问结点每个结点都会被路过3次图示说明：第一次路过第二次路过第三次路过182020/6/23王道考研/10王道考研/CSKAOYAN.COM求后序遍历序列求后序遍历序列后序遍历（InOrder）的操作过程如下：1. 若二叉树为空，则什么也不做；2. 若二叉树非空：后序遍历左子树；后序遍历右子树；访问根结点。ABDGECF7421365脑补空结点，从根节点出发，画一条路：如果左边还有没走的路，优先往左边走走到路的尽头（空结点）就往回走如果左边没路了，就往右边走如果左、右都没路了，则往上面走后序遍历第三次

10、路过时访问结点每个结点都会被路过3次图示说明：第一次路过第二次路过第三次路过从你的全世界路过法19王道考研/CSKAOYAN.COM-+a/e*fb-cda + b * ( c d ) e / f算数表达式的“分析树”先序遍历 前缀表达式中序遍历 中缀表达式（需要加界限符）后序遍历 后缀表达式二叉树的遍历（手算练习）二叉树的遍历（手算练习）202020/6/23王道考研/11王道考研/CSKAOYAN.COM例：求树的深度（应用）例：求树的深度（应用）-+a/e*fb-cd21王道考研/CSKAOYAN.COM知识回顾与重要考点知识回顾与重要考点空间复杂度：O(h)脑补空结点，从根节点出发，画一条路：如果左边还有没走的路，优先往左边走走到路的尽头（空结点）就往回走如果左边没路了，就往右边走如果左、右都没路了，则往上面走22