T16-树(遍历与应用)

遍历与应用第八章：树

主讲：周翔二叉树的遍历遍历定义：就是按某种次序访问树中的结点，要求树中每个结点访问一次且仅访问一次。遍历用途：是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心遍历方式按访问结点的先后次序将结点排列起来，分别得到的结点列表遍历区别先序遍历前序列表最先访问根中序遍历中序列表中间访问根后序遍历后序列表最后访问根二叉树的遍历——先序遍历先序遍历：在遍历二叉树时先访问根结点，然后访问左子树，最后访问右子树。ABDFIL第一步：访问根结点，输出A；第二步：访问左子树；左子树是以B为根结点的二叉树；先遍历这棵左子树的根结点，输出B；第三步：访问B的左子树，发现没有左子树，则访问B的右子树，右子树是以F为根结点的二叉树，先遍历这棵树的根结点，则输出F；二叉树的遍历——先序遍历先序遍历：在遍历二叉树时先访问根结点，然后访问左子树，最后访问右子树。ABDFIL第四步：访问F的左子树，左子树是以L为根结点的二叉树，遍历这棵树的根结点，输出L；第五步：访问L的左子树，L没有左子树；则访问L的右子树，L没有右子树；以L为根结点的二叉树访问完毕，即F的左子树访问完毕；第六步：访问F的右子树，发现F没有右子树，则以F为根结点的二叉树访问完毕，即B的右子树访问完毕，那么以B为根结点的二叉树就访问完毕，即A的左子树访问完毕；二叉树的遍历——先序遍历先序遍历：在遍历二叉树时先访问根结点，然后访问左子树，最后访问右子树。ABDFIL第七步：访问A的右子树，右子树是以D为根结点的二叉树，先遍历根结点，则输出D；第八步：遍历D的左子树，左子树是以I为根结点的二叉树，先遍历根结点，则输出I；第九步：访问I的左子树，左子树不存在；访问I的右子树，右子树不存在；则以I为根结点的二叉树访问完毕，即D的左子树遍历完毕；第十步：访问D的右子树，D没有右子树；则以D为根结点的二叉树访问完毕，即A的右子树遍历完毕，整棵树也遍历完毕；二叉树的遍历——先序遍历先序遍历：在遍历二叉树时先访问根结点，然后访问左子树，最后访问右子树。ABDFIL先序遍历结果：A->B->F->L->D->I二叉树的遍历——中序遍历中序遍历：中序遍历就是先访问树的左子树，然后访问根结点，最后访问右子树。ABDFIL中序遍历结果：A有左子树先访问左子树B没有左子树输出BB

然后访问B的右子树二叉树的遍历——中序遍历中序遍历：中序遍历就是先访问树的左子树，然后访问根结点，最后访问右子树。ABDFIL中序遍历结果：BF有左子树访问其左子树L没有左子树输出LLL也没有右子树返回到L的根F二叉树的遍历——中序遍历中序遍历：中序遍历就是先访问树的左子树，然后访问根结点，最后访问右子树。ABDFIL中序遍历结果：BLF

输出(根)F

输出F后，A的整个左子树遍历完毕返回根结点A二叉树的遍历——中序遍历中序遍历：中序遍历就是先访问树的左子树，然后访问根结点，最后访问右子树。ABDFIL中序遍历结果：BLFA二叉树的遍历——中序遍历中序遍历：中序遍历就是先访问树的左子树，然后访问根结点，最后访问右子树。ABDFIL中序遍历结果：BLFD有左子树先访问左子树I无左子树输出IAII无左右子树返回(根)D二叉树的遍历——中序遍历中序遍历：中序遍历就是先访问树的左子树，然后访问根结点，最后访问右子树。ABDFIL中序遍历结果：BLFAI

