回 帖 发 新 帖 刷新版面

主题:中序遍历线索二叉树,得不到正确的输出?大侠们帮着看看

#include <stdio.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define NULL 0
typedef int ElemType;
typedef int Status;
typedef struct BiThrNode
{ElemType data;
 struct BiThrNode *lchild,*rchild;
 int ltag,rtag;
}BiThrNode,*BiThrTree;
BiThrTree pre=NULL;
Status CreateBiThrTree(BiThrTree &T)
{//创建二叉链表
 char ch;
 scanf("%c",&ch); getchar();
 if(ch==' ') T=NULL;
 else
 {T=(BiThrTree)malloc(sizeof(BiThrNode));
  if(!T) return ERROR;
  T->data=ch;
printf("%c的左结点为:",ch);
   CreateBiThrTree(T->lchild);
printf("%c的右结点为:",ch);
  CreateBiThrTree(T->rchild);
 }
 return OK;
}
void InThreading(BiThrTree p)
{if(p)
 {InThreading(p->lchild);
 if(!p->lchild){p->ltag=1;p->lchild=pre;}
 if(!pre->rchild) {pre->rtag=1;pre->rchild=p;}
  printf("当前访问的结点为:%c\n",p->data);
  pre=p;
  InThreading(p->rchild);}
}
Status InOrderThreading(BiThrTree &Thrt,BiThrTree T)
{//对带头结点的二叉链表进行中序线索化
 
   Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
    if(!Thrt) return ERROR;
    Thrt->ltag=0; Thrt->rtag=1;
    Thrt->rchild=Thrt;
    if(!T) Thrt->lchild=Thrt;
    else
    {Thrt->lchild=T; pre=Thrt;
     InThreading(T);
     pre->rchild=Thrt; pre->rtag=1;
     Thrt->rchild=pre;
    }
    return OK;
}
Status InOrderTraverse_Thr(BiThrTree Thrt)
{//中序遍历线索二叉树非递归算法
BiThrTree p;
p=Thrt->lchild;
while(p!=Thrt)
{while(p->ltag==0) p=p->lchild;
 printf("%2c",p->data);
 while(p->rtag==1 && p->rchild!=Thrt)
 {p=p->rchild;printf("%2d",p->data);}
  p=p->rchild;
}
return OK;
}


main()
{BiThrTree T,Thrt;
printf("---------创建二叉树--------------\n");
printf("输入第一个结点:\n");
CreateBiThrTree(T);
printf("---------中序线索化二叉树---------------------\n");
InOrderThreading(Thrt,T);
printf("\n");
InOrderTraverse_Thr(Thrt);
printf("\n");


}

回复列表 (共3个回复)

沙发

typedef struct BiThrNode
{ElemType data;
 struct BiThrNode *lchild,*rchild;
 int ltag,rtag;
}BiThrNode,*BiThrTree;/*这里为什么是*BiThrTree,这样下面定义的变量都成指针了,你把它改一下,再把下面的变量改一下,应该可以的,改成BiThrTree,然后定义的时候用,BiThrTree *p.

板凳

这个程序,我测了半天没弄明白,
线索我不太懂。

只能打印出总根结点的右子树。
过几天回答

3 楼

int CreateBiThrTree(BiThrTree &T){
char ch;
scanf("%c",&ch);
getchar();
if(ch==' ') T=NULL;
else{
T=(BiThrTree)malloc(sizeof(BiThrNode));
if(!T) exit(1);
T->data=ch;
printf("%c的左结点为:",ch);
CreateBiThrTree(T->lchild);
if(T->lchild!=NULL) T->ltag=0;
printf("%c的右结点为:",ch);
CreateBiThrTree(T->rchild);
if(T->rchild!=NULL) T->rtag=0;
}
return 0;
    }



#include<stdlib.h>

我来回复

您尚未登录,请登录后再回复。点此登录或注册