由二叉树的前序和中序如何得到二叉树的后序呢？
专注于为中小企业提供
成都做网站、成都网站制作服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业
阿克陶免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了成百上千家企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。
首先得明白什么是前序、中序、后序。
二叉树前序：遍历顺序为，根节点、左子树、右子树；中序：遍历顺序为，左子树、根节点、右子树；后序：遍历顺序为，左子树、右子树、根节点
可以发现，二叉树前序中的第一个节点为树的根节点root，然后找出root在中序里面的位置，就可以把前序和中序分别划分为左、右子树两个部分，然后递归调用即可。
#include
using namespace std;
template
struct BinaryTreeNode
{
T _data;
BinaryTreeNode* _left;
BinaryTreeNode* _right;
BinaryTreeNode(const T& x)
:_data(x)
, _left(NULL)
, _right(NULL)
{}
};
template
class BinaryTree
{
protected:
BinaryTreeNode* _root;
protected:
void _PreOrder(BinaryTreeNode* root)
{
if (root != NULL)
{
cout << root->_data << " ";
_PreOrder(root->_left);
_PreOrder(root->_right);
}
return;
}
BinaryTreeNode* _CreateBinary(char* preOrder, char* inOrder, int length)
{
BinaryTreeNode* root = NULL;
if (length == 0)
return NULL;
int tmp = *preOrder;
int index = 0;
while (index < length&&inOrder[index] != tmp)
index++;
if (index < length)
{
root = new BinaryTreeNode(tmp-'0');
root->_left = _CreateBinary(preOrder + 1, inOrder,index);
root->_right = _CreateBinary(preOrder + index + 1, inOrder + index + 1, length - index - 1);
}
return root;
}
void _Clear(BinaryTreeNode* root)
{
if (root)
{
_Clear(root->_left);
_Clear(root->_right);
delete root;
}
}
public:
BinaryTree()
:_root(NULL)
{}
~BinaryTree()
{
_Clear(_root);
_root = NULL;
}
void PreOrder()
{
_PreOrder(_root);
cout << endl;
}
void CreateBinaryTree(char* preOrder, char* inOrder)
{
int length = strlen(preOrder);
_root = _CreateBinary(preOrder, inOrder,length);
}
};
void Test1()
{
char* preOrder = "12473568";
char* inOrder = "47215386";
BinaryTree bt;
bt.CreateBinaryTree(preOrder, inOrder);
bt.PreOrder();
}
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
新闻名称：由二叉树的前序和中序如何得到二叉树的后序呢？-创新互联
文章链接：
http://bjjierui.cn/article/dijgch.html
