问题描述
从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行中序遍历，然后将遍历结果打印输出。要求采用非递归方法实现。
解题思路
使用栈中间存储树的结点
程序实现
#include#include #define FALSE 0#define TRUE 1typedef char Datatype;/*二叉树*/typedef struct Node { Datatype data; struct Node *LChild; struct Node *RChild;} BiTNode, *BiTree;/*链栈*/typedef struct Stack { struct Node *node; struct Stack *next;} Stack, *SeqStack;typedef struct { SeqStack top; int count;} LinkStack;/*栈操作*/int initStack(LinkStack *stack);int emptyStack(LinkStack *stack);int push(LinkStack *stack, BiTree tree);BiTree pop(LinkStack *stack);void createBiTree(BiTree *tree);void traverseTree(BiTree tree, LinkStack *stack);int main(int argc, char *argv[]) { BiTree tree; printf("按先序遍历序列建立二叉树:\n"); createBiTree(&tree); LinkStack stack; initStack(&stack); printf("使用栈后序输出二叉树:\n"); traverseTree(tree, &stack); return 0;}/** * 初始化一个空栈 */int initStack(LinkStack *stack) { stack->top = (SeqStack)malloc(sizeof(Stack)); if(!stack->top) { return FALSE; } stack->top = NULL; stack->count = 0; return TRUE;}/** * 判断栈是否为空 */int emptyStack(LinkStack *stack) { int result = 0; if (stack->count == 0) { result = 1; } return result;}/** * 入栈操作 */int push(LinkStack *stack, BiTree tree) { SeqStack s = (SeqStack)malloc(sizeof(Stack)); s->node = tree; s->next = stack->top; /* 把当前的栈顶元素赋值给新结点的直接后继，见图中① */ stack->top = s; /* 将新的结点s赋值给栈顶指针，见图中② */ stack->count++; return 1;}/** * 出栈操作 */BiTree pop(LinkStack *stack) { BiTree tree; SeqStack p; if (emptyStack(stack)) { return FALSE; } tree = stack->top->node; /*将栈顶结点赋值给p*/ p = stack->top; /*使得栈顶指针下移一位，指向后一结点*/ stack->top = stack->top->next; /* 释放结点p */ free(p); stack->count--; return tree;}void createBiTree(BiTree *tree) { char ch; ch = getchar(); if(ch == ' ') { *tree = NULL; } else { //生成一个新结点 *tree = (BiTree)malloc(sizeof(BiTNode)); (*tree)->data = ch; //生成左子树 createBiTree(&((*tree)->LChild)); //生成右子树 createBiTree(&((*tree)->RChild)); }}/**遍历树的结点*/void traverseTree(BiTree tree, LinkStack *stack) { if(tree == NULL) { return; } BiTree root = tree; while (root != NULL || !emptyStack(stack)) { if (root != NULL) { push(stack, root); root = root->LChild; } else { root = pop(stack); printf("%c ", root->data); root = root->RChild; } }}
运行结果
