threadtree1.h

大学计算机专业课程中数据结构各章的算法设计

#include<iostream.h>
#include"ThreadTreeNode1.h"

class ThreadTree1
{
public:
     ThreadTreeNode1 * root;

	ThreadTree1(char *str="");
	ThreadTreeNode1 * create(char *str);

	 void inThreadTree();
	 void inThreadTree(ThreadTreeNode1 *p);

/*	 ThreadTreeNode1 * innext(ThreadTreeNode1 *p);
	 void inorder();

     ThreadTreeNode1 * inlast(ThreadTreeNode1 *p);
	 void inorder_last();

	 ThreadTreeNode1 * prenext(ThreadTreeNode1 *p);
	 void preorder();

	 ThreadTreeNode1 * postlast(ThreadTreeNode1 *p);
	 void postorder();*/
};

void ThreadTree1::inThreadTree()
{
	inThreadTree(root);
}
void ThreadTree1::inThreadTree(ThreadTreeNode1 *p)
{
	static ThreadTreeNode1* front=NULL;
	if(p!=NULL)
	{
		inThreadTree(p->left);
		if(p->left==NULL)
		{
			p->ltag=1;
			p->left=front;
		}
     if(p->right==NULL)
		 p->rtag=1;
     if(front!=NULL&&front->rtag==1)
		 front->right=p;
	 if(front!=NULL)
		 cout<<"front="<<front->data<<"\t\t";
	 else
		 cout<<"front=NULL\t";
	 cout<<" p="<<p->data<<"  ";
	 cout<<" ltag="<<p->ltag <<"  ";
	 cout<<" rtag="<<p->rtag <<"  ";

	 front=p;
	 inThreadTree(p->right);
	}
}/*
ThreadTreeNode1* ThreadTree1::inlast(ThreadTreeNode1 *p)
{
	if(p->ltag==1)
		p=p->left;
	else
	{
		p=p->left;
		while(p->rtag==0)
			p=p->right;
	}
	return p;
}
ThreadTreeNode1* ThreadTree1::innext(ThreadTreeNode1* p)
{
	if(p->rtag==1)
		p=p->right;
	else
	{
		p=p->right;
		while(p->ltag==0)
			p=p->left;
	}
	return p;
}
void ThreadTree1::inorder()

{
	ThreadTreeNode1 *p=root;
	if(p!=NULL)
	{
		cout<<"中根遍历中序二叉树";
		while(p->ltag==0)
			p=p->left;
		do
		{
			cout<<p->data<<" ";
			p=innext(p);

		}
		while(p!=NULL);
		cout<<endl;
	}
}
*/
ThreadTreeNode1 * ThreadTree1::prenext(ThreadTreeNode1 *p)
{
	if(p->ltag ==0)
		p=p->left ;
	else
	{
		if(p->rtag ==0)
			p=p->right;
		else
		{
			while(p->rtag ==1&&p->right !=NULL)
              p=p->right;
			p=p->right;
		}
	}
	return p;
}
void ThreadTree1::preorder()
{
    ThreadTreeNode1 *P=root;
	if(p!=NULL)
	{
		cout<<"先根次序遍历二叉数 “";
		do
		{
			cout<<p->data<<" ";
			p=prenext();

		}while(p!=NULL)
			cout<<endl;
	}
}
ThreadTreeNode1 * ThreadTree1::postlast(ThreadTreeNode1 *p)
{
	if(p->rtag ==0)
		p=p->right ;
	else
	{
		while(p->ltag ==1&&p->left !=NULL)
			p=p->left ;
            p=p->left ;
	}
	return p;
}