用c++设计一个程序，由给定的二叉树先序序列，建立其二叉链表存储结构，并求出二叉树的中序序列和后序序列。

以下是C++代码，建立二叉链表存储结构，并求出中序序列和后序序列。
#include<iostream>
#include<stack>
using namespace std;

// 二叉树结点的定义
struct TreeNode {
char data;
TreeNode *lchild, *rchild;
TreeNode(char d):data(d), lchild(NULL), rchild(NULL){};
};

// 根据先序序列建立二叉树
TreeNode* createTree(){
char data;
cin >> data;
if(data == '#') return NULL;
TreeNode* root = new TreeNode(data);
root->lchild = createTree();
root->rchild = createTree();
return root;
}

// 中序遍历二叉树
void inOrder(TreeNode* root){
if(!root) return;
inOrder(root->lchild);
cout << root->data << " ";
inOrder(root->rchild);
}

// 后序遍历二叉树
void postOrder(TreeNode* root){
if(!root) return;
postOrder(root->lchild);
postOrder(root->rchild);
cout << root->data << " ";
}

// 根据先序序列建立二叉链表，并返回根节点
TreeNode* createBinaryTree(string preOrder, int&amp; index){
if(index >= preOrder.size()) return NULL;
if(preOrder[index] == '#') {
index++;
return NULL;
}
TreeNode* root = new TreeNode(preOrder[index]);
index++;
root->lchild = createBinaryTree(preOrder, index);
root->rchild = createBinaryTree(preOrder, index);
return root;
}

// 非递归方式求中序序列
void inOrderTraversal(TreeNode* root){
stack<TreeNode*> s;
TreeNode* cur = root;
while(cur || !s.empty()){
if(cur) {
s.push(cur);
cur = cur->lchild;
}else {
cur = s.top();
s.pop();
cout << cur->data << " ";
cur = cur->rchild;
}
}
}

// 非递归方式求后序序列
void postOrderTraversal(TreeNode* root){
stack<TreeNode*> s1, s2;
s1.push(root);
while(!s1.empty()){
TreeNode* cur = s1.top();
s1.pop();
s2.push(cur);
if(cur->lchild) s1.push(cur->lchild);
if(cur->rchild) s1.push(cur->rchild);
}
while(!s2.empty()){
cout << s2.top()->data << " ";
s2.pop();
}
}

int main(){
// 根据先序序列建立二叉树
TreeNode* root = createTree();

// 中序遍历二叉树，输出中序序列
cout << "Inorder traversal: ";
inOrder(root);
cout << endl;

// 后序遍历二叉树，输出后序序列
cout << "Postorder traversal: ";
postOrder(root);
cout << endl;

// 根据先序序列建立二叉链表存储结构，并输出中序序列和后序序列
string preOrder;
cout << "Enter the preorder traversal: ";
cin >> preOrder;
int index = 0;
TreeNode* newRoot = createBinaryTree(preOrder, index);

cout << "Inorder traversal: ";
inOrderTraversal(newRoot);
cout << endl;

cout << "Postorder traversal: ";
postOrderTraversal(newRoot);
cout << endl;

return 0;
}
登录后复制
输入示例：
AB#D##C##
ABCD
登录后复制
输出示例：
Inorder traversal: A B D C
Postorder traversal: D B C A
Enter the preorder traversal: ABCD
Inorder traversal: A B C D
Postorder traversal: D C B A
登录后复制