thread.cpp

常用算法与数据结构原代码

#include <iostream.h>

typedef struct node{
	char data;
	node *lchild,*rchild;
	int lflg,rflg;
} NODE;

typedef struct lnode {
	NODE *data;
	lnode *link;
} LNODE;

LNODE *top;

void l_push(NODE *x,LNODE *&toppt)
{
	LNODE *p=new LNODE;
	p->data=x;
	p->link=toppt;
	toppt=p;
}

int l_pop(NODE *&x,LNODE *&toppt)
{
	LNODE *p=toppt;
	if (toppt==NULL)
		return 1;
	x=p->data;
	toppt=p->link;
	delete p;
	return 0;
}

NODE *threaded(NODE *t)
{
	NODE *p,*pr,*h;
	if (t==NULL)
		return NULL;
	top=NULL;
	p=t;pr=NULL;
	do{
		while (p!=NULL)
		{
			l_push(p,top);
			p=p->lchild;
		}
		l_pop(p,top);
		if (pr==NULL)
		{
			h=p;
			p->lflg=0;
		}
		else
		{
			if (p->lchild==NULL)
			{
				p->lchild=pr;
				p->lflg=1;
			}
			else
				p->lflg=0;
			if (pr->rchild==NULL)
			{
				pr->rchild=p;
				pr->rflg=1;
			}
			else
				pr->rflg=0;
		}
		pr=p;
		p=p->rchild;
	}
	while (p!=NULL || top!=NULL);
	pr->rflg=0;
	return h;
}