2016年度精品遍序列建树.docx

?  HYPERLINK /loomman/article/details/4027082 二叉树遍历及C语言实现 分类：? HYPERLINK /loomman/article/category/447723 C++语言2009-03-26 16:29?9441人阅读? HYPERLINK /loomman/article/details/4027082 \l comments 评论(6)? HYPERLINK javascript:void(0); \o 收藏 收藏? HYPERLINK /loomman/article/details/4027082 \l report \o 举报 举报 二叉树遍历及C语言实现 已知中序和前序序列，或者已知中序和后序序列，都能够构造一棵二叉树。在本例中，本人用C语言写程序解答了下面两个算法题： （1）给出一棵二叉树的中序与后序遍历序列，求出它的先序遍历序列。 （2）给出一棵二叉树的中序与先序遍历序列，求出它的后序遍历序列。 知识点扼要回顾：所谓二叉树的遍历，是指按一定的顺序对二叉树中的每个结点均访问一次，且仅访问一。按照根结点访问位置的不同，通常把二叉树的遍历分为六种：TLR（根左右）, TRL（根右左）, LTR（左根右）RTL（右根左）, LRT（左右根）, RLT（右左根） 其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为前序遍历、中序遍历和后序遍历。 前序遍历的规律是：输出根结点，输出左子树，输出右子树；??中序遍历的规律是：输出左子树，输出根结点，输出右子树；?后序遍历的规律是：输出左子树，输出右子树，输出根结点； 不多说了，看代码吧：） #include?iostream?? #include?string?? ?? using?namespace?std;?? ?? //存储节点数据，为简便起见，这里选用字符?? typedef?char???DATA_TYPE;?? ?? typedef?struct?tagBINARY_TREE_NODE??BINARY_TREE_NODE,?*LPBINARY_TREE_NODE;?? ?? struct?tagBINARY_TREE_NODE?? {?? ??????DATA_TYPE?????????????data;???????????//节点数据?? ??????LPBINARY_TREE_NODE????pLeftChild;?????//左孩子指针?? ??????LPBINARY_TREE_NODE????pRightChild;????//右孩子指针?? };?? ?? //?? //函数??称：TreeFromMidPost?? //函数功能：给出一棵二叉树的中序与后序序列，构造这棵二叉树。??? //输入参数：LPBINARY_TREE_NODE??lpNode：二叉树的结点??? //??????????string?mid：存储了二叉树的中序序列的字符串??? //??????????string?post：存储了二叉树的后序序列的字符串??? //??????????int?lm,?int?rm：二叉树的中序序列在数组mid中的左右边界??? //??????????int?lp,?int?rp：二叉树的后序序列在数组post中的左右边界?? //?? void?TreeFromMidPost(LPBINARY_TREE_NODE??lpNode,?string?mid,?string?post,?int?lm,?int?rm,?int?lp,?int?rp)?? {?? ????//构造二叉树结点?? ????lpNode?=?new?BINARY_TREE_NODE;?? ????lpNode-data?=?post[rp];?? ????lpNode-pLeftChild?=?NULL;?? ????lpNode-pRightChild?=?NULL;?? ?? ????int?pos?=?lm;?? ?? ????while?(mid[pos]?!=?post[rp])?? ????{?? ????????pos++;?? ????}?? ????int?iLeftChildLen?=?pos?-?lm;?? ?? ????if?(pos??lm)//有左孩子，递归构造左子树?? ????{?? ????????TreeFromMidPost(lpNode-pLeftChild,?mid,?post,?lm,?pos?-?1