资源描述：
《遍历序列建树(推荐给大家).docx》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、二叉树遍历及C语言实现分类： C++语言2009-03-2616:29 9441人阅读 评论(6) 收藏 举报二叉树遍历及C语言实现已知中序和前序序列，或者已知中序和后序序列，都能够构造一棵二叉树。在本例中，本人用C语言写程序解答了下面两个算法题：（1）给出一棵二叉树的中序与后序遍历序列，求出它的先序遍历序列。（2）给出一棵二叉树的中序与先序遍历序列，求出它的后序遍历序列。知识点扼要回顾：所谓二叉树的遍历，是指按一定的顺序对二叉树中的每个结点均访问一次，且仅访问一。按照根结点访问位置的不同，通常把二
2、叉树的遍历分为六种：TLR（根左右）,TRL（根右左）,LTR（左根右）RTL（右根左）,LRT（左右根）,RLT（右左根）其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为前序遍历、中序遍历和后序遍历。前序遍历的规律是：输出根结点，输出左子树，输出右子树； 中序遍历的规律是：输出左子树，输出根结点，输出右子树； 后序遍历的规律是：输出左子树，输出右子树，输出根结
3、点；不多说了，看代码吧：）1.#include 2.#include 3. 4.using namespace std; 5. 6.//存储节点数据，为简便起见，这里选用字符 7.typedef char DATA_TYPE; 8. 9.typedef struct tagBINARY_TREE_NODE BINARY_TREE_NODE, *LPBINARY_TREE_NODE; 1. 2.struct tagBINARY_TREE
4、_NODE 3.{ 4. DATA_TYPE data; //节点数据 5. LPBINARY_TREE_NODE pLeftChild; //左孩子指针 6. LPBINARY_TREE_NODE pRightChild; //右孩子指针 7.}; 8. 9.// 10.//函数名称：TreeFromMidPost 11.//函数功能：给出一棵二叉树的中序与后序序列，构造这棵二叉树
5、。 12.//输入参数：LPBINARY_TREE_NODE & lpNode：二叉树的结点 13.// string mid：存储了二叉树的中序序列的字符串 14.// string post：存储了二叉树的后序序列的字符串 15.// int lm, int rm：二叉树的中序序列在数组mid中的左右边界 16.// int lp, int rp：二叉树的后序序列在数组post中的左右边界 17.//
6、 18.void TreeFromMidPost(LPBINARY_TREE_NODE & lpNode, string mid, string post, int lm, int rm, int lp, int rp) 19.{ 20. //构造二叉树结点 21. lpNode = new BINARY_TREE_NODE; 22. lpNode->data = post[rp]; 23. lpNode->pLeftChild = NULL; 24. lp
7、Node->pRightChild = NULL; 25. 26. int pos = lm; 27. 28. while (mid[pos] != post[rp]) 29. { 30. pos++; 31. } 32. int iLeftChildLen = pos - lm; 33. 34. if (pos > lm)//有左孩子，递归构造左子树 35. { 36. TreeFromMidPost(l
8、pNode->pLeftChild, mid, post, lm, pos - 1, lp, lp + iLeftChildLen - 1); 37. } 38. 39. if (pos < rm)//有右孩子，递归构造右子树 40. { 41. TreeFromMidPost(lpNode->pRightChild, mid, post, pos + 1, rm, lp + iLeftChildLen, rp - 1);
