1、编写二叉树基本操作算法(可如下所示函数，也可自定义，能实现即可)①算法5.2中序遍历二叉树T的非递归算法void InOrderTraverse1(BiTree T)②算法5.3先序遍历的顺序建立二叉链表void CreateBiTree(BITree &T) 2、编写主函数，调用上述算法实现二叉树的中序遍历操作。

1. 二叉树基本操作算法

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 算法5.2中序遍历二叉树T的非递归算法
void InOrderTraverse1(BiTree T) {
    stack<BiTree> s;
    BiTree p = T;
    while (p || !s.empty()) {
        if (p) {
            s.push(p);
            p = p->lchild;
        }
        else {
            p = s.top();
            s.pop();
            cout << p->data << " ";
            p = p->rchild;
        }
    }
}

// 算法5.3先序遍历的顺序建立二叉链表
void CreateBiTree(BiTree &T) {
    char ch;
    cin >> ch;
    if (ch == '#') T = NULL;
    else {
        T = new BiTNode;
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

2. 主函数调用中序遍历操作

int main() {
    BiTree T;
    cout << "请输入先序遍历序列，其中 '#' 表示空节点：" << endl;
    CreateBiTree(T);
    cout << "中序遍历结果为：" << endl;
    InOrderTraverse1(T);
    return 0;
}

示例输入：

AB#C##D##

示例输出：

中序遍历结果为：
A B C D