听 --风 2022-05-21 00:04
浏览 22
已结题

C语言数据结构二叉树的非递归遍历

    在调试过程中进出去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;
}

  • 写回答

0条回答 默认 最新

    报告相同问题?

    问题事件

    • 系统已结题 5月29日
    • 创建了问题 5月21日

    悬赏问题

    • ¥15 python天天向上类似问题,但没有清零
    • ¥30 3天&7天&&15天&销量如何统计同一行
    • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
    • ¥15 C#调用python代码(python带有库)
    • ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
    • ¥15 活动选择题。最多可以参加几个项目?
    • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
    • ¥15 vs2019中数据导出问题
    • ¥20 云服务Linux系统TCP-MSS值修改?
    • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)