1、编写二叉树基本操作算法(可如下所示函数，也可自定义，能实现即可)①算法5.2中序遍历二叉树T的非递归算法void InOrderTraverse1(BiTree T)②算法5.3先序遍历的顺序建立二叉链表void CreateBiTree(BITree &T) 2、编写主函数，调用上述算法实现二叉树的中序遍历操作。 3、完成实验报告。 三、实验原理、方法和手段 1、根据实验内容编程，上机调试、 得出正确的运行程序。void InOrderTraverse1(BITree T) //算法5.2中序遍历二叉树T的非递归算法LinkStack S; BlTree p; BiTree q=new BiTNode; InitStack(S); p=T; while(plI!StackEmpty(S)) if(p) Push(S,p); //p非空根指针进栈，遍历左子树 p=p->lchild; else Pop(S,q); //p为空根指针退栈，访问根结点，遍历右 子树 cout<<q->data;p=q->rchild; } 1/ while

1、二叉树基本操作算法

// 定义二叉树结点
struct BiTNode {
    char data;
    BiTNode* lchild;
    BiTNode* rchild;
};

// 中序遍历二叉树T的非递归算法
void InOrderTraverse1(BiTNode* T) {
    LinkStack S;
    BiTNode *p, *q;
    InitStack(S);
    p = T;
    while (p || !StackEmpty(S)) {
        if (p) {
            Push(S, p); //p非空根指针进栈，遍历左子树
            p = p->lchild;
        } else {
            Pop(S, q); //p为空根指针退栈，访问根结点，遍历右子树
            cout << q->data;
            p = q->rchild;
        }
    }
}

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

2、主函数调用上述算法实现二叉树的中序遍历操作

int main() {
    BiTNode* T = nullptr;
    CreateBiTree(T); // 先序遍历建立二叉树
    InOrderTraverse1(T); // 中序遍历二叉树
    return 0;
}

3、实验报告

本次实验实现了二叉树的中序遍历操作，采用了非递归算法，主要思路是使用栈来辅助遍历。同时还实现了先序遍历建立二叉链表的操作。在实现过程中，需要注意对栈的初始化、压栈、弹栈等操作。