# 二叉树的相关操作

BiTree() { bt = Creat(bt); } //创建树
~BiTree() { ReleaseTree(bt); } //销毁树
void PreOrder() { PreOrder(bt); } //前序遍历
void InOrder() { InOrder(bt); } //中序遍历
void PostOrder() { PostOrder(bt); } //后序遍历
void levelOrder() { levelOrder(bt); }//层序遍历
void swapLR() { swapLR(bt); } //交换子树
int leafCount() { return leafCount(bt); } //计算叶子
int nodeCount() { return nodeCount(bt); } //计算结点
int highOfTree() { return highOfTree(bt); } //计算树高

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
template<class T>
struct Node
{
T data;
Node<T> *L, *R;
};
template<class T>
class BiTree
{
public:
BiTree() { bt = Creat(bt); }    //创建树
~BiTree() { ReleaseTree(bt); }    //销毁树
void PreOrder() { PreOrder(bt); }  //前序遍历
void InOrder() { InOrder(bt); }    //中序遍历
void PostOrder() { PostOrder(bt); }  //后序遍历
void LevelOrder() { LevelOrder(bt); }//层序遍历
void swapLR() { swapLR(bt); }        //交换子树
int leafCount() { return leafCount(bt); }  //计算叶子
int nodeCount() { return nodeCount(bt); }  //计算结点
int highOfTree() { return highOfTree(bt); } //计算树高
private:
Node<T> *bt;
Node<T> *Creat(Node<T>* bt);
void PreOrder(Node<T>* bt);
void InOrder(Node<T>* bt);
void PostOrder(Node<T>* bt);
void LevelOrder(Node<T>* bt);
void ReleaseTree(Node<T>* bt);
void swapLR(Node<T>* bt);
int leafCount(Node<T> *bt);
int nodeCount(Node<T> *bt);
int highOfTree(Node<T> *bt);
};
template<class T>
Node<T>* BiTree<T>::Creat(Node<T>* bt)
{
char ch;
cin >> ch;
if (ch == '#') bt = NULL;
else {
bt = new Node<T>; bt->data = ch;
bt->L = Creat(bt->L);
bt->R = Creat(bt->R);
}
return bt;
}
template<class T>
void BiTree<T>::PreOrder(Node<T>* bt)
{
if (bt == NULL) return;
else {
cout << bt->data;
PreOrder(bt->L);
PreOrder(bt->R);
}
}
template<class T>
void BiTree<T>::InOrder(Node<T>* bt)
{
if (bt == NULL) return;
else {
InOrder(bt->L);
cout << bt->data;
InOrder(bt->R);
}
}
template<class T>
void BiTree<T>::PostOrder(Node<T>* bt)
{
if (bt == NULL) return;
else {
PostOrder(bt->L);
PostOrder(bt->R);
cout << bt->data;
}
}
template<class T>
void BiTree<T>::LevelOrder(Node<T>* bt)
{
queue<Node<T> *> que;
if (bt == NULL)
return;
que.push(bt);
while (!que.empty())
{
Node<T> *q = que.front();
que.pop();
cout << q->data;
if (q->L != NULL)
que.push(q->L);
if (q->R != NULL)
que.push(q->R);
}
cout << endl;
}

template<class T>
void BiTree<T>::ReleaseTree(Node<T>* bt)
{
if (bt != NULL)
{
ReleaseTree(bt->L);
ReleaseTree(bt->R);
delete bt;
}
}
template<class T>
void BiTree<T>::swapLR(Node<T>* bt)
{
if (bt->L == NULL && bt->R == NULL)
return;
else {
swap(bt->L, bt->R);
}
if (bt->L)
swapLR(bt->L);
if (bt->R)
swapLR(bt->R);
}
template<class T>
int BiTree<T>::leafCount(Node<T>* bt)
{
int leaf = 0;
if (bt == NULL)
return 0;
else if (bt->L == NULL && bt->R == NULL)
return 1;
else
leaf = leafCount(bt->L) + leafCount(bt->R);
return leaf;
}
template<class T>
int BiTree<T>::nodeCount(Node<T>* bt)
{
int nodeNum = 0;
if (bt == NULL)
return 0;
else {
nodeNum = 1 + nodeCount(bt->L) + nodeCount(bt->R);
}
return nodeNum;
}
template<class T>
int BiTree<T>::highOfTree(Node<T>* bt)
{
int hL = 0, hR = 0;
if (bt == NULL)
return 0;
else {
hL = highOfTree(bt->L);
hR = highOfTree(bt->R);
if (hL < hR)
return hR + 1;
else
return hL + 1;
}
return 0;
}
int main()
{
char cont;
do
{
cout << "输入扩展的前序序列以创建树" << endl;
BiTree<char> bt;//树的构建

bt.PreOrder();//前序遍历
cout << endl;
bt.InOrder();//中序遍历
cout << endl;
bt.PostOrder();//后序遍历
cout << endl;
bt.LevelOrder();//层序遍历
cout << endl;
cout << bt.nodeCount() << endl//结点数
<< bt.leafCount() << endl//叶子数
<< bt.highOfTree() << endl;//树高度
bt.swapLR();//交换子树
bt.PreOrder();//交换后前序
cout << endl;
bt.InOrder();//交换后中序
cout << endl;
bt.PostOrder(); //交换后后序
cout << endl;
bt.LevelOrder();//交换后层序
cout << endl;

cin >> cont;
} while (cont == 'Y');//再来一次
return 0;
}