数据结构二叉树遍历例题 数据结构之二叉树的遍历

数据结构之二叉树的遍历  

二叉树遍历的基本概念 　

　　遍历（Traversal） 是指沿着某条搜索路线 依次对树中每个结点均做一次且仅做一次访问 　　从二叉树的递归定义可知 二叉树是由三个基本单元组成 根结点 左子树和右子树 因此 若能依次遍历这三部分 便是遍历了整个二叉树 假如以L D R分别表示遍历左子树 访问根结点和遍历右子树 则可有DLR LDR LRD DRL RDL RLD六种遍历二叉树的方案 若限定先左后右 则只有前三种情况 分别称之为前序遍历 中序遍历和后序遍历  前序遍历

　　前序遍历（Preorder Traversal）亦称先序遍历 定义为 　　若二叉树为空 则空操作 否则 执行下列步骤 　　（ ）访问根结点 　　（ ）遍历左子树 　　（ ）遍历右子树

中序遍历

　　中序遍历（Inorder Traversal）定义为 　　若二叉树为空 则空操作 否则 执行下列步骤 　　（ ）遍历左子树 　　（ ）访问根结点 　　（ ）遍历右子树

后序遍历

　　后序遍历（Postorder Traversal）定义为 　　若二叉树为空 则空操作 否则 执行下列步骤 　　（ ）遍历左子树 　　（ ）遍历右子树 　　（ ）访问根结点

构造二叉链表