线索化二叉树.cpp

共有10个文件代码

#include <iostream.h>
#include <malloc.h>
#define Maxsize 100
#define Maxwidth 40
typedef char elemtype;
typedef struct node
{
	elemtype data;
	struct node *left,*right;
	int ltag,rtag;
}BTree;
void create(BTree * &b,char *str)
{
	BTree *stack[Maxsize],*p;
	int top=-1,k,j=0;  //top为栈指针，k指定是左还是右孩子，j为str指针
	char ch;
	b=NULL;
	ch=str[j];
	while(ch!='\0')
	{
		switch(ch)
		{
		case '(':top++;stack[top]=p;k=1;break;
		case ')':top--;break;
		case ',':k=2;break;
		default:p=(BTree *)malloc(sizeof(BTree));
			p->data=ch;p->left=p->right=NULL;
			if(b==NULL)
				b=p;
			else
			{
				switch(k)
				{
				case 1:stack[top]->left=p;break;
				case 2:stack[top]->right=p;break;
				}
			}
		}
		j++;
		ch=str[j];
	}
}
void printree(BTree *b)
{
	if(b!=NULL)
	{
		cout<<b->data;
		if(b->left!=NULL ||b->right!=NULL)
		{
			cout<<"(";
			printree(b->left);
			if(b->right!=NULL) 
				cout<<",";
			printree(b->right);
			cout<<")";
		}
	}
}

void thread(BTree *&r,BTree *&pre)
{
	if(r!=NULL)
	{
		thread(r->left,pre);  //左子树线索化
		if(r->left==NULL)
		{
			r->left=pre;     //建立当前节点的前驱线索
			r->ltag=1;
		}
		if(r->right==NULL)    //建立当前节点的后驱线索
		{
			r->right=r;
			r->rtag=1;
		}
		pre=r;
		thread(r->right,pre);      //右子树线索化
	}
}
BTree *createthread(BTree *b)
{
	BTree *pre,*root,*p;
	root=(BTree *)malloc(sizeof(BTree));  //建立根节点
	root->data='r';            //'r'表示根节点
	root->ltag=1,root->rtag=0;
	if(b==NULL)
	{
		root->left=root;
		root->right=root;
	}
	else
	{
		p=root->left=b;
		root->ltag=0;
		pre=root;       //p是前驱节点，供加线索用
		thread(p,pre);  //中序遍历线索化二叉树
		pre->right=root;
		pre->rtag=1;
		root->right=pre;
		root->rtag=1;
	}
	return root;
}
void inorder(BTree *b)
{
	BTree *p=b->right;
	cout<<"线索化后遍历:";
	do{
		cout<<p->data<<" ";
		while((p->ltag==1)&&(p->left!=b))
		{
			p=p->left;
			cout<<p->data<<" ";
		}
		p=p->left;
		while(p->rtag==0)
			p=p->right;
	}while(p!=b);
}
void main()
{
	BTree *b,*r;
	char s[40]={"(a(b(,c),d(e)))"};
	create(b,s);
	r=createthread(b);
	inorder(r);
}