在调试过程中进出去while语句,程序运行没有完成,C新手,求教大佬!!!
程序在下
#include <stdio.h>
#include <stdlib.h>
typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
/------堆栈的定义-------/
typedef Position SElementType;
typedef struct SNode *PtrToSNode;
struct SNode {
SElementType Data;
PtrToSNode Next;
};
typedef PtrToSNode Stack;
Stack CreateStack();
int IsEmpty( Stack S ); /判断堆栈空不空/
void Push( Stack S, SElementType X );/入栈/
SElementType Pop( Stack S ); /* 删除并仅返回S的栈顶元素 /
SElementType Peek( Stack S ); / 仅返回S的栈顶元素 /
/----堆栈的定义结束-----*/
Stack CreateStack()
{
Stack S;
S=(Stack)malloc(sizeof(struct SNode));
S->Next =NULL;
return S;
}
BinTree CreateBinTree();
BinTree CreateBinTree() /将数据为空格当作树的每个分支的结束标志/
{ /将叶子节点的左节点和右节点指向NULL,如果/
BinTree BT; /输入的数据不是空格,则继续进行递归创建/
char ch;
scanf("%c",&ch);
if(ch==' '){
BT=NULL;
}
else{
BT=(BinTree)malloc(sizeof(struct TNode));
BT->Data =ch;
BT->Left =CreateBinTree();
BT->Right =CreateBinTree();
}
return BT;
}
int IsEmpty( Stack S )
{
return (S->Next ==NULL); /if(S->Next==NULL) return 1; else return 0;/
}
void Push( Stack S, SElementType X ) /* SElementType X 是struct TNode 类型的数据/
{
Stack TmpCell;
TmpCell=(Stack)malloc(sizeof(struct SNode));
TmpCell->Data =X;
TmpCell->Next =S->Next ;
S->Next =TmpCell;
}
SElementType Pop( Stack S )
{
Stack FristCell;
SElementType TopElem;
if(IsEmpty( S )){
printf("堆栈为空\n");
return NULL;
}
else{
FristCell=S->Next ;
S->Next =FristCell->Next;
TopElem=FristCell->Data ;
free(FristCell);
return TopElem;
}
}
SElementType Peek( Stack S )
{
SElementType TopElem;
TopElem = S->Next->Data ;
return TopElem;
}
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT )
{
BinTree T = BT;
Stack S = CreateStack( ); /*创建并初始化堆栈,命名为 S ,Stack表示 struct SNode * */
while( T || !IsEmpty( S )){ /*树不空,或堆栈不空*/
while(T);{ /* 出错 */ /*都空结束遍历操作*/
Push( S, T );
printf("%c",T->Data );
T = T->Left ;
}
if(!IsEmpty( S )){
T= Pop( S );
T = T->Right;
}
}
}
void InorderTraversal( BinTree BT ) /中序遍历/
{
BinTree T = BT;
Stack S = CreateStack( ); /*创建并初始化堆栈,命名为 S ,Stack表示 struct SNode * */
while( T || !IsEmpty( S )){ /树不空,或堆栈不空/
while(T);{ /*都空结束遍历操作*/
Push( S, T );
T = T->Left ;
}
if(!IsEmpty( S )){
T= Pop( S );
printf("%c",T->Data );
T = T->Right;
}
}
}
void PostorderTraversal( BinTree BT )
{
BinTree T = BT;
BinTree Temp=NULL; /保持上次pop的元素/
Stack S = CreateStack( ); /*创建并初始化堆栈,命名为 S ,Stack表示 struct SNode * */
while( T || !IsEmpty( S )){ /树不空,或堆栈不空/
while(T);{ /*都空结束遍历操作*/
Push( S, T );
T = T->Left ;
}
if(!IsEmpty( S )){
T= Pop( S );
if(T->Right ==NULL||T->Left ==Temp){ /*如果右儿子为空,或上次抛出的是右儿子,则可以输出*/
printf("%c",T->Data );
Temp=T;
T=NULL; /*整个字树遍历完,指针置为NULL*/
}
else{
Push( S, T ); /*右子树没有遍历完,不能出栈 */
T = T->Right;
}
}
}
free(S);
}
int main()
{ printf("请输入二叉树存储信息\n");
printf("请连续输入,空格表示树的每个分支的结束\n");
BinTree BT = CreateBinTree();
printf("Preorder:"); PreorderTraversal(BT); printf("\n");
printf("Inorder:"); InorderTraversal(BT); printf("\n");
printf("Postorder:"); PostorderTraversal(BT); printf("\n");
return 0;
}