C++实现树的建立 |21xrx.com

C++实现树的建立

2023-06-24 12:12:45 深夜i -- --

C++ 树建立

C++语言是一种非常好用和强大的编程语言，用它来实现各种数据结构都相当方便。在这里，我们将介绍如何使用C++语言来实现树的建立。

在计算机科学中，树是一种非常常见的数据结构，它由节点和边组成。其中，节点表示树的一个元素，而边则表示节点之间的关系。根据树的定义，每个节点只能有一个父节点，但可以拥有多个子节点。

C++语言提供了一个非常方便的容器类——STL中的vector，可以用它来表示树的节点。关于树的边，则可以用二维数组或结构体来存储。

下面展示如何用C++语言来实现树的建立：

1.首先，我们需要定义一个节点Class来表示树的节点：


class TreeNode {
public:
  int val;
  vector<TreeNode*> children;
  TreeNode(int _val) : val(_val) {};
  void addChild(TreeNode* node){
    children.push_back(node);
  }
};

在这个节点Class中，我们用val变量来表示该节点的值，用vector 类型的变量来存储该节点的所有子节点。

2.下一步，我们需要写一个函数来建立树：


TreeNode* buildTree(vector<vector<int>>& nodes) {
  unordered_map<int, TreeNode*> mp;
  for (auto& node : nodes) {
    int parent = node[0], child = node[1];
    if (!mp[parent]) mp[parent] = new TreeNode(parent);
    if (!mp[child]) mp[child] = new TreeNode(child);
    mp[parent]->addChild(mp[child]);
  }
  return mp.begin()->second;
}

这个函数接收一个二维数组nodes，其中nodes[i][0]代表节点i的父节点，nodes[i][1]代表节点i的子节点。这个函数首先创建一个unordered_map 类型的字典，用于存储树的所有节点。然后，遍历nodes数组，对于每个节点，如果它不存在于字典中，则创建一个新的节点，然后将这个节点添加到字典中。接着，我们把该节点添加到父节点的子节点列表中。

最后，我们返回字典中第一个节点，即树的根节点。

3.最后，我们可以测试我们的树是否正确建立：


void traverseTree(TreeNode* root) {
  if (!root) return;
  cout << root->val << " ";
  for (auto child : root->children)
    traverseTree(child);
}
int main() {
  vector<vector<int>> nodes = { 2, 1, 2, 2, 6, 7};
  TreeNode* root = buildTree(nodes);
  traverseTree(root); //输出：1 2 4 5 7 3 6
  return 0;
}

在这个测试例子中，我们用buildTree函数建立了一个包含7个节点的树。然后，我们用traverseTree函数来遍历这个树，输出每个节点的值。运行这个程序，我们可以看到输出结果为：1 2 4 5 7 3 6，说明树的建立成功。

总结

在这篇文章中，我们讲述了如何使用C++语言来实现树的建立。通过定义一个节点Class和一个buildTree函数，我们成功地创建了一棵树，并对它进行了遍历。希望本文能够对大家学习C++语言和树的建立有所帮助。

上一篇: idea打包java可执行jar包

下一篇: C++函数中值的传递方式：引用和指针

评论区

()

相似文章