4-2.c

《C程序员成长攻略》-黎陡-源代码-4282 中国水利水电出版社 程序员成长之路丛书

#include"stdio.h"
#include"conio.h"
#include"alloc.h"
typedef enum 
{ 
	Link,Thread
} pTag;

typedef struct BtTREE
{
	int data;
    pTag ltag,rtag;/*左右标志*/
    struct BtTREE *left,*right;
}

btNode,*btTree;/*线索二叉树的结点类型*/
btTree Root,pre=NULL;
btTree T;

btTree Create()
{
	btTree root,p;
    int data;
    p=(btTree)malloc(sizeof(btNode));
	p->left=NULL;
	p->right=NULL;
    p->data=1;
    root=p;

    p=(btTree)malloc(sizeof(btNode));
    p->left=NULL;
    p->right=NULL;
    p->data=2;
    root->left=p;

    p=(btTree)malloc(sizeof(btNode));
    p->left=NULL;
    p->right=NULL;
    p->data=3;
    root->right=p;

    p=(btTree)malloc(sizeof(btNode));
    p->left=NULL;
    p->right=NULL;
    p->data=4;
    root->left->left=p;

    p=(btTree)malloc(sizeof(btNode));
    p->left=NULL;
    p->right=NULL;
    p->data=5;
    root->left->right=p;

    p=(btTree)malloc(sizeof(btNode));
    p->left=NULL;
    p->right=NULL;
    p->data=6;
    root->right->left=p;

    p=(btTree)malloc(sizeof(btNode));
    p->left=NULL;
    p->right=NULL;
    p->data=7;
    root->right->right=p;

    Root=root;
    return Root;
}

void InOrderThreading(btTree root)
{ 
	/*将二叉树p中序线索化*/
	btTree p=root,first,last;
	if(p)
	{   /*p非空时,当前访问结点是*p*/
		InOrderThreading(p->left);  /*左子树线索化*/
		/*以下直至右子树线索化之前相当于遍历算法中访问结点的操作*/
		p->ltag=(p->left)?Link:Thread;
		/*左指针非空时左标志为Link(即0),否则为Thread(即1)*/
		p->rtag=(p->right)?Link:Thread;
		if(pre)
		{ /*若*p的前趋*pre存在*/
		    if(pre->rtag==Thread) /*若*p的前趋右标志为线索*/
                pre->right=p; /*令*pre的右线索指向中序后继*/
			if(p->ltag==Thread) /**p的左标志为线索*/
				p->left=pre; /*令*p的左线索指向中序前趋*/
		} /*完成处理*pre的线索*/
		pre=p; /*令pre是下一访问结点的中序前趋*/
		InOrderThreading(p->right); /*右子树线索化*/
	}
	T->left=root;
	p=root;
	while(p)
	{
		first=p;
		p=p->left; 
	}
	first->left=T;
	p=root;
	while(p)
	{
		last=p; 
		p=p->right;
	}
	last->right=T;
}

main()
{
	btTree root,p,first,last;
	clrscr();
	Create();
	root=Root;
	InOrderThreading(root);
	p=T->left;
	while(p!=T)
	{
		while(p->ltag==Link) p=p->left;
		    printf("%d,",p->data);
		while(p->rtag==Thread && p->right!=T)
		{
			p=p->right;
			printf("%d ",p->data);
		}
		p=p->right; 
	}
	getch();
}