求码神们援助 中序遍历非递归算法

设定二叉树采用二叉链表方式存储，利用栈的基本 *** 作设计中序遍历非递归算法。

（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();

/*TODO:栈初始化

 功能描述：初始化栈，如果分配内存成功，栈顶指针top设置为-1，

 否则，分配内存失败的情况，输出错误信息，printf("初始化栈失败!\n");

 返回值说明：返回初始化后的栈

*/

Stack InitStack() {

}

/*TODO:判断栈是否为空

 功能描述：判断栈是否为空，若为空，则返回1，不为空返回0

 参数说明：S-Stack类型的栈

 返回值说明：栈为空，则返回1，栈不为空返回0

 */

int StackEmpty(Stack S) {

}

/*TODO:判断栈是否满

 功能描述：判断栈是否为满，栈满，则返回1，栈不满返回0

 参数说明：S-Stack类型的栈

 返回值说明：栈满，则返回1，栈不满返回0

 */

int StackFull(Stack S) {

}

/*TODO:创建二叉树

 功能描述：编写建立二叉树函数。从键盘输入扩展的先序结点数据序列scanf("%c", // char类型的结点数据);，以二叉链表作为存储结构，

 输入#表示空结点，如果某个结点的左右孩子都是#则标识它是叶子结点

 比如输入：AC##D##

 对应的树结构为

    A

  C   D

 参数说明：*T-BiTree类型指针

 */

void Create(BiTree *T) {

}

/*TODO: 进栈 *** 作

 功能描述：进栈 *** 作，移动栈顶指针，压入元素

 进栈之前要判断栈是否满，若满，则不能进栈

 参数说明：*S-Stack类型的栈

 *e-BiNode类型二叉树的二叉链表

 */

void Push(Stack *S, BiNode *e) {

}

/*TODO: 出栈 *** 作

 功能描述：即d出栈顶元素，用一个节点保存d出的栈顶元素，作为返回值

 出栈之前，要判断栈是否为空，若为空，则无效 *** 作

 参数说明：*S-Stack类型的栈

 返回值说明：返回d出的栈顶元素

 */

BiNode* Pop(Stack *S) {

}

/*TODO:取得栈顶元素

 功能描述：判断栈是否为空，如果为空返回NULL，不为空返回栈顶元素

 参数说明：S-Stack类型的栈

 返回值说明：返回取得的栈顶元素

*/

BiNode* GetTop(Stack S) {

}

// 输出栈中元素的内容

void Visit(BiNode *root) {

    if (root->data != '#')

        printf("%c ", root->data);

}

/*TODO:二叉树的中序遍历的非递归算法

 功能描述：利用栈非递归完成二叉树的中序遍历 *** 作，调用方法Visit(BiNode *root)输出中序遍历的结点信息。

 参数说明：T-BiTree类型的二叉链表

*/

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()函数结束