二叉树遍历二叉树遍历(Binary Tree Traversal)(Binary Tree Traversal)所谓树的遍历，就是按某种次序访问树中的结点，要求每所谓树的遍历，就是按某种次序访问树中的结点，要求每 个结点访问一次且仅访问一次。个结点访问一次且仅访问一次。设设访问根结点访问根结点记作记作 V V遍历根的左子树遍历根的左子树记作记作 L L遍历根的右子树遍历根的右子树记作记作 R R则可能的遍历次序有则可能的遍历次序有前序前序 VLR VLR 镜像镜像 VRLVRL中序中序 LVR LVR 镜像镜像 RVLRVL后序后序 LRV LRV 镜像镜像 RLVRLV 中序遍历二叉树算法的框架是：中序遍历二叉树算法的框架是：vv若二叉树为空，则空操作；若二叉树为空，则空操作；vv否则否则中序遍历左子树中序遍历左子树 (L)(L)；访问根结点访问根结点 (V)(V)；中序遍历右子树中序遍历右子树 (R)(R)。遍历结果遍历结果a a + + b b * * c c - - d d - - e e / / f f中序遍历中序遍历 ( (InorderInorder Traversal) Traversal)表达式语法树表达式语法树二叉树递归的中序遍历算法二叉树递归的中序遍历算法emplate void BinaryTree :InOrder ( ) InOrder ( root ); template void BinaryTree : InOrder ( BinTreeNode *current ) if ( current != NULL ) InOrder ( currentleftChild );cout void BinaryTree :PreOrder ( ) PreOrder ( root ); template void BinaryTree:PreOrder ( BinTreeNode *current ) if ( current != NULL ) cout void BinaryTree :PostOrder ( ) PostOrder ( root ); template void BinaryTree: PostOrder ( BinTreeNode *current ) if ( current != NULL ) PostOrder ( currentleftChild );PostOrder ( currentrightChild );cout currentdata;