linetree.cpp

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

#include <iostream.h>

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

NODE *prev(NODE *t)
{
	if (t->lflg==1 || t->lchild==NULL)
		return t->lchild;
	t=t->lchild;
	while (t->rflg==0)
		t=t->rchild;
	return t;
}

NODE *succ(NODE *t)
{
	if (t->rflg==1 || t->rchild==NULL)
		return t->rchild;
	while (t->lflg==0)
		t=t->lchild;
	return t;
}

void left_insert(NODE *p,NODE *q,NODE *&hpt)
{
	NODE *temp;
	if (p->lflg==1 || p->lchild==NULL)
	{
		if (p->lchild==NULL)
			hpt=q;
		q->lflg=p->lflg; q->lchild=p->lchild;
		q->rflg=1;       q->rchild=p;
		p->lflg=0;       p->lchild=q;
	}
	else
	{
		temp=prev(p);
		q->rflg=temp->rflg;
		q->rchild=temp->rchild;
		q->lflg=1;
		q->lchild=temp;
		temp->rflg=0;
		temp->rchild=q;
	}
}

void right_insert(NODE *p,NODE *q)
{
	NODE *temp;
	if (p->rflg==1 || p->rchild==NULL)
	{
		q->rflg=p->rflg; q->rchild=p->rchild;
		q->lflg=1;       q->lchild=p;
		p->rflg=0;       p->rchild=q;
	}
	else
	{
		temp=succ(p);
		q->lflg=temp->lflg;
		q->lchild=temp->lchild;
		q->rflg=1;
		q->rchild=temp;
		temp->lflg=0;
		temp->lchild=q;
	}
}

NODE *th_sort_t(char *str,NODE *& hpt)
{
	NODE *root,*head,*p,*t;
	if (*str=='\0')
		return NULL;
	head=root=new NODE;
	root->data=*str++;
	root->lchild=root->rchild=NULL;
	root->lflg=root->rflg=0;
	while (*str)
	{
		t=new NODE;
		t->data=*str++;
		p=root;
		while (1)
		{
			if (t->data<=p->data)
				if (!p->lflg && p->lchild)
					p=p->lchild;
				else
				{
					left_insert(p,t,head);
					break;
				}
			else
				if (!p->rflg && p->rchild)
					p=p->rchild;
				else
				{
					right_insert(p,t);
					break;
				}
		}
	}
	hpt=head;
	return root;
}

void midorder(NODE *t)
{
	if (t!=NULL)
	{
		if (t->lflg==0)
			midorder(t->lchild);
		cout<<t->data<<endl;
		if (t->rflg==0)
			midorder(t->rchild);
	}
}

void main()
{
	char s[]="abcdefg";
	NODE *root,*head;
	root=th_sort_t(s,head);
	midorder(root);
}