输出DDD无右子树则A的右子树遍历完毕二叉树的遍历——后序遍历后序遍历：后序遍历就是先访问树的左子树，然后访问树的右子树，最后访问根结点。ABDFIL后序遍历结果：LFBIDA二叉树的遍历对下图中的二叉树进行前序、中序、后序遍历得到的列表分别为：ABDEFGHIJ先序列表:ABEFIJDGH中序列表:EBIFJAGDH后序列表:EIJFBGHDA二叉树的遍历对下图中的二叉树进行前序、中序、后序遍历得到的列表分别为：先序列表:ABDFGCEH中序列表:BFDGACEH后序列表:FGDBHECAABCEDHFG二叉树的应用最早提出遍历问题是对存储在计算机中的表达式求值。例如：(a+b×c)-d/e前缀：-+a×bc/de中缀：a+b×c-d/e后缀：abc×+de/--+/a×debc二叉树的应用——递归思想的应用遍历算法的分析：从递归的角度看，三种算法是完全相同的，或说这三种算法的访问路径是相同的，只是访问结点的时机不同从虚线的出发点到终点的路径上，每个结点经过3次。AFEDCBG第1次经过时访问＝先序遍历第2次经过时访问＝中序遍历第3次经过时访问＝后序遍历二叉树的应用——递归思想的应用输出叶结点：假设结点中存储的数据元素为整数，并要求按先序输出如果是空树，则叶子结点个数为0；否则，为左子树的叶子结点个数+右子树的叶子结点个数二叉树的应用——递归思想的应用求二叉树的叶子结点的个数算法思想如下：（1）二叉树的叶子结点个数是左子树叶子结点和右子树叶子结点个数之和；（2）左子树又可视为一棵独立的二叉树，它的叶子结点个数是其左子树和右子树叶子结点数之和；（3）右子树也可视为一棵独立的二叉树，它的叶子结点个数是其左子树和右子树叶子结点数之和；…….二叉树的应用——递归思想的应用求二叉树的高度在一棵二叉树中，根结点是树中的第一层，求其左子树与右子树的高度，比较左右子树的高度，取较大的值加上根结点的高度1就是整棵树的高度。二叉树的应用——递归思想的应用求二叉树的高度若树为空树，则高度为0若树非空，高度应为其左、右子树高度的最大值加1二叉树的应用——非递归遍历以中序遍历为例来讲解树的非递归遍历中序非递归遍历，依然是先访问左子树，然后访问根结点，最后访问右子树。在遍历过程中需要用栈来处理数据。接下来就用图解来讲解树的中序非递归遍历。二叉树的应用——非递归遍历（1）首先访问根结点A，A有左子树，则A结点入栈。二叉树的应用——非递归遍历（2）A结点入栈后，指针下移，访问A结点的左子树，其左子树是以B为根结点的二叉树。访问结点B，判断B是否有左子树。B没有左子树，输出B。二叉树的应用——非递归遍历（3）访问B结点后，判断B是否有右子树，有，使指针下移，指向结点F，访问F结点，判断F结点是否有左子树，有，则F结点入栈。二叉树的应用——非递归遍历（4）F结点入栈后，指针下移，遍历其左子树；其左子树是以L为根结点的二叉树，访问L结点，L没有左子树，则访问L，将其输出。二叉树的应用——非递归遍历（5）输出L结点后，要访问其右子树，L没有右子树，则表示L结点访问完毕；根据栈顶指针回退到F结点，访问F，将其输出。二叉树的应用——非递归遍历（6）访问完栈顶元素结点后，要访问其右子树，F没有右子树，则根据栈顶指针指示再次回退，结果回退到结点A，访问A结点，将其输出。二叉树的应用——非递归遍历（7）访问完栈顶元素结点A之后，访问其右子树，即遍历D结点，因为D结点有左子树，D结点入栈。二叉树的应用——非递归遍历（8）D结点入栈后，访问其左子树，左子树是以I为根结点的二叉树，而I没有左子树，则访问I结点，将其输出。二叉树的应用——非递归遍历（9）结点I也没有右子树，则根据栈顶指示，回退到结点D，访问D结点，将其输出。（10）访问D结点后，访问其右子树，D没有右子树，且此时栈已为空，表示树已经遍历完毕。那么遍历输出结果为“BLFAID”。二叉树的应用——非递归遍历利用栈的前序遍历的非递归算法abcdecdcc退栈访问a右进c左进b退栈访问b右进d左进空退栈访问d右进空左进空退栈访问c右进空左进e退栈访问e右进空左进空e结束ba根进a树的遍历遍历方式遍历区别先序遍历最先访问根中序遍历中间访问根后序遍历最后访问根层序遍历树的遍历对T进行前序遍历：先访问树根n，然后依次前序遍历T1，T2，…，Tk，即前序遍历T1，然后前序遍历T2，…，最后前序遍历Tk。对T进行中序遍历：先中序遍历T1，然后访问树根n，接着中序遍历T2，…，Tk。对T进行后序遍历：先依次对T1，T2，…，Tk进行后序遍历，最后访问树根n。nT1T2…Tk树的遍历对下图中的树进行前序遍历、中序遍历、后序遍历得到的列表分别为：ABCDEFGHIJ前序列表:ABEFIJCDGH中序列表:EBIFJACGDH后序列表:EIJFBCGHDA补充：层序遍历对树中结点按层序遍历是指先访问树根，然后从左到右地依次访问所有层数为1的结