树的构造与遍历

在C++中构造和遍历树形结构通常涉及定义树的节点结构、创建树的实例以及实现遍历算法。

下面是一些基本步骤和示例代码：

1. 定义树节点

首先，你需要定义一个树节点（Node）结构，通常包含数据和指向子节点的指针。

struct TreeNode {
    int value; // 节点存储的数据
    TreeNode *left; // 指向左子节点的指针
    TreeNode *right; // 指向右子节点的指针

    // 构造函数，初始化节点
    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

2. 构造树

接下来，你可以创建树的实例，这通常涉及到动态分配内存来创建节点，并根据需要将它们连接起来。

// 创建一个示例树
//       1
//      / \
//     2   3
//    / \
//   4   5
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);

3. 遍历树

树的遍历是树算法中的一个重要部分，常见的遍历方式有前序遍历、中序遍历、后序遍历和层序遍历。

前序遍历（Pre-order Traversal）

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

void preOrder(TreeNode* node) {
    if (node == nullptr) return;
    std::cout << node->value << " "; // 访问当前节点
    preOrder(node->left); // 遍历左子树
    preOrder(node->right); // 遍历右子树
}

中序遍历（In-order Traversal）

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

void inOrder(TreeNode* node) {
    if (node == nullptr) return;
    inOrder(node->left); // 遍历左子树
    std::cout << node->value << " "; // 访问当前节点
    inOrder(node->right); // 遍历右子树
}

后序遍历（Post-order Traversal）

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

void postOrder(TreeNode* node) {
    if (node == nullptr) return;
    postOrder(node->left); // 遍历左子树
    postOrder(node->right); // 遍历右子树
    std::cout << node->value << " "; // 访问当前节点
}

层序遍历（Level-order Traversal）

层序遍历使用队列来实现，按照从上到下的顺序访问树的每一层。

#include <queue>

void levelOrder(TreeNode* root) {
    if (root == nullptr) return;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        std::cout << node->value << " ";
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

4. 清理内存

使用new创建的节点需要使用delete来释放内存，以避免内存泄漏。

// 递归删除树的所有节点
void deleteTree(TreeNode* node) {
    if (node) {
        deleteTree(node->left);
        deleteTree(node->right);
        delete node;
    }
}

// 使用示例
deleteTree(root);

这些是C++中构造和遍历树的基本方法。

(责任编辑：admin)

热门: