树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。
树是一种特殊的数据结构。它满足：每个顶点有零个或多个子顶点；没有父顶点的顶点称为根顶点；每一个非根顶点有且只有一个父顶点；除了根顶点外，每个子顶点可以分为多个不相交的子树。下面将利用二叉链表完成二叉树类的编写。实际上，对于一般的树，只需将指针域由两个指针更改为指针数组即可，其基本思想不变，因此只编写二叉树类。
二叉链表也是一种链表。因此首先编写如下的结构体：
template <typename T>
struct tree_node
{
tree_node *left;
tree_node *right;
T data;
tree_node(T k) : data(k), left(nullptr), right(nullptr) {}
};
基本同线性表，但区别是递归思想得到了广泛的应用。程序如下：
template <typename T>
class tree
{
static T error; // 用于指示异常
tree_node<T> *g;
void destroy_node(tree_node<T> *p)
{
if (p->left)
destroy_node(p->left);
if (p->right)
destroy_node(p->right);
delete p;
}
tree_node<T> *copy_node(const tree_node<T> *p)
{
if (!p)
return nullptr;
tree_node<T> *q(new tree_node<T>(p->data));
q->left = this->copy_node(p->left);
q->right = this->copy_node(p->right);
return q;
}
public:
tree() : g(nullptr) {}
tree(T gen) : g(new tree_node<T>(gen)) {}
tree(tree_node<T> *p) : g(this->copy_node(p)) {}
tree(const tree &x) : g(this->copy_node(x.g)) {}
tree &operator=(const tree &x)
{
if (g)
destroy_node(g);
g = this->copy_node(x.g);
return *this;
}
~tree()
{
if (g)
destroy_node(g);
}
};
template <typename T>
T tree<T>::error = 0;
此程序基本上同析构函数。
template <typename T>
void cleartree(tree<T> &x)
{
x.destroy_node(x.g);
x.g = nullptr;
}
一个树的深度可以很容易由其左右子树的深度确定，因此利用递归思想很容易写出程序：
template <typename T>
unsigned treedepth(const tree<T> &x)
{
if (!x.g)
return 0;
unsigned a(treedepth(tree<T>(x.g->left))), b(treedepth(tree<T>(x.g->right)));
return a > b ? ++a : ++b;
}
直接返回即可，但若为空树则输出错误。程序如下：
template <typename T>
T &root(tree<T> &x)
{
if (x.g)
return x.g->data;
return tree<T>::error;
}
由于树结构的特殊性，因此要想确定一个顶点的位置，必须提供从根顶点到待插入顶点的位置，因此传参时利用字符串确定顶点位置。程序如下：
tree &insert(const char *s, T e)
{
if (!s)
{
if (!g)
g = new tree_node<T>(e);
else
g->data = e;
return *this;
}
tree_node<T> *p(g);
do
if (*s == 'L')
if (!p->left)
p = p->left = new tree_node<T>(0);
else
p = p->left;
else if (*s == 'R')
if (!p->right)
p = p->right = new tree_node<T>(0);
else
p = p->right;
while (*++s);
if (p)
p->data = e;
else
p = new tree_node<T>(e);
return *this;
}
删除顶点是插入顶点的逆操作，因此确定顶点的方式同插入。程序如下：
tree &del(const char *s)
{
if (!s)
{
destroy_node(g);
g = nullptr;
return *this;
}
tree_node<T> *p(g);
do
if (*s == 'L')
{
if (!p->left)
return *this;
p = p->left;
}
else if (*s == 'R')
{
if (!p->right)
return *this;
p = p->right;
}
while (*++s);
if (p)
destroy_node(p);
return *this;
}
有了插入删除顶点的基础，我们很容易实现二叉树的输入，即从根顶点开始逐个插入顶点。由于字符串输入有效，因此不能根据输入流的状态直接判断输入是否结束。这里采用字符串"End"来标志树的输入的结束。程序如下：
#include <string>
template <typename T>
std::istream &operator>>(std::istream &c, tree<T> &x)
{
std::string s;
T e;
cleartree(x);
c >> x.g->data;
do
{
c >> s;
if (s == "End")
return c;
c >> e;
x.insert(s.c_str(), e);
} while (true);
}
由于树结构的特殊性，无法直接在命令行窗口直接显示其结构，因此输出其先序序列、中序序列及后序序列。由于序列长度未知，因此利用标准库类vector，首先包含头文件：
#include <vector>
std::vector<T> front() const
{
if (!g)
return std::vector<T>();
std::vector<T> x;
x.push_back(g->data);
std::vector<T> y(tree<T>(g->left).front()), z(tree<T>(g->right).front());
x.insert(x.end(), y.begin(), y.end());
x.insert(x.end(), z.begin(), z.end());
return x;
}
std::vector<T> middle() const
{
if (!g)
return std::vector<T>();
std::vector<T> x(tree<T>(g->left).middle()), z(tree<T>(g->right).middle());
x.push_back(g->data);
x.insert(x.end(), z.begin(), z.end());
return x;
}
std::vector<T> rear() const
{
if (!g)
return std::vector<T>();
std::vector<T> x(tree<T>(g->left).rear()), z(tree<T>(g->right).rear());
x.insert(x.end(), z.begin(), z.end());
x.push_back(g->data);
return x;
}
使用范围for循环遍历先、中、后序列。
template <typename T>
std::ostream &operator<<(std::ostream &c, const tree<T> &x)
{
if (!x.g)
{
c << "\t[空]" << std::endl;
return c;
}
c << "先序序列:";
std::vector<T> r(x.front());
for (auto i : r)
c << '\t' << i;
c << "\n中序序列:";
r = x.middle();
for (auto i : r)
c << '\t' << i;
c << "\n后序序列:";
r = x.rear();
for (auto i : r)
c << '\t' << i;
c << std::endl;
return c;
}