| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1019 人关注过本帖
标题:二叉树前、中、后线索化及遍历程序,没报错,但没结果,求解释!!!!
只看楼主 加入收藏
乌托邦之梦
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2011-8-31
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:5 
二叉树前、中、后线索化及遍历程序,没报错,但没结果,求解释!!!!
#include "stdio.h"
#include "stdlib.h"
#define NULL 0
typedef char TElemType;
typedef int  status;
typedef enum{Link,Thread}PointTag;
typedef struct BiThrNode{
    TElemType data;
    struct BiThrNode *lchild,*rchild;
    PointTag LTag,RTag;
}BiThrNode,*BiThrTree;
BiThrTree pre,p;
status CreateBiTree(BiThrTree *T)
{
    char ch;
  fflush(stdin);//加入清空缓冲
    ch=getchar();
    if(ch=='#')
        (*T)=NULL;
    else{
        (*T)=(BiThrTree)malloc(sizeof(BiThrNode));
        (*T)->data=ch;
        (*T)->LTag=(*T)->RTag=Link;
        
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
        
    }
    return 1;
}
/*void preThreading(BiThrTree p){

    if (p)
    {
        if (p->lchild==NULL)
        {
            p->LTag=Thread;
            p->lchild=pre;
        }
        if (p->rchild==NULL)
        {
            p->RTag=Thread;
            p->rchild=pre;
        }
       pre=p;
       preThreading(p->lchild);
       preThreading(p->rchild);
    }
}
void InThreading(BiThrTree p){
    if (p)
    {
        InThreading(p->lchild);
        if (p->lchild==NULL)
        {
            p->LTag=Thread;
            p->lchild=pre;   
        }
        if (pre->rchild==NULL)
        {
            pre->RTag=Thread;
            pre->rchild=p;
        }
        pre=p;
        InThreading(p->rchild);
    }
}
void postThreading(BiThrTree p){
    if (p)
    {
        postThreading(p->lchild);
        postThreading(p->rchild);
        if (p->lchild==NULL)
        {
            p->LTag=Thread;
            p->lchild=pre;
        }
if (p->rchild==NULL)
{
    p->RTag=Thread;
    p->rchild=pre;
}
pre=p;
    }
}
status PreorderThreading(BiThrTree *Thrt,BiThrTree T)
{
    (*Thrt)=(BiThrTree)malloc(sizeof(BiThrNode));
    (*Thrt)->LTag=Link;
    (*Thrt)->RTag=Thread;
    (*Thrt)->rchild=(*Thrt);
    if(T==NULL)
        (*Thrt)->lchild=(*Thrt);
    else{
        preThreading(T);
        (*Thrt)->lchild=T;
        pre=(*Thrt);
        pre->RTag=Thread;
        (*Thrt)->rchild=pre;
    }
    return 1;
}
status InorderThreading(BiThrTree *Thrt,BiThrTree T)
{
    (*Thrt)=(BiThrTree)malloc(sizeof(BiThrNode));
    (*Thrt)->LTag=Link;
    (*Thrt)->RTag=Thread;
    (*Thrt)->rchild=(*Thrt);
    if(T==NULL)
        (*Thrt)->lchild=(*Thrt);
    else{
        (*Thrt)->lchild=T;
        pre=(*Thrt);
        InThreading(T);
        pre->rchild=(*Thrt);
        pre->RTag=Thread;
        (*Thrt)->rchild=pre;
    }
    return 1;
}
status postorderThreading(BiThrTree *Thrt,BiThrTree T)
{
    (*Thrt)=(BiThrTree)malloc(sizeof(BiThrNode));
    (*Thrt)->LTag=Link;
    (*Thrt)->RTag=Thread;
    (*Thrt)->rchild=(*Thrt);
    if(T==NULL)
        (*Thrt)->lchild=(*Thrt);
    else{
        (*Thrt)->lchild=T;
        pre=(*Thrt);
   
        pre->rchild=(*Thrt);
        pre->RTag=Thread;
        InThreading(T);
        (*Thrt)->rchild=pre;
        
    }
    return 1;
}
status preorderTraverse(BiThrTree Thrt)
{
    BiThrTree p;
    p=Thrt->lchild;
    while (p!=Thrt)
    {
        printf("%2c\n",p->data);
        while(p->LTag==Link) p->lchild;
        printf("%2c\n",p->data);
        while (p->RTag==Thread&&p->rchild!=Thrt)
        {
            p=p->rchild;
            printf("%2C",p->data);
        }
        
        if(p->LTag==Link)p = p->lchild;
        else p=p->rchild;
    }
    return 1;
}


status InorderTraverse(BiThrTree Thrt)
{
    BiThrTree p;
    p=Thrt->lchild;
    while (p!=Thrt)
    {
        while(p->LTag==Link) p->lchild;
        printf("%2c\n",p->data);
        while (p->RTag==Thread&&p->rchild!=Thrt)
        {
            p=p->rchild;
            printf("%2C",p->data);
        }
        p=p->rchild;
    }
    return 1;
}
BiThrTree parent(BiThrTree thrt,BiThrTree   p)
{   
    BiThrTree   temp;  
    temp=thrt;  
    if(temp->lchild==p)   
        return temp;    //父节点是头结点   
    else    {           
        temp=temp->lchild;
        while( temp->lchild!=p && temp->rchild!=p )   
        {   
            if(Link==temp->RTag)   
                temp=temp->rchild;                    //如果节点有右节点,那么往右      
            else               
                temp=temp->lchild;    //如果节点没有右孩子,那么去左孩子,没有左孩子,去前驱,也是走往左      
        }      
            return temp;   
        }
    }
void postorderTraverse(BiThrTree thrt)
{   
    BiThrTree    p;
    BiThrTree   par;
    p=thrt->lchild;  
    while(1)   
    {
        while(Link==p->LTag)
            p=p->lchild;  
        if(Link==p->RTag)  
            p=p->rchild;      
        else            break;        //p指向第一个被访问的节点   
    }   
    while(p!=thrt)
    {   
        printf("%2C",p->data);     
        par=parent(thrt,p);    //parent是p的双亲:     
        if(thrt==par)        //1.若parent是thrt,即p是根节点,则无后继   
            p=thrt;        
        else if(p==par->rchild || Thread==par->RTag) //2.若p是双亲的右孩子,或者是独生左孩子,则后继为双亲  
            p=par;   
        else        {         
            while(par->RTag==Link)     //3.若p是有兄弟的左孩子,则后继为双亲的右子树上按照后续遍历访问的第一个节点。     
            {               
                par=par->rchild;               
            while(par->LTag==Link)   
            {            
                par=par->lchild;  
            }  
            }     
            p=par;      
        }
    }
}

void main()
{
    BiThrTree T=NULL,Thrt=NULL;
    printf("\nCreat a Thread Binary Tree\n");
    CreateBiTree(&T);
    InorderThreading(&Thrt,T);
    InorderTraverse(Thrt);
    PreorderThreading(&Thrt,T);
    preorderTraverse(Thrt);
    postorderThreading(&Thrt,T);
    postorderTraverse(Thrt);

}
   
   
   
搜索更多相关主题的帖子: include status 二叉树 
2011-11-01 22:24
jj369258
Rank: 4
等 级:业余侠客
帖 子:116
专家分:226
注 册:2010-12-2
收藏
得分:5 
下一节课我们也要学了!哈哈
2011-11-02 21:57
编程的乐趣
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:1
帖 子:229
专家分:1027
注 册:2011-4-4
收藏
得分:5 
.
2011-11-02 21:59
尐城
Rank: 2
来 自:广州
等 级:论坛游民
帖 子:10
专家分:15
注 册:2011-10-27
收藏
得分:5 
回复 楼主 乌托邦之梦
/*前序遍历*/
void preorder(BiThrTree *p)
{
    if(p!=NULL)
    {
        printf("  %c",p->data);
        preorder(p->lchild);
        preorder(p->rchild);
    }
}
/*中序遍历*/
void inorder(BiThrTree *p)
{
    if(p!=NULL)   
    {
        inorder(p->lchild);
        printf("  %c",p->data);
        inorder(p->rchild);
    }
}
/*后序遍历*/
void postorder(BiThrTree *p)
{
    if(p!=NULL)   
    {
        postorder(p->lchild);
        postorder(p->rchild);
        printf("  %c",p->data);
    }
}
2011-11-03 11:27
小鱼儿c
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:14
帖 子:852
专家分:1317
注 册:2011-4-1
收藏
得分:5 
程序代码:
我运行了一下。。
status CreateBiTree(BiThrTree *T)
{
    char ch;
  fflush(stdin);//加入清空缓冲
  puts("请输入字符");
    ch=getchar();
    printf("%c",ch);
    printf("%d",ch);
    if(ch=='#')
    {
        puts("进来了");
        /*return 0;*/
        (*T)=NULL;
    }
        /*(*T)=NULL;*/
    else{
        (*T)=(BiThrTree)malloc(sizeof(BiThrNode));
        (*T)->data=ch;
        (*T)->LTag=(*T)->RTag=Link;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);这2句构成了死循环了。。。你自己再自己改改。。。。感觉代码好奇怪的。。。。
    }
    return 1;
}

