| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1376 人关注过本帖
标题:先序二叉树为什么是无限循环
只看楼主 加入收藏
yf879326915
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2017-4-12
收藏
 问题点数:0 回复次数:2 
先序二叉树为什么是无限循环
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef char TElemType;
typedef enum PointerTag{Link,Thread};
typedef struct BiThrNode{
    TElemType data;
    struct BiThrNode *lchild,*rchild;
    PointerTag LTag,RTag;
}BiThrNode,*BiThrTree;
BiThrTree pre;

Status CreateBiThrTree(BiThrTree &T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#') T=NULL;
    else
    {
        if(!(T=(BiThrNode*)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
        T->data=ch;
        T->LTag=Link;
        T->RTag=Link;
        CreateBiThrTree(T->lchild);
        CreateBiThrTree(T->rchild);
    }
    return OK;
}


Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e))
{   
    BiThrTree p;
    p=T->lchild;
    while(p!=T)
    {
        while(p->LTag==Link) p=p->lchild;
        if(!Visit(p->data)) return ERROR;
        while(p->RTag==Thread&&p->rchild!=T)
        {
            p=p->rchild; Visit(p->data);
        }
        p=p->rchild;
    }
    return OK;
}
void InThreading(BiThrTree p)
{
    if(p){
        InThreading(p->lchild);
        if(!p->lchild){p->LTag=Thread; p->lchild=pre;}
        if(!pre->rchild){pre->RTag=Thread; pre->rchild=p;}
        pre=p;
        InThreading(p->rchild);
    }
}


Status InOrderThreading(BiThrTree &Thrt,BiThrTree T)
{
    if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrTree)))) exit(OVERFLOW);
    Thrt->LTag=Link;
    Thrt->RTag=Thread;
    Thrt->rchild=Thrt;
    if(!T) Thrt->lchild=Thrt;
    else{
        Thrt->lchild=T;
        pre=Thrt;
        InThreading(T);
        pre->rchild=Thrt;
        pre->RTag=Thread;
        Thrt->rchild=pre;
    }
    return OK;
}

Status PrintElement(TElemType e) {
    printf("%c", e);
    return OK;
}
















void PreThreading(BiThrTree p) //前序线索化二叉树  
{  
    if(p)  
    {
        if(!p->lchild)  { p->LTag = Thread; p->lchild = pre;   }  
        if(!pre->rchild)  {pre->RTag = Thread; pre->rchild = p;  }
        pre = p;
        if(p->LTag==Link)  PreThreading(p->lchild);
        if(p->RTag==Link)  PreThreading(p->rchild);  
    }  
}  

Status PreOrderThreading(BiThrTree &Thrt,BiThrTree T)
{
    if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrTree)))) exit(OVERFLOW);
    Thrt->LTag=Link;
    Thrt->RTag=Thread;
    Thrt->rchild=Thrt;
    if(!T) Thrt->lchild=Thrt;
    else{
        Thrt->lchild=T;
        pre=Thrt;
        PreThreading(T);
        pre->rchild=Thrt;
        pre->RTag=Thread;
        Thrt->rchild=pre;
    }
    return OK;
}

Status PreOrderTraverse_Thr(BiThrTree L,Status(*Visit)(TElemType e)) //前序遍历线索化二叉树  
{  
    BiThrTree p;
    p = L->lchild;  
    while(p != L)  
    {  
        Visit(p->data);  
        if(p->LTag == Link)  
            p = p->lchild;  
        else  
            p = p->rchild;  
    }  
    return OK;  
}  
   

void main()
{
    BiThrTree T,L,Thrt;
    //TElemType b,d,e;
    //char a;
    printf("创建二叉树,按先序次序输入二叉树中结点的值:\n");
    CreateBiThrTree(T);
    if(InOrderThreading(Thrt,T)==OK) printf("成功建立中序线索化链表!\n");
    printf("中序遍历线索二叉树,结果是:\n");
    InOrderTraverse_Thr(Thrt,PrintElement);
    printf("\n");
    if(PreOrderThreading(Thrt,T)==OK) printf("成功建立先序线索化链表!\n");
    printf("先序遍历线索二叉树,结果是:\n");
    PreOrderTraverse_Thr(Thrt,PrintElement);
    printf("\n");
//    if(PostOrderThreading(Thrt,T)==OK) printf("成功建立后序线索化链表!\n");
    printf("后序遍历线索二叉树,结果是:\n");
//    PostOrderTraverse_Thr(Thrt,PrintElement);
    printf("\n");
      
}
搜索更多相关主题的帖子: include 二叉树 
2017-04-18 22:35
yangfrancis
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:141
帖 子:1510
专家分:7661
注 册:2014-5-19
收藏
得分:0 
为你的先序遍历块的变量加上注释
2017-04-19 12:12
marlow
Rank: 6Rank: 6
等 级:侠之大者
威 望:2
帖 子:125
专家分:419
注 册:2016-7-18
收藏
得分:0 
程序运行没有问题:
图片附件: 游客没有浏览图片的权限,请 登录注册

一切都在学习、尝试、摸索中
2017-04-20 20:08
快速回复:先序二叉树为什么是无限循环
数据加载中...
 
   



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

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