C++ 中的 Tree 模板类

• 下载源代码 - 6.32 Kb

引言

树在编程中非常常用。如果您使用过几次，就会注意到与树遍历和子节点管理相关的代码在所有情况下都基本相同。例如，这通常会包括诸如以下的方法：

void Node::add_child (Node* node);
void Node::set_parent (Node* parent);
int Node::num_children();
Node* Node::child (int i); // a get method

然而，尽管存在这种重复性，每次需要为新的数据类型组装一棵树时，您都必须重新编写代码。在本文中，我介绍了一个 Tree 类，它允许您将任何数据类型组装成树状结构，然后使用深度优先遍历对其进行操作。目前我只实现了 DFS 遍历。以后，可以以类似的方式实现其他遍历方式。

使用该类

首先，我将展示如何使用它

typedef Tree <char> TreeCls;
TreeCls g_tree;

这一行声明了一个 Tree，其节点可以包含“char”数据。同样，您可以为您的树结构选择任何您想要的“节点类型”。

在此示例中，我创建了这个树的全局实例。目前，树不包含任何节点。现在，我们需要填充树的节点。创建树比使用树进行遍历要复杂一些。因此，现在，让我们假设我们可以使用一个函数来填充树，例如

read_tree_from_file();

在此调用之后，我们的全局树变量将被填充了一些“char”数据。稍后我将详细介绍此函数。全局变量不好，但这只是一个片段。在您的代码中，您可能以其他方式填充树。

假设我们用一些节点填充了我们的树，这些节点可能看起来像这样

1
|--2
|--3
    |--5
    |--6
    |--7
|--4
    |--8
    |--9

如果上图未能正确显示“树”的可视化效果，那么下面的图可能会有所澄清

        1
       /|\
     /  |  \
   /    |    \
  2     3     4
       /|\    /\
      / | \  /  \
     5  6 7  8  9

这些数字只是用来为每个节点分配一个“名称”……以便识别它们。

现在，这是以 DFS 顺序遍历树的代码

TreeCls::iterator_dfs it = g_tree.begin();
TreeCls::iterator_dfs it_end = g_tree.end();

while ( it != it_end ) 
{
    char& c = *it;
    std::cout << c << "\n";
    ++it;
}

解释

首先，您使用树的 begin() 成员函数请求树第一个节点的迭代器。之后，如果您决定添加更多迭代器类型，当然，您必须将 begin() 函数的名称更改为诸如 begin_dfs() 之类的名称。

end() 提供一个指向 DFS 顺序中最后一个节点之后的迭代器。++ 以 DFS 顺序移动迭代器。在任何时候，您都可以解引用迭代器以返回构成节点数据的“char”的引用。

现在，关于实现细节。

基本上，我们需要将用户的数据类型转换为一个可以“组装”到树中的节点。让我们称用户的数据类型为“T”。树中的节点**不能**是 T 类型。这是因为它们需要支持比 T 中可能定义的更多操作。这些操作就是我们在最开始提到的。

因此，我们在 Tree 类中定义了一个嵌套类型 Node。这个 Node 类将 T 数据类型“包含”为一个成员变量。Node 类型的其余变量用于树遍历和子节点管理。

我们还定义了嵌套的 iterator_dfs 数据类型。它定义了 !=、== 和 ++ 运算符。它的解引用运算符、operator * 和箭头运算符、operator --> 被编码为返回当前节点的 T 类型。

迭代器是如何跟踪“当前”节点的？很简单。它使用显式堆栈实现了一个简单的 DFS 搜索。

现在可以在关联的代码中查看所有这些详细信息。

构建树

现在回到我们最初创建树的问题。起初，我想提供一个接口，如下所示：

typedef Tree<int> IntTree;
IntTree tree;

IntTree::iterator_dfs it = tree.begin();
*it = 5;

tree.add_child (it, 10);
tree.add_child (it, 125);
it++;

然而，在实现过程中，这被证明是有问题的。这是因为 operator++() 的实现方式。迭代器的 operator()++ 首先将所有子节点收集到堆栈中，然后返回下一个节点。在“当前”迭代器处添加新节点可能会导致 DFS 堆栈不一致。我或许可以销毁堆栈并重新遍历它，但这不仅效率低下，而且也很难验证。

因此，我决定放弃这种方法，而是将内部的 Node 类设为 public，尽管我曾想将其设为 private（因为应用程序不应该知道树的实际节点类）。

所以要构建树，我们必须使用 Node 类的原始接口，如下所示：

TreeCls::Node* node = new TreeCls::Node ( char ('a') ) ;
parent_node -> add_child (node);

parent_node 是您要添加子节点的父节点。Node 类定义了三个构造函数；一个无参数构造函数，一个带 T 类型参数（按值传递）的构造函数，以及一个带父节点和 T 类型值的第三个构造函数。

函数 read_tree_from_file() 只是为了完成测试。它不是 Tree 类代码的一部分。它从文本文件中读取树描述，该文件包含所有节点在遇到节点时的子节点数量，这些节点是在 DFS 遍历中遇到的。因此，给定文件：

3
2
0
0
0
1

前面的 3 表示根节点有三个子节点。向下遍历到第一个子节点，它有两个子节点。这两个子节点都没有子节点。然后，第二个子节点再次没有子节点。第三个子节点有一个子节点。（**注意**：这与上面显示的树不是同一棵树。）

该函数简单地创建一个堆栈，读取一个数字，创建指定数量的子节点，并为这些新子节点设置适当的父节点。每创建一个节点，都会为其分配一个 char 值。这有助于以后“打印”树。

Tree 类在其自己的 .h 文件中。另一个文件用于测试它。该项目是使用 VC++ 2005 Express 创建的。

您可以自由地在您的工作中 unrestricted 地使用此代码。欢迎提出所有评论和批评。