21xrx.com
2025-07-13 10:54:10 Sunday
登录
文章检索 我的文章 写文章
C++树的构建和遍历
2023-06-22 15:11:35 深夜i     15     0
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);
    }
  }
}

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

  
  

评论区