穿线二叉树的实现

#include <iostream>
#include <sstream>
using namespace std;

template<class T>
struct tbtnode
{
	T s_t;
	bool lflag;
	bool rflag;
	tbtnode *lchild;
	tbtnode *rchild;
};

template<class T>
tbtnode<T>* createtbt(tbtnode<T>* tbt, int k, ostream& out, istream& in)
{
	tbtnode<T> *p, *t;
	T tmp;
	out << "Input key: " << endl;
	in >> tmp;
	out << '\t' << tmp << endl;
	if ('0' != tmp)
	{
		p = new tbtnode<T>;
		p->s_t = tmp;
		p->lchild = NULL;
		p->rchild = NULL;
		p->lflag = 0;
		p->rflag = 0;
		if (0 == k) t = p;
		if (1 == k) tbt->lchild = p;
		if (2 == k) tbt->rchild = p;

		createtbt(p, 1, out, in);
		createtbt(p, 2, out, in);
	}

	return (t);
}

template<class T>
void pretraverse(tbtnode<T> *root)
{
	if (NULL != root)
	{
		cout << root->s_t << " ";
		pretraverse(root->lchild);
		pretraverse(root->rchild);
	}
}

template<class T>
void intraverse(tbtnode<T> *root)
{
	if (NULL != root)
	{
		intraverse(root->lchild);
		cout << root->s_t << " ";
		intraverse(root->rchild);
	}
}

template<class T>
void postraverse(tbtnode<T> *root)
{
	if (NULL != root)
	{
		postraverse(root->lchild);
		postraverse(root->rchild);
		cout << root->s_t << " ";
	}
}

template<class T>
void inthread(tbtnode<T> *tbt, tbtnode<T> **h)
{
	if (NULL != tbt)
	{
		inthread(tbt->lchild, h);
		if (tbt->lchild == NULL)
		{
			tbt->lchild = *h;
			tbt->lflag = 1;
		}
		if ((*h != NULL) && ((*h)->rchild == NULL))
		{
			(*h)->rchild = tbt;
			(*h)->rflag = 1;
		}
		*h = tbt;
		inthread(tbt->rchild, h);
	}
}

template<class T>
void prethread(tbtnode<T> *tbt, tbtnode<T> **h)
{
	if (NULL != tbt)
	{
		if (tbt->lchild == NULL)
		{
			tbt->lchild = *h;
			tbt->lflag = 1;
		}

		if ((*h != NULL) && ((*h)->rchild == NULL))
		{
			(*h)->rchild = tbt;
			(*h)->rflag = 1;
		}

		*h = tbt;
		//*h = tbt->lchild;
		if (tbt->lflag == 0)
			prethread(tbt->lchild, h);
		if (tbt->rflag == 0)		
			prethread(tbt->rchild, h);
	}
}

template<class T>
void posthread(tbtnode<T> *tbt, tbtnode<T> **h)
{
	if (NULL != tbt)
	{
		posthread(tbt->lchild, h);
		posthread(tbt->rchild, h);

		if (tbt->lchild == NULL)
		{
			tbt->lchild = *h;
			tbt->lflag = 1;
		}

		if ((*h != NULL) && ((*h)->rchild == NULL))
		{
			(*h)->rchild = tbt;
			(*h)->rflag = 1;
		}
		*h = tbt;
	}
}

template<class T>
void inthtraverse(tbtnode<T> *tbt)
{
	tbtnode<T> *h;
	if (tbt == NULL) return;
	h = tbt;
	while (h->lflag == 0) h = h->lchild;
	cout << h->s_t << " ";
	while (h->rchild != NULL)
	{
		if (h->rflag == 1)
			h = h->rchild;
		else
		{
			h = h->rchild;
			while ((h->lflag == 0) && (h->lchild != NULL))
				h = h->lchild;
		}
		cout << h->s_t << " ";
	}
}

template<class T>
void prethtraverse(tbtnode<T> *tbt)
{
	tbtnode<T> *h;
	if (tbt == NULL) return;
	h = tbt;
	cout << tbt->s_t << " ";
	while (h->rchild != NULL)
	{
		if ((h->lflag == 0) && (h->lchild != NULL))
		{
			h = h->lchild;
		}
		else
		{
			h = h->rchild;
		}
		cout << h->s_t << " ";
	}
}

template<class T>
void posthtraverse(tbtnode<T> *tbt)
{
	tbtnode<T> *h;
	if (tbt == NULL) return;
	h = tbt;
}

int main()
{
	typedef tbtnode<char> tbtnode_char;
	tbtnode_char *root;
	//istringstream ssin(string("AB0DG000CE0H00F00"));
	istringstream ssin(string("ABCD00E00FG00H00IJK00L00MN00O00"));
	root = createtbt(root, 0, cout, ssin);
	pretraverse(root);
	cout << endl;
	intraverse(root);
	cout << endl;
	postraverse(root);
	cout << endl;

	cout << "通过穿线二叉树进行遍历" << endl;
	tbtnode_char *h = NULL;

	//inthread(root, &h);
	//inthtraverse(root);

	prethread(root, &h);
	prethtraverse(root);

	cout << endl;

	return 0;
}