返回顶部

收藏

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

相关聚客文章
  1. 博主 发表 2012-10-09 16:00:00 简单 Python C 扩展的编写及其对 Python 递归性能的提高
  2. yalewoo 发表 2017-04-20 15:08:52 【OJ】二叉搜索树转换为有序双向链表
  3. Arthur 发表 2014-06-16 13:11:00 二叉树非递归后序遍历
  4. 博主 发表 2012-11-30 03:08:17 C语言栈和函数递归
  5. One Coder 发表 2013-02-28 14:26:17 数组全排列递归算法 C语言实现
  6. Yysfire 发表 2014-12-20 20:18:00 二叉树的遍历序列转换算法及其复杂度分析
  7. Sana Mithani 发表 2013-07-10 22:35:00 C++ REST SDK 1.1.0 is now available
  8. 博主 发表 2013-08-18 14:51:59 快速实现Python C 拓展 - ctypesgen.py
  9. master 发表 2013-12-25 00:41:59 C/C++内存分配知识
  10. 博主 发表 2014-01-23 07:30:00 Objective-C中的Literals
  11. haipo 发表 2013-10-03 15:40:04 C 语言中的变长数组
  12. 孙鹤 发表 2013-05-14 10:25:28 C 语言泛型链表实现

发表评论