当前访客身份:游客 [ 登录 | 加入 OSCHINA ]

代码分享

当前位置:
代码分享 » C/C++  » 编程基础
@Modix

二叉树的建立及递归遍历

@Modix 发布于 2010年11月05日 11时, 13评/12910阅
分享到: 
收藏 +0
1
数据结构中二叉树的建立和递归遍历
标签: 二叉树 递归

代码片段(1) [全屏查看所有代码]

1. [代码]二叉树     跳至 [1] [全屏预览]

#include<stdio.h>
#include<malloc.h>
#include<iostream>

//定义节点 
typedef struct BiNode{
        char data;
        struct BiNode *lch;
        struct BiNode *rch;
}BiNode,*BiTree;

//先序拓展序列建立二叉树 
void Create(BiTree &T)
{
        T =(BiNode*) malloc (sizeof(BiNode));
        
        printf("Enter the data \n");
        scanf(" %c",&T->data);
        if(T->data=='#') T = NULL;
        if(T){
                printf("");
                Create(T->lch);
                Create(T->rch);
        }
}

//先序遍历 (递归)
void Preorder (BiTree T)
{                    
   if (T) {
      printf(" %c",T->data);             // 访问根结点
      
      Preorder(T->lch); // 遍历左子树
      Preorder(T->rch);// 遍历右子树
   }
}

//中序遍历 (递归)
void Inorder (BiTree T)
{
     if(T) {
       Inorder(T->lch);
       
       printf(" %c",T->data);
       
       Inorder(T->rch);    
       }
} 

//后序遍历 (递归)
void Postorder (BiTree T)
{
     if(T) {
       Postorder(T->lch);
       Postorder(T->rch);
       
       printf(" %c",T->data); 
     }
} 

int main()
{
    //建树 
    printf("The fuction Create() is called.\n");
    BiTree T;
    Create(T);
    
    //三种遍历递归算法 
    printf("\n");    
    printf("The fuction Preorder() is called.\n");
    Preorder(T);
    
    printf("\n");
    printf("The fuction Inorder() is called.\n");
    Inorder(T);
    
    printf("\n");
    printf("The fuction Postorder() is called.\n");
    Postorder(T);
    
    
    printf("\n");
    system("pause");
    
}


开源中国-程序员在线工具:Git代码托管 API文档大全(120+) JS在线编辑演示 二维码 更多»

发表评论 回到顶部 网友评论(13)

  • 1楼:ifsc01 发表于 2010-12-29 11:13 回复此评论
    用codeblock编译g++编译的,有问题,停留在创建树那,不能遍历,你是在什么环境里测试 的?
  • 2楼:@Modix 发表于 2011-01-02 14:08 回复此评论
    您好,我是在DEV C++里编译的。对了,可能是您建树没输入完成。
  • 3楼:IT小小鸟 发表于 2011-06-07 12:20 回复此评论

    引用来自“lidashuang”的评论

    用codeblock编译g++编译的,有问题,停留在创建树那,不能遍历,你是在什么环境里测试 的?
    那是你输入的先序序列不对吧,只有输入了正确的序列,才能结束迭代过程。
  • 4楼:timeout 发表于 2011-11-10 11:21 回复此评论
    新手,感谢楼主.刚开始我也以为是有问题呢,研究后才发现是我自己输入的有问题.提醒一下大家,这里的输入要严格按照正确的顺序才能结束.这里要用到二叉树的一个性质,就是说对于有n个节点的二叉树,就有n+1个空域,在这里即为如果你输入了n个元素,那么一定要有n+1个#才会结束迭代过程.
  • 5楼:@Modix 发表于 2012-03-27 22:19 回复此评论

    引用来自“timeout”的评论

    新手,感谢楼主.刚开始我也以为是有问题呢,研究后才发现是我自己输入的有问题.提醒一下大家,这里的输入要严格按照正确的顺序才能结束.这里要用到二叉树的一个性质,就是说对于有n个节点的二叉树,就有n+1个空域,在这里即为如果你输入了n个元素,那么一定要有n+1个#才会结束迭代过程.
    该读者指出了关键,值得鼓励。
  • 6楼:process 发表于 2012-04-25 16:54 回复此评论
    create最好在结束的时候free掉刚才申请的内存吧!
  • 7楼:@Modix 发表于 2012-05-18 17:32 回复此评论

    引用来自“LeungHenry”的评论

    create最好在结束的时候free掉刚才申请的内存吧!
    如果free掉的话,那这颗二叉树岂不是白白创建了,你说是不是?
  • 8楼:杨峰22号 发表于 2012-11-25 11:53 回复此评论
    中续和后续怎么是一样的。  测试用例是1234567########
  • 9楼:杨峰22号 发表于 2012-12-11 21:40 回复此评论
    是我自己建树的时候没有写好,这真的是好程序。
  • 10楼:zero1386 发表于 2013-03-12 16:04 回复此评论

    引用来自“@Modix”的评论

    引用来自“LeungHenry”的评论

    create最好在结束的时候free掉刚才申请的内存吧!
    如果free掉的话,那这颗二叉树岂不是白白创建了,你说是不是?
    还是有问题的,用create后,每次到树底,T=NULL,之前都没有free当前T,造成地址丢失,则每次调用create,都会冗余树枝末的内存。
  • 11楼:zero1386 发表于 2013-03-14 12:17 回复此评论
    void Create(BiTree &T)
    {
            T =(BiNode*) malloc (sizeof(BiNode));
                 
            printf("Enter the data \n");
            scanf(" %c",&T->data);
            if(T->data=='#')
           {
               free(T);        
               T = NULL;
           }
            if(T){
                    printf("");
                    Create(T->lch);
                    Create(T->rch);
            }
    }
  • 12楼:凡程子 发表于 2013-06-25 15:42 回复此评论
    你的创建二叉树程序什么时候停止创建。。
  • 13楼:法布雷加钊 发表于 2015-11-13 21:51 回复此评论

    引用来自“ech0o”的评论

    是我自己建树的时候没有写好,这真的是好程序。
    我也是这种情况,为什么呢
开源从代码分享开始 分享代码
@Modix的其它代码 全部(1)...