二叉树遍历的基本概念
遍历（Traversal）是指沿着某条搜索路线依次对树中每个结点均做一次且仅做一次访问
从二叉树的递归定义可知二叉树是由三个基本单元组成根结点左子树和右子树因此若能依次遍历这三部分便是遍历了整个二叉树假如以LDR分别表示遍历左子树访问根结点和遍历右子树则可有DLRLDRLRDDRLRDLRLD六种遍历二叉树的方案若限定先左后右则只有前三种情况分别称之为前序遍历中序遍历和后序遍历
前序遍历
前序遍历（Preorder Traversal）亦称先序遍历定义为
若二叉树为空则空操作否则执行下列步骤
（）访问根结点
（）遍历左子树
（）遍历右子树
中序遍历
中序遍历（Inorder Traversal）定义为
若二叉树为空则空操作否则执行下列步骤
（）遍历左子树
（）访问根结点
（）遍历右子树
后序遍历
后序遍历（Postorder Traversal）定义为
若二叉树为空则空操作否则执行下列步骤
（）遍历左子树
（）遍历右子树
（）访问根结点
构造二叉链表
基于先序遍历构造二叉链表算法
依据前序遍历中序遍历或中序遍历后序遍历构造二叉树
