如何用C++递归算法实现树的遍历-开发者知识库平台

如何用C++递归算法实现树的遍历

c++

889

2024/9/27 12:32:16

栏目: 编程语言

在C++中，使用递归算法实现树的遍历有三种主要方法：前序遍历（Pre-order Traversal）、中序遍历（In-order Traversal）和后序遍历（Post-order Traversal）。这里给出一个简单的二叉树结构以及相应的递归遍历实现。

首先，定义一个二叉树节点结构体：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

接下来，实现递归遍历：

前序遍历（Pre-order Traversal）：根节点 -> 左子树 -> 右子树

void preOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->val << " ";
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

中序遍历（In-order Traversal）：左子树 -> 根节点 -> 右子树

void inOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inOrderTraversal(root->left);
    cout << root->val << " ";
    inOrderTraversal(root->right);
}

后序遍历（Post-order Traversal）：左子树 -> 右子树 -> 根节点

void postOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    cout << root->val << " ";
}

以上代码中，我们使用了递归的方式实现了二叉树的前序、中序和后序遍历。在主函数中，可以创建一个二叉树并调用相应的遍历函数进行测试。

辰迅云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>

如何用C++递归算法实现树的遍历

最新知识库

相关标签