用心做一件事情就这么简单
2011-11-03 16:54
乌托邦之梦
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2011-8-31
收藏
得分:0 
//先序及后序实现线索二叉树的建立与遍历
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct BiThrNode{
    char data;
    int LTag,RTag;
    BiThrNode *lchild,*rchild;
}BiThrNode,*BiThrTree;
BiThrTree pre,p;

void CreateBiThrTree(BiThrTree &T)      //按前序递归生成线索化二叉树结点类型
{
    char ch;
    ch=getchar();
    if(ch=='#') T=NULL;
    else
    {
        T=(BiThrTree)malloc(sizeof(BiThrNode));
        T->data=ch;
        CreateBiThrTree(T->lchild);
        CreateBiThrTree(T->rchild);
    }
}

void PreThreading(BiThrTree T)      //对每个结点的具体前序线索化
{
    if(T)
    {
        if(!(T->lchild))               //前驱线索化
        {
            T->lchild=pre;
            T->LTag=1;
        }
        else T->LTag=0;
        if(!(pre->rchild))             //后继线索化
        {
            pre->rchild=T;
            pre->RTag=1;
        }
        else pre->RTag=0;
        pre=T;
        if(T -> LTag != 1)  PreThreading(T -> lchild);    //线索化左子树
        if(T -> RTag != 1)  PreThreading(T -> rchild);    //线索化右子树
    }
}
void PreOrderThreading(BiThrTree &Thrt,BiThrTree T)    //前序线索化二叉树
{
    Thrt=(BiThrTree)malloc(sizeof(BiThrNode));   //创建头结点
    Thrt->LTag=0;
    Thrt->RTag=1;
    Thrt->rchild=Thrt;
    if(!T) Thrt->lchild=Thrt;           //空二叉树
    else
    {
        Thrt->lchild=T;                     
        pre=Thrt;                       //令pre指向刚刚访问过的结点
        PreThreading(T);
        pre->rchild=Thrt;
        pre->RTag=1;
        Thrt->rchild=pre;
    }

}

