posts - 100,  comments - 15,  trackbacks - 0
二叉树线索化
输入二叉树先序，建树，然后中序线索化，遍历输出
  1#include<iostream>
  2using namespace std;
  3
  4enum PointerTag
  5{ 
  6    Link,Thread        //枚举值Link和Thread分别为0，1
  7}; 
  8
  9struct BiThrNode    //线索二叉树的结点类型
 10{
 11    char data;
 12    PointerTag LTag;    //左标志
 13    PointerTag RTag;    //右标志
 14    BiThrNode *lchild;    //左孩子指针
 15    BiThrNode *rchild;    //右孩子指针
 16};
 17
 18typedef BiThrNode* BiThrTree;
 19BiThrNode *pre=NULL; //全局量
 20
 21void InOrderThreading(BiThrTree & Thrt,BiThrTree T);//线索化
 22void InThreading(BiThrTree p);//中序遍历线索化
 23bool PreOrderCreatBiTree(BiThrTree &T);//先序建立树
 24void InOrderTraverse_Thr(BiThrTree T);//中序遍历线索树
 25
 26int main()
 27{
 28    BiThrTree T,Thrt;
 29    printf("输入先序序列('#'表示空节点)建立二叉树：\n");
 30    PreOrderCreatBiTree(T);//先序建立树
 31    InOrderThreading(Thrt,T);//中序线索化
 32    printf("中序线索化，中序遍历得中缀式：\n");
 33    InOrderTraverse_Thr(Thrt);//中序遍历线索树
 34    printf("\n");
 35    return 0;
 36}
 37
 38void InOrderThreading(BiThrTree & Thrt,BiThrTree T)
 39{
 40    Thrt=new BiThrNode;
 41    Thrt->LTag=Link;
 42    Thrt->RTag=Thread;
 43    Thrt->rchild=Thrt;
 44    if(!T) Thrt->lchild=Thrt;
 45    else{
 46        Thrt->lchild=T;
 47        pre=Thrt;
 48        InThreading(T);
 49        pre->rchild=Thrt;
 50        pre->RTag=Thread;
 51        Thrt->rchild=pre;
 52    }
 53}
 54
 55void InThreading(BiThrTree p)
 56{
 57    if(p)
 58    {
 59        InThreading(p->lchild);
 60        if(!p->lchild){ p->LTag=Thread; p->lchild=pre;}
 61        if(!pre->rchild){ pre->RTag=Thread; pre->rchild=p; }
 62        pre=p;
 63        InThreading(p->rchild);
 64    }
 65}
 66
 67bool PreOrderCreatBiTree(BiThrTree &T)
 68{//该节点非空返回true，双亲节点对应标志Link，空时返回false，双亲节点对应标志应为Thread
 69    char ch;
 70    scanf("%c",&ch);
 71    if(ch=='#')
 72    {
 73        T=NULL;
 74        return false;
 75    }else {
 76        T=new BiThrNode;
 77        T->data=ch;
 78        if(PreOrderCreatBiTree(T->lchild)) T->LTag=Link;    //左孩子存在则左标志为Link
 79        else T->LTag=Thread;
 80        if(PreOrderCreatBiTree(T->rchild)) T->RTag=Link;    //右孩子存在则右标志为Link
 81        else T->RTag=Thread;
 82    }
 83    return true;
 84}
 85
 86
 87void InOrderTraverse_Thr(BiThrTree T)
 88{
 89    BiThrNode *p;
 90    p=T->lchild;
 91    while(p!=T)
 92    {
 93        while(p->LTag==Link) p=p->lchild;
 94        printf("%c",p->data);
 95        while(p->RTag==Thread && p->rchild!=T) //if(p->RTag==Thread && p->rchild!=T)
 96        {
 97            p=p->rchild;
 98            printf("%c",p->data);
 99        }
100        p=p->rchild;
101    }
102}
posted on 2009-05-13 17:00 wyiu 阅读(556) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by:
C++博客
Copyright ©2024 wyiu