C++ 构建树结构 |21xrx.com

C++ 构建树结构

2023-07-05 07:23:09 深夜i -- --

C++语言树结构数据结构节点构建算法

C++ 是一种功能强大的编程语言，可用于构建各种应用程序，包括数据结构。其中一个常见的数据结构是树，它由一组节点组成，每个节点都有一个父节点和零个或多个子节点。节点和边的关系可以用指针或数组来表示，因此在 C++ 中构建树结构非常容易。

首先，我们需要定义节点的结构体。每个节点可以包含任意数据，比如整数、字符串或对象等。节点结构体也应该包含指向其子节点的指针和指向其父节点的指针。下面是一个简单的节点结构体示例：


struct Node {
  int data;
  Node* parent;
  std::vector<Node*> children;
};

在上面的代码中，我们使用了标准库的 vector 类型来存储子节点，使得向树中添加或删除节点变得更加容易。

接下来，我们需要为树定义一个类。树类应该包含根节点指针以及其他操作，如添加和删除节点、遍历树等。下面是一个简单的树类示例：


class Tree {
private:
  Node* root;
public:
  Tree(int data) {
    root = new Node { data, nullptr, {} };
  }
  ~Tree() {
    deleteSubtree(root);
  }
  Node* getRoot() const
    return root;
  
  Node* addChild(Node* parent, int data) {
    Node* child = new Node { data, parent, {} };
    parent->children.push_back(child);
    return child;
  }
  void deleteSubtree(Node* node) {
    for (Node* child : node->children) {
      deleteSubtree(child);
    }
    delete node;
  }
};

在上面的代码中，我们在构造函数中创建了根节点。addChild() 函数用于向树中添加节点，可以指定父节点和节点的数据。deleteSubtree() 函数用于删除整个子树。

最后，我们可以使用上面的代码来构建任意类型的树结构。例如，下面的代码演示了如何创建一个简单的树，并逐层打印出节点：


int main() {
  Tree tree(1);
  Node* node2 = tree.addChild(tree.getRoot(), 2);
  Node* node3 = tree.addChild(tree.getRoot(), 3);
  Node* node4 = tree.addChild(node2, 4);
  Node* node5 = tree.addChild(node2, 5);
  Node* node6 = tree.addChild(node3, 6);
  std::cout << "Level 0: " << tree.getRoot()->data << "\n";
  std::cout << "Level 1: " << node2->data << ", " << node3->data << "\n";
  std::cout << "Level 2: " << node4->data << ", " << node5->data << ", " << node6->data << "\n";
  return 0;
}

输出将是：

Level 0: 1 Level 1: 2, 3 Level 2: 4, 5, 6

在上面的代码中，我们创建了一个包含六个节点的树。我们指定了根节点的数据为 1，然后添加了四个子节点和两个子节点的子节点。最后，我们遍历树并打印出每个节点的数据。

可以看到，使用 C++ 构建树结构非常容易，并且我们可以使用任意的数据类型来存储节点数据。此外，使用指针和 vector 来表示节点和边的关系也使得向树中添加或删除节点变得非常容易。

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

下一篇: Devc++编译后代码自动缩进方法分享

评论区

()

相似文章