二叉树求解路径建立成功入栈成功但是最后无法打印路径
#include<stdio.h>
#include<string.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define STACK_EMPTY 0
#define STACK_NOT_EMPTY 1
#define FOUND 1
#define NOT_FOUND 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define MAXLEN 100
#define NLAYER 5
typedef int Status;
typedef char TElemType;
TElemType Nil = ' ';
typedef struct BiTNode {
TElemType data;
struct BiTNode* lchild;
struct BiTNode* rchild;
int is_visit;
}BiTNode, BiTree;// 二叉链表
/ 创建二叉树 /
typedef struct StackNode {
BiTree data;// 数据
struct StackNode next;// 下一个结点
}StackNode, * Stack;// 链栈
/* 创建二叉树结点 /
BiTree createBiTNode();
/ 创建二叉树 */
void createBiTree(BiTree );
/ 非递归后序遍历寻找路径 */
void PostOrderTraverse(BiTree T, Stack S);
BiTree createBiTNode()
{
BiTree newNode = (BiTree)malloc(sizeof(BiTNode));
if (newNode == NULL) {
printf("错误");
exit(0);
}
newNode->lchild = NULL;
newNode->rchild = NULL;
return newNode;
}
void createBiTree(BiTree T)
{ printf("输入结点：");
TElemType ch;
ch=getchar();
getchar();
if (ch == Nil) / 空 */
*T = NULL;
else
{
*T = (BiTree)malloc(sizeof(BiTNode));
if (!*T)
exit(OVERFLOW);
(T)->data = ch; / 生成根结点 */
(*T)->is_visit = 0;
createBiTree(&(T)->lchild); / 构造左子树 */
createBiTree(&(T)->rchild); / 构造右子树 */
}
}
// 创建栈结点
Stack createStackNode() {
Stack newNode = (Stack)malloc(sizeof(StackNode));
if (newNode == NULL) {
printf("错误");
exit(0);
}
newNode->next = NULL;
return newNode;
}
// 初始化栈，并返回头结点
Stack initStack() {
Stack stack = createStackNode();
BiTree newNode = (BiTree)malloc(sizeof(BiTNode));;
stack->data = newNode;
return stack;
}
// 栈头结点是否存在
int isStackExist(Stack S) {
if (S == NULL) return FALSE;
return TRUE;
}
// 栈是否为空
int isStackEmpty(Stack S) {
if (isStackExist(S) == FALSE) {
return STACK_EMPTY;
}
if (S->next == NULL) {
return STACK_EMPTY;
}
return STACK_NOT_EMPTY;
}
// 入栈，data是要入栈的结点的数据
BiTree push(Stack S, BiTree data) {
if (isStackExist(S) == TRUE) {
Stack node = createStackNode();
node->data = data;
node->next = S->next;
S->next = node;
}
return data;
}
// 出栈，返回栈顶结点的数据
BiTree pop(Stack S) {
BiTree ret;
if (isStackEmpty(S) == STACK_NOT_EMPTY) {
Stack deleted = S->next;
S->next = deleted->next;
ret = deleted->data;
free(deleted);
}
return ret;
}
// 查看栈顶元素
BiTree peek(Stack S) {
if (isStackEmpty(S) == STACK_NOT_EMPTY)
return S->next->data;
else
return NULL;
}
// 清空栈
void clearStack(Stack S) {
while (isStackEmpty(S) == STACK_NOT_EMPTY) {
pop(S);
}
free(S);
}
void PostOrderTraverse(BiTree T, Stack S){
TElemType c;
printf("请输入要查询的结点：");
scanf("%c", &c);
getchar();
printf("非递归后序遍历 栈的具体操作如下：\n");
push(S, T);
printf("push %c\n", T->data);
BiTree p = T;
p->is_visit=1;
int flag = 0;
while ((!isStackEmpty(S)||p)) {
if(p->data == c){
flag=1;
break;
}
if(p->lchild && !p->lchild->is_visit){
push(S, p->lchild);
printf("push %c\n", p->lchild->data);
p = p->lchild;
p->is_visit = 1;
}
else{
if(p->rchild && !p->rchild->is_visit){
push(S,p->rchild);
printf("push %c\n", p->rchild->data);
p = p->rchild;
p->is_visit=1;
}
else{
p = pop(S);
printf("pop %c\n", p->data);
p = peek(S);
}
}
}
if(!flag){
printf("未找到该结点\n");
}
else{
Stack output = initStack();
while(!isStackEmpty(S)){
p=pop(S);
push(output, p);
}
printf("从根结点到%c结点路径为", c);
int len=-1;
while(!isStackEmpty(output)){
p=pop(output);
printf("%c", p->data);
len++;
}
printf("\n路径长度为%d\n", len);
}
}
int main()
{
int c=0; BiTree tree = NULL;
printf("请输入二叉树\n");
createBiTree(&tree);
Stack stack = initStack();
PostOrderTraverse(tree, stack);
return 0;
}
