> 二叉树遍历及C语言实现二叉树遍历及C语言实现已知中序和前序序列，或者已知中序和后序序列，都能够构造
二叉树遍历及C语言实现二叉树遍历及C语言实现已知中序和前序序列，或者已知中序和后序序列，都能够构造
lijieandjenny & &
发布时间： & &
浏览：10 & &
回复：0 & &
悬赏：0.0希赛币
二叉树遍历及C语言实现
　　二叉树遍历及C语言实现
　　已知中序和前序序列，或者已知中序和后序序列，都能够构造一棵二叉树。在本例中，本人用C语言写程序解答了下面两个算法题：
　　（1）给出一棵二叉树的中序与后序遍历序列，求出它的先序遍历序列。
　　（2）给出一棵二叉树的中序与先序遍历序列，求出它的后序遍历序列。
　　知识点扼要回顾：所谓二叉树的遍历，是指按一定的顺序对二叉树中的每个结点均访问一次，且仅访问一。按照根结点访问位置的不同，通常把二叉树的遍历分为六种：TLR（根左右）, TRL（根右左）, LTR（左根右）RTL（右根左）, LRT（左右根）, RLT（右左根）
　　其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为前序遍历、中序遍历和后序遍历。
　　前序遍历的规律是：输出根结点，输出左子树，输出右子树；　中序遍历的规律是：输出左子树，输出根结点，输出右子树； 后序遍历的规律是：输出左子树，输出右子树，输出根结点；
　　不多说了，看代码吧：）
#include &iostream&　
#include &string&　
//存储节点数据，为简便起见，这里选用字符　
typedef char　 DATA_TYPE;　
typedef struct tagBINARY_TREE_NODE　BINARY_TREE_NODE, *LPBINARY_TREE_NODE;　
struct tagBINARY_TREE_NODE　
　　　DATA_TYPE　　　　　　　　　　　 //节点数据　
　　　LPBINARY_TREE_NODE　　pLeftC　　 //左孩子指针　
　　　LPBINARY_TREE_NODE　　pRightC　　//右孩子指针　
//函数名称：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 =　
　　while (mid[pos] != post[rp])　
　　　　pos++;　
　　int iLeftChildLen = pos -　
　　if (pos & lm)//有左孩子，递归构造左子树　
　　　　TreeFromMidPost(lpNode-&pLeftChild, mid, post, lm, pos - 1, lp, lp + iLeftChildLen - 1);　
　　if (pos & rm)//有右孩子，递归构造右子树　
　　　　TreeFromMidPost(lpNode-&pRightChild, mid, post, pos + 1, rm, lp + iLeftChildLen, rp - 1);　
//函数名称：TreeFromMidPre　
//函数功能：给出一棵二叉树的先序与中序序列，构造这棵二叉树。 　
//输入参数: BINARY_TREE_NODE & lpNode：二叉树的结点　
//　　　　　string mid：存储了二叉树的中序序列的字符串 　
//　　　　　string pre：存储了二叉树的先序序列的字符串 　
//　　　　　int lm, int rm：二叉树的中序序列在数组mid中的左右边界 　
//　　　　　int lp, int rp：二叉树的先序序列在数组pre中的左右边界　
void TreeFromMidPre(LPBINARY_TREE_NODE & lpNode, string mid, string pre, int lm, int rm, int lp, int rp)　
　　//构造二叉树结点　
　　lpNode = new BINARY_TREE_NODE;　
　　lpNode-&data = pre[lp];　
　　lpNode-&pLeftChild = NULL;　
　　lpNode-&pRightChild = NULL;　
　　int pos =　
　　while (mid[pos] != pre[lp])　
　　　　pos++;　
　　int iLeftChildLen = pos -　
　　if (pos & lm)//有左孩子，递归构造左子树　
　　　　TreeFromMidPre(lpNode-&pLeftChild, mid, pre, lm, pos - 1, lp + 1, lp + iLeftChildLen);　
　　if (pos & rm)//有右孩子，递归构造右子树　
　　　　TreeFromMidPre(lpNode-&pRightChild, mid, pre, pos + 1, rm, lp + iLeftChildLen + 1, rp);　
//先序遍历　
void PreOrder(LPBINARY_TREE_NODE p)　
　　　 if(p != NULL)　
　　　 {　
　　　　　　　cout $<$ p-&　　　　　//输出该结点　
　　　　　　　PreOrder(p-&pLeftChild);　//遍历左子树 　
　　　　　　　PreOrder(p-&pRightChild); //遍历右子树　
　　　 }　
//中序遍历　
void MidOrder(LPBINARY_TREE_NODE p)　
　　　 if(p != NULL)　
　　　 {　
　　　　　　　MidOrder(p-&pLeftChild);　 //遍历左子树 　
　　　　　　　cout $<$ p-&　　　　　 //输出该结点　
　　　　　　　MidOrder(p-&pRightChild);　//遍历右子树　
　　　 }　
//后序遍历　
void PostOrder(LPBINARY_TREE_NODE p)　
　　　 if(p != NULL)　
　　　 {　
　　　　　　　PostOrder(p-&pLeftChild);　//遍历左子树 　
　　　　　　　PostOrder(p-&pRightChild); //遍历右子树　
　　　　　　　cout $<$ p-&　　　　　 //输出该结点　
　　　 }　
//释放二叉树　
void Release(LPBINARY_TREE_NODE lpNode)　
　　if(lpNode != NULL)　
　　　　Release(lpNode-&pLeftChild);　
　　　　Release(lpNode-&pRightChild);　
　　　　delete lpN　
　　　　lpNode = NULL;　
int main(int argc, char* argv[])　
　　string　　　　　　　　　　　　　//存储先序序列　
　　string　　　　　　　　　　　　　//存储中序序列　
　　string　　　　　　　　　　　　 //存储后序序列　
　　LPBINARY_TREE_NODE　lpR　　　　 //二叉树根节点指针　
　　cout$<<$程序１已知二叉树的中序与后序序列，求先序序列"$<$　
　　cout$<<$请先输入中序序列，回车后输入后序序列："$<$　
　　cin $>$　
　　cin $>$　
　　TreeFromMidPost(lpRoot, mid, post, 0, mid.size()-1, 0, post.size()-1);　
　　cout$<<$先序遍历结果：";　
　　PreOrder(lpRoot);　
　　cout$<$　
　　cout$<<$中序遍历结果：";　
　　MidOrder(lpRoot);　
　　cout$<$　
　　cout$<<$后序遍历结果：";　
　　PostOrder(lpRoot);　
　　cout$<$　
　　Release(lpRoot);　
　　cout$<$　
　　cout$<<$程序２已知二叉树的中序与先序序列，求后序序列"$<$　
　　cout$<<$请先输入先序序列，回车后输入中序序列："$<$　
　　cin $>$　
　　cin $>$　
　　TreeFromMidPre(lpRoot, mid, pre, 0, mid.size()-1, 0, pre.size()-1);　
　　cout$<<$先序遍历结果：";　
　　PreOrder(lpRoot);　
　　cout$<$　
　　cout$<<$中序遍历结果：";　
　　MidOrder(lpRoot);　
　　cout$<$　
　　cout$<<$后序遍历结果：";　
　　PostOrder(lpRoot);　
　　cout$<$　
　　Release(lpRoot);　
　　cout$<$　
　　system("pause");　
　　return 0;　
　　（1）程序1的输入方式：已知二叉树的中序与后序序列，求先序序列，请先输入中序序列，回车后输入后序序列：例如输入：DGBAECHFGDBEHFCA输出：先序遍历结果：ABDGCEFH中序遍历结果：DGBAECHF后序遍历结果：GDBEHFCA
　　（2）程序2的输入方式：已知二叉树的先序与中序序列，求后序序列，请先输入先序序列，回车后输入中序序列：例如输入：abdefgcdebgfac输出：先序遍历结果：abdefgc中序遍历结果：debgfac后序遍历结果：edgfbca
　　最后请看该程序运行效果图：
　　这是程序1所确定的二叉树图：
　　这是程序2所确定的二叉树图：
　　by Loomman, QQ:, MSN:
QQ裙： ☆程序天堂☆ 请尊重作者原创，转载注明来自裂帛一剑博客，谢谢合作。
本问题标题：
本问题地址：
温馨提示：本问题已经关闭，不能解答。
暂无合适的专家
&&&&&&&&&&&&&&&
希赛网 版权所有 & &&