返回顶部

收藏

C语言构造并递归遍历二叉树的代码

更多
#include<stdio.h>
#include<malloc.h>

#define FALSE 1
#define ERROR 0
#define OK 1
#define ON 0

typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;

typedef int Status;
BiTree T;

Status CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);
    if (ch==' ')
        *T = NULL;
    else
    {
        if (!((*T) = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
        (*T)->data = ch;
        CreateBiTree(&((*T)->lchild));   // 构造左子树
        CreateBiTree(&((*T)->rchild));   // 构造右子树
    }
    return OK;
} // CreateBiTree

int vi(char c)
{
    printf("%c ",c);
    return OK;
}

//先序遍历的递归
void PreOrder(BiTree T)
{
    if(T)
    {
        vi(T->data);      //访问结点
        PreOrder(T->lchild);       //遍历左子树
        PreOrder(T->rchild);       //遍历右子树
    }
}

//中序遍历的递归
void InOrder(BiTree T)
{
    // 采用二叉链表存储结构,Visit是对数据元素操作的应用函数。
    // 中序遍历二叉树T的递归算法,对每个数据元素调用函数Visit。
    if(T)
    {
    InOrder(T->lchild);
    vi(T->data);
    InOrder(T->rchild);
    }
} // InOrderTraverse

//后序遍历的递归
void PostOrder(BiTree T)
{
    // 采用二叉链表存储结构,Visit是对数据元素操作的应用函数。
    // 中序遍历二叉树T的递归算法,对每个数据元素调用函数Visit。
    if(T)
    {
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    vi(T->data);
    }
} // InOrderTraverse
int main()
{
    printf("先序输入二叉树(空格代表空节点):\n");
    CreateBiTree(&T);
    printf("先序输出二叉树:\n");
    PreOrder(T);
    printf("\n");
    printf("中序输出二叉树:\n");
    InOrder(T);
    printf("\n");
    printf("后序输出二叉树:\n");
    PostOrder(T);
    printf("\n");
    return 0;
}

标签:递归,二叉树,C语言

收藏

0人收藏

支持

0

反对

0

发表评论