设定二叉树采用二叉链表方式存储，利用栈的基本操作设计中序遍历非递归算法。
（1）编写二叉链表方式存储的二叉树建立函数；
（2）编写栈的基本操作函数；
（3）编写中序遍历二叉树的非递归函数，参考算法6.11c；
（4）要求程序通过一个主菜单进行控制，通过选择菜单项序号调用各功能函数。
#include
#include
#include
#define Stack_Size 30
//二叉树的二叉链表结点结构定义（链式存储结构）
typedef struct BiNode {
char data;
struct BiNode *lchild, *rchild;
} BiNode, *BiTree;
//栈的数据结构
//栈元素类型
typedef struct {
BiNode *stack[Stack_Size]; // 存储节点数组
int top; // 栈顶指针
} BStack, *Stack;
// 栈初始化
Stack InitStack();
// 判断栈是否为空
int StackEmpty(Stack S);
// 判断栈是否满
int StackFull(Stack S);
// 创建二叉树
void Create(BiTree *T);
// 进栈操作
void Push(Stack *S, BiNode *e);
// 出栈操作
BiNode* Pop(Stack *S);
// 取得栈顶元素
BiNode* GetTop(Stack S);
// 输出栈中元素的内容
void Visit(BiNode *root);
// 二叉树的中序遍历的非递归算法
void InTraverse(BiTree T);
// 菜单
int selectMenu();
Stack InitStack() {
}
int StackEmpty(Stack S) {
}
int StackFull(Stack S) {
}
void Create(BiTree *T) {
}
void Push(Stack *S, BiNode *e) {
}
BiNode* Pop(Stack *S) {
}
BiNode* GetTop(Stack S) {
}
// 输出栈中元素的内容
void Visit(BiNode *root) {
if (root->data != '#')
printf("%c ", root->data);
}
void InTraverse(BiTree T) {
}
// 菜单驱动程序
int selectMenu() {
int sn;
printf("-----------MENU---------n"); //显示菜单
printf("=========================================n");
printf("1.----二叉树的建立------n");
printf("2.----中序遍历非递归算法--------n");
printf("0.----退出程序----------n");
printf("=========================================n");
printf("请选择0--2:");
//菜单功能选择
for (;;) {
scanf("%d", &sn); //输入选项
getchar();
if (sn < 0 || sn > 2)
printf("n 输入选择错误，请重新选择 0--2：");
else
break;
}
return sn;
}
int main()
{
BiTree T;
// 无限循环,选择0 退出
for (;;) {
switch (selectMenu()) // 调用菜单函数，按返回值选择功能函数
{
case 1:
printf("n1.----二叉树的建立--------n");
Create(&T);
break;
case 2:
printf("n2.----中序遍历非递归算法--------n");
InTraverse(T);
printf("n");
break;
case 0:
printf("n0.----退出程序------------n");
return 0;
} // switch语句结束
} // for循环结束
} // main()函数结束
