穿線二叉木の実現
5361 ワード
#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;
}