C++树的构建和遍历 |21xrx.com

C++树的构建和遍历

2023-06-22 15:11:35 深夜i -- --

C++ 树的构建遍历

树是一种非线性结构，它由若干个节点构成，每个节点可以有零个或多个子节点。在计算机科学中，树经常用于描述层次和依赖关系。C++中，我们可以使用指针来构建和遍历树。

树的构建可以通过节点结构体和指针来完成。例如，我们可以定义一个节点结构体：


struct Node {
  int val;
  Node* left;
  Node* right;
  Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

以上代码定义了一个节点结构体，其中包括节点的值和左右子节点的指针。构造函数用于初始化节点的值和指针，并将左右子节点初始化为nullptr。在实际构建树的过程中，我们可以通过递归来动态地给节点分配子节点。例如，以下代码可以构建如下的一棵树：

5 / \ 3 7 / \ \ 1 4 9


Node* root = new Node(5);
root->left = new Node(3);
root->right = new Node(7);
root->left->left = new Node(1);
root->left->right = new Node(4);
root->right->right = new Node(9);

遍历树是在树上执行某些操作的过程，有三种主要的遍历方式：前序遍历、中序遍历和后序遍历。这些遍历方法采用不同的顺序访问节点和子节点。

前序遍历是指先访问根节点，再依次访问左右子节点的顺序，我们可以通过以下递归函数来实现：


void preorderTraversal(Node* root) {
  if (root == nullptr)
    return;
  
  cout << root->val << " ";
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

中序遍历是指先访问左子节点，再访问根节点，最后访问右子节点的顺序，我们可以通过以下递归函数来实现：


void inorderTraversal(Node* root) {
  if (root == nullptr)
    return;
  
  inorderTraversal(root->left);
  cout << root->val << " ";
  inorderTraversal(root->right);
}

后序遍历是指先访问左右子节点，最后访问根节点的顺序，我们可以通过以下递归函数来实现：


void postorderTraversal(Node* root) {
  if (root == nullptr)
    return;
  
  postorderTraversal(root->left);
  postorderTraversal(root->right);
  cout << root->val << " ";
}

除此之外，还有一种层序遍历的方法，它是按照行的顺序一层一层地访问节点和子节点。我们可以使用队列来实现。


void levelOrderTraversal(Node* root) {
  if (root == nullptr)
    return;
  
  queue<Node*> q{{root}};
  while (!q.empty()) {
    Node* cur = q.front();
    q.pop();
    cout << cur->val << " ";
    if (cur->left != nullptr) {
      q.push(cur->left);
    }
    if (cur->right != nullptr) {
      q.push(cur->right);
    }
  }
}

通过以上代码和解释，我们可以实现树的构建和遍历。在实际应用中，树的结构和遍历方法都是非常有用的，了解和熟悉它们可以加深我们对数据结构和算法的理解。

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

下一篇: C++编程：输出1!～10!

评论区

()

相似文章