C++二叉チェーンテーブルのテンプレート実装
4518 ワード
C++二叉チェーンテーブルのテンプレート実装
#pragma once
//
#include
#include
#include
using namespace std;
template
struct BiNode
{
DataType data;
BiNode *lchild, *rchild;
};
template
struct ForPost
{
BiNode * ptr;
int flag;
};
template
class BiTree
{
public:
BiTree(){ root = Creat(root); }
~BiTree(){ release(root); }
void PreOrder(){ PreOrder(root); }
void InOrder(){ InOrder(root); }
void PostOrder(){ PostOrder(root); }
void LeverOrder();
private:
BiNode* root;
BiNode* Creat(BiNode* bt);
void release(BiNode* bt);
void PreOrder(BiNode* bt);
void InOrder(BiNode* bt);
void PostOrder(BiNode* bt);
};
//
template
void BiTree::PreOrder (BiNode* bt)
{
if (bt == NULL)
{
return;
}
else
{
cout << bt.data;
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
}
template
void BiTree::InOrder (BiNode* bt)
{
if (bt == NULL)
{
return;
}
else
{
InOrder(bt->lchild);
cout << bt.data;
InOrder(bt->rchild);
}
}
template
void BiTree::PostOrder(BiNode* bt)
{
if (bt == NULL)
{
return;
}
else
{
PostOrder(bt->lchild);
PostOrder(bt->rchild);
cout << bt.data;
}
}
// 1、 Q
// 2、 ，
// 3、 Q
// 3.1、q= Q
// 3.2、 q
// 3.3、 q ，
// 3.4、 q ，
//
template
void BiTree::LeverOrder ()
{
int front = -1;
int rear = -1;
if (root == NULL)
{
return;
}
queue Q;
BiNode* q;
Q[++rear] = root; //
while (front != rear) //
{
q = Q[++front];
cout << q.data;
if (q->lchild != NULL)
{
Q[++rear] = q->lchild;
}
if (q->rchild != NULL)
{
q[++rear] = q->rchild;
}
}
}
template
BiNode* BiTree::Creat(BiNode* bt)
{
cin >> ch;
if (ch == '#')
{
bt = NULL;
}
else
{
bt = new BiNode ;
bt->data = ch;
bt->lchild = Creat(bt->lchild);
bt->rchild = Creat(bt->rchild);
}
return bt;
};
template
void BiTree::release(BiNode* bt)
{
if (bt != NULL)
{
release(bt->lchild);
release(bt->rchild);
delete bt;
}
}
//
// 1、 s
// 2、 bt s
// 2.1、 bt
// 2.1.1、 bt->data
// 2.1.2、 bt
// 2.1.3、 bt
// 2.2、 s
// 2.2.1、 bt
// 2.2.2、 bt
template
void BiTree::PreOrder (BiNode* bt)
{
int top = -1;
stack S;
while (bt != NULL || top != -1)
{
while (bt != NULL)
{
cout << bt.data;
S[++top] = bt;
bt = bt->lchild;
}
if (top != -1)
{
bt = S[top--];
bt = bt->rchild;
}
}
}
template
void BiTree::InOrder (BiNode* bt)
{
int top = -1;
stack S;
while (bt != NULL || top != -1)
{
while (bt != NULL)
{
S[++top] = bt;
bt = bt->lchild;
}
if (top != -1)
{
bt = S[top--];
cout << root.data;
bt = bt->rchild;
}
}
}
// 1、 s
// 2、 bt
// 2.1、 bt
// 2.2.1、 bt flag=1
// 2.2.2、 bt
// 2.2、 s 2 ，
// 2.3、 ， 2，
template
void BiTree::PostOrder (BiNode* bt)
{
int top = -1;
stack S;
while (bt != NULL || top != -1)
{
while (bt != NULL)
{
top++;
S[top].ptr = bt;
S[top].flag = 1;
}
while (top != -1 && s[top].flag = 2)
{
bt = S[top--].ptr;
cout << bt.data;
}
if (top != -1)
{
S[top].flag = 2;
bt = s[top].ptr->rchild;
}
}
}