void PreOrderTraverseThr(BiThrTree T){    //前序遍历线索二叉树  
    BiThrTree p;
    p=T->lchild;
    while(p != T)
    {
        while(1)              //访问根结点
        {                          
            printf("%c",p->data);
            if(p->LTag==0)
            {
                p=p->lchild;
            }
            else break;
        }
        while((p->RTag==1)&&(p->rchild!=T))  //根据线索访问后继
        {
            p= p->rchild;
            printf("%c",p->data);
        }
        if(p->LTag==0)    p=p->lchild;
        else p = p->rchild;
    }
    printf("\n");
}


void PostThreading(BiThrTree T)   //对每个结点的具体后序线索化
{
    if(T)
    {
        if(T -> LTag != 1)  PostThreading(T -> lchild);    //线索化左子树
        if(T -> RTag != 1)  PostThreading(T -> rchild);    //线索化右子树
        if(!(T->lchild))               //前驱线索化
        {
            T->lchild=pre;
            T->LTag=1;
        }
        else T->LTag=0;
        if(!(pre->rchild))             //后继线索化
        {
            pre->rchild=T;
            pre->RTag=1;
        }
        else pre->RTag=0;
        pre=T;
   
    }
}

void PostOrderThreading(BiThrTree &Thrt,BiThrTree T)    //后序线索化二叉树
{
    Thrt=(BiThrTree)malloc(sizeof(BiThrNode));   //创建头结点
    Thrt->LTag=0;
    Thrt->RTag=1;
    Thrt->rchild=Thrt;
    if(!T) Thrt->lchild=Thrt;           //空二叉树
    else
    {
        Thrt->lchild=T;                     
        pre=Thrt;                       //令pre指向刚刚访问过的结点
        PostThreading(T);
        pre->rchild=Thrt;
        pre->RTag=1;
        Thrt->rchild=pre;
    }
}

BiThrTree parent(BiThrTree Thrt,BiThrTree T)
{
    BiThrTree  temp ;
    temp=Thrt;
    if(temp->lchild==p)
        return temp;    //父节点是头结点   
    else   
    {
        temp=temp->lchild;
        while( temp->lchild!=p && temp->rchild!=p )     
        {  
            if(0==temp->RTag)
                temp=temp->rchild;    //如果节点有右节点,那么往右  
            else   
                temp=temp->lchild;    //如果节点没有右孩子,那么去左孩子,没有左孩子,去前驱,也是走往左
        }
        return temp;
    }
}
 

void PostOrderTraverseThr(BiThrTree &T)  //后序遍历线索二叉树
{
    BiThrTree    par;
    p=T->lchild;  
    while(1)  
    {        
        while(p->LTag==0)   
            p=p->lchild;        
        if(p->RTag==0)      
            p=p->rchild;      
        else      break;        //p指向第一个被访问的节点
    }  
    while(p!=T)   
    {      
        printf("%c",p->data) ;
        par=parent(T,p);    //parent是p的双亲:     
        if(T==par)        //1.若parent是thrt,即p是根节点,则无后继      
            p=T;        
        else if(p==par->rchild || par->RTag==1)    //2.若p是双亲的右孩子,或者是独生左孩子,则后继为双亲   
            p=par;      
        else      
        {   
            while(par->RTag==0)  //3.若p是有兄弟的左孩子,则后继为双亲的右子树上按照后续遍历访问的第一个节点。  
            {               
                par=par->rchild;   
                while(par->LTag==0)        
                {                  
                    par=par->lchild;         
                }         
            }         
            p=par;   
        }
    }
}

void main()
{
    int m;
    printf("1 前序线索化二叉树的建立与遍历\n");
    printf("2 后序线索化二叉树的建立与遍历\n");
    printf("请选择:\n");
    scanf("%d",&m);
    if(m==1 || m==2)
    {
    switch(m)
    {
    case 1:
        BiThrTree T1;
        BiThrTree Thrt1;
        printf("请输入:\n");
        CreateBiThrTree(T1);
        printf("前序线索化二叉树:\n");
        PreOrderThreading(Thrt1,T1);
        PreOrderTraverseThr(Thrt1);
        break;
    case 2:
        BiThrTree T2;
        BiThrTree Thrt2;
        printf("请输入:\n");
        CreateBiThrTree(T2);
        printf("后序线索化二叉树:\n");
        PostOrderThreading(Thrt2,T2);
        PostOrderTraverseThr(Thrt2);
        break;
    }
    }
    else
        printf("输入错误!请重新选择:\n");
}
这是正确的代码,有兴趣的朋友可以看看·····
2011-11-04 22:46
快速回复:二叉树前、中、后线索化及遍历程序,没报错,但没结果,求解释!!!! ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.014733 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved