二叉树遍历实现 - C语言论坛

问题点数：0 回复次数：10

二叉树遍历实现

我写的遍历二叉树的程序，我输入数据的时候怎么一直让我输入啊
麻烦帮忙看看创建二叉树的函数，多谢
#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;
}

搜索更多相关主题的帖子: 二叉树　遍历　

第 2 楼

得分: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);
}
}

倚天照海花无数，流水高山心自知。

第 3 楼

得分:0

回复：（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;
}
}

上善若水，水善利万物而不争，处众人之所恶

第 4 楼

得分:0

我输入AB##C##
怎么输出ABB啊

上善若水，水善利万物而不争，处众人之所恶

第 5 楼

得分:0

你看清楚我的回帖再发你这个帖子!

倚天照海花无数，流水高山心自知。

第 6 楼

得分:0

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

上善若水，水善利万物而不争，处众人之所恶

第 7 楼

得分:0

你老是遍历左子树,现在看懂没.

倚天照海花无数，流水高山心自知。

第 8 楼

得分:0

不好意思
万分感谢
搞定了

上善若水，水善利万物而不争，处众人之所恶

第 9 楼

得分:0

程序代码：


/**
 * 按先序创建二叉树.
 * 依次输入二叉树的结点值(一个字符)
 * 空格表示空树
 */
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;
}

在这里推荐一本书 <The C Programming Language>

第 10 楼

得分:0

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

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

上善若水，水善利万物而不争，处众人之所恶