【数据结构】遍历二叉树.pdfVIP

遍历二叉树和线索二叉树遍历二叉树和线索二叉树 遍历二叉树遍历二叉树遍历二叉树遍历二叉树 遍历二叉树遍历二叉树 –– 按某种路径按某种路径((或策略或策略))访问二叉树中的每个结访问二叉树中的每个结 点，且对每个每个每个每个结点只访问一结点只访问一次次次次。这。这样样样样，二，二 点，且对 叉树中的结点按被访问顺序形成一个线性叉树中的结点按被访问顺序形成一个线性 序列。序列。 –– 用于信息查询或逐一处理，是二叉树大部用于信息查询或逐一处理，是二叉树大部 分其他操作的基础分其他操作的基础分其他操作的基础分其他操作的基础 遍历二叉树遍历二叉树遍历二叉树遍历二叉树 二叉树的三个基本单元二叉树的三个基本单元 –– 根结点、左子树、右子树根结点、左子树、右子树 D 符号约定符号约定 –– LL ：表示遍历左子树：表示遍历左子树 L R –– DD ：表示访问根结点：表示访问根结点 –– RR ：表示遍历右子树：表示遍历右子树 对二叉对二叉树的树的树的树的可可能遍能遍能遍能遍历顺历顺序序序序 – DLR, LDR, LRD, DRL, RDL, RLD六种 – 若若限定定先左先左后右，则则有有DLR, LDR, LRD三种种，分别 称之为先序遍历，中序遍历和后序遍历，形成先序序 列列，，中序序列和后序序列中序序列和后序序列 遍历遍历遍历遍历二二叉树的操作叉树的操作叉树的操作叉树的操作 先序遍历二叉树先序遍历二叉树先序遍历二叉树先序遍历二叉树((((PreOrderTraversePreOrderTraversePreOrderTraversePreOrderTraverse)))) –– 访问根结点访问根结点 –– 先序遍历左子树先序遍历左子树先序遍历左子树先序遍历左子树 –– 先序遍历右子树先序遍历右子树 中序遍历二叉树中序遍历二叉树中序遍历二叉树中序遍历二叉树((((InOrderTraverseInOrderTraverseInOrderTraverseInOrderTraverse)))) –– 中序遍历左子树中序遍历左子树 –– 访问根结点访问根结点访问根结点访问根结点 –– 中序遍历右子树中序遍历右子树 后序遍历二叉树后序遍历二叉树后序遍历二叉树后序遍历二叉树((((PostOrderTraversePostOrderTraversePostOrderTraversePostOrderTraverse)))) –– 后序遍历左子树后序遍历左子树 –– 后序遍历右子树后序遍历右子树后序遍历右子树后序遍历右子树 –– 访问根结点访问根结点 先序遍历先序遍历:: D L R AA A DD LL RR DD LL RR B C DD B C D L R 先序遍历序列：A B D C D 中序遍历中序遍历:: L