二叉树遍历实现_C语言

二叉树遍历实现

我写的遍历二叉树的程序，我输入数据的时候怎么一直让我输入啊
麻烦帮忙看看创建二叉树的函数，多谢
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
//定义结构体
typedef struct BiTNode
{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//创建二叉树
void CreateBiTree(BiTree &T)
{
char ch;
// ch=getchar();
scanf("%c",&ch);
if(ch=='#')T=NULL;
else
{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
{
exit(1);
}
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
//访问函数
void Visit(char e)
{
printf("%c",e);
}
//先序遍历
void PreOrderTraverse(BiTree T)
{
if(T)
{
Visit(T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->lchild);
}
}
//中序遍历
void InOrderTraverse(BiTree T)
{
if(T)
{
PreOrderTraverse(T->lchild);
Visit(T->data);
PreOrderTraverse(T->lchild);
}
}
//后序遍历
void PostOrderTraverse(BiTree T)
{
if(T)
{
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->lchild);
Visit(T->data);
}
}

int main()
{
BiTree T;
CreateBiTree(T);
PreOrderTraverse(T);
return 0;
}

搜索更多相关的解决方案: 二叉树 遍历

----------------解决方案--------------------------------------------------------

建立没有问题,但输入要像是这样的AB##C##,除非你的编译器不支持C++的引用
你有问题的是下面的,遍历全是L,以下雷同.
void PreOrderTraverse(BiTree T)
{
if(T)
{
Visit(T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->lchild);
}
}
//中序遍历
void InOrderTraverse(BiTree T)
{
if(T)
{
PreOrderTraverse(T->lchild);
Visit(T->data);
PreOrderTraverse(T->lchild);
}
}
//后序遍历
void PostOrderTraverse(BiTree T)
{
if(T)
{
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->lchild);
Visit(T->data);
}
}

----------------解决方案--------------------------------------------------------

回复：（nuciewth）建立没有问题,但输入要像是这样的A...

我改成这样可以吧
//先序遍历
int PreOrderTraverse(BiTree T)
{
if(T)
{
if(Visit(T->data))
{
if(PreOrderTraverse(T->lchild))
{
if(PreOrderTraverse(T->lchild))
{
return OK;
}
}
return FALSE;
}
return FALSE;
}
else
{
return OK;
}
}
//中序遍历
int InOrderTraverse(BiTree T)
{
if(T)
{
if(InOrderTraverse(T->lchild))
{
if(Visit(T->data))
{
if(InOrderTraverse(T->lchild))
{
return OK;
}
}
return FALSE;
}
return FALSE;
}
else
{
return OK;
}
}
//后序遍历
int PostOrderTraverse(BiTree T)
{
if(T)
{
if(PostOrderTraverse(T->lchild))
{
if(PostOrderTraverse(T->lchild))
{
if(Visit(T->data))
{
return OK;
}
}
return FALSE;
}
return FALSE;
}
else
{
return OK;
}
}
----------------解决方案--------------------------------------------------------
我输入AB##C##
怎么输出ABB啊
----------------解决方案--------------------------------------------------------
你看清楚我的回帖再发你这个帖子!
----------------解决方案--------------------------------------------------------

你说什么遍历全是L啊不懂啊

----------------解决方案--------------------------------------------------------

你老是遍历左子树,现在看懂没.
----------------解决方案--------------------------------------------------------
不好意思
万分感谢
搞定了
----------------解决方案--------------------------------------------------------

程序代码：

/**
* 按先序创建二叉树.
* 依次输入二叉树的结点值(一个字符)
* 空格表示空树
*/
Status CreateBiTree( BiThrTree &T)
{// 先序创建二叉树
char ch;
scanf(\"%c\",&ch);

if (ch == ' ')
{
T = NULL;
}
else
{
T = (BiThrNode *)malloc(sizeof(BiThrNode));
T->data = ch;
T->visited = 0;
if (!T)
{
return OVERFLOW;
}
CreateBiTree(T->pLChild);
CreateBiTree(T->pRChild);
}
return OK;
}

/**
* 先序遍历二叉树
* mod = true, 递归
* mod = false, 非递归
*/
Status PreOrderTraverse( BiThrTree T, Status(* visit)(TElemType e),bool mod = false)
{// 先序遍历
if (T)
{
if (mod)
{//递归
if (visit(T->data))
{
if (PreOrderTraverse(T->pLChild,visit,mod))
{
if (PreOrderTraverse(T->pRChild,visit,mod))
{
return OK;
}
}
}
}
else
{//非递归
SqStack S;
InitStack(S);
Push(S,T);
BiThrTree p;
while (!StackEmpty(S))
{
while (GetTop(S,p) && p)
{
if (!visit(p->data))
{
return ERROR;
}
Push(S,p->pLChild);
}//while

Pop(S,p);
if (!StackEmpty(S))
{
Pop(S,p);
Push(S,p->pRChild);
}
}//while
return OK;
}
return ERROR;
}
return OVERFLOW;
}//PreOrderTraverse

/**
* 中序遍历二叉树
* mod = true, 递归
* mod = false, 非递归
*/
Status InOrderTraverse( BiThrTree T, Status(* visit)(TElemType e),bool mod = false)
{// 中序遍历

if (T)
{
if (mod)
{
if (InOrderTraverse(T->pLChild,visit,mod))
{
if (visit(T->data))
{
if (InOrderTraverse(T->pRChild,visit,mod))
{
return OK;
}
}
}
}
else
{//非递归
SqStack S;
InitStack(S);
Push(S,T);
BiThrTree p;

while (!StackEmpty(S))
{
while(GetTop(S,p) && p)
{
Push(S,p->pLChild);
}
Pop(S,p);

if (!StackEmpty(S))
{
Pop(S,p);
if( !visit(p->data) )
{
return ERROR;
}
Push(S,p->pRChild);
}
}
return OK;
}
return ERROR;

}
return OVERFLOW;
}

/**
* 后序遍历二叉树
* mod = true, 递归
* mod = false, 非递归
*/
Status PostOrderTraverse( BiThrTree T, Status(* visit)(TElemType e),bool mod = false)
{// 后序遍历
if (T)
{
if (mod)
{//递归
if (PostOrderTraverse(T->pLChild,visit,mod))
{
if (PostOrderTraverse(T->pRChild,visit,mod))
{
if (visit(T->data))
{
return OK;
}
}
}
}
else
{//非递归
SqStack S;
InitStack(S);
Push(S,T);
BiThrTree p;

while(!StackEmpty(S))
{
while(GetTop(S,p) && p)
{
Push(S,p->pLChild);
if (p->pLChild && p->pLChild->visited == 1)
{//左子树被访问过

Pop(S,p);
Push(S,NULL);
}
}
Pop(S,p);
if (!StackEmpty(S))
{
GetTop(S,p);
{
if (!p->pRChild || p->pRChild->visited == 1)
{//右子树为空或被访问过

if (!visit(p->data))
{
return ERROR;
}

p->visited = 1;
Pop(S,p);
}
else
{
Push(S,p->pRChild);
}
}
}
}
return OK;
}
return ERROR;
}
return OVERFLOW;
}

/*
* 对二叉树进行层序遍历
*/
Status LeverOrderTraverse( BiThrTree T, Status(* visit)(TElemType e))
{// 层序遍历
LinkQueue Q;
InitQueue( Q );
if(T)
{
EnQueue(Q,T);
}
QElemType p;
while( !QueueEmpty(Q))
{
DeQueue(Q,p);
if( !(visit)(p->data))
{
return ERROR;
}
if(p->pLChild)
{
EnQueue(Q,p->pLChild); //左孩子入队列
}
if( p->pRChild )
{
EnQueue(Q,p->pRChild); // 右孩子入队列
}
}

return OK;
}

----------------解决方案--------------------------------------------------------

回复：（lw_China）[code]/** * 按先序创建二叉树. * ...

还有非递归的啊
真是太谢谢你了

----------------解决方案--------------------------------------------------------