C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）

下面是关于C++二叉树数据结构的详细攻略。

什么是二叉树

二叉树是一种树形数据结构，每个节点最多有两个子节点：左节点和右节点。一个节点没有左节点或右节点则分别为左子树和右子树为空。

递归遍历二叉树

前序遍历

前序遍历是指对于一棵二叉树，在访问右子树之前，先访问根节点，然后访问左子树。

下面是C++递归遍历二叉树的前序遍历示例代码：

template <typename T>
void preorderTraversal(TreeNode<T>* root) {
    if (!root) return;
    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

中序遍历

中序遍历是指对于一棵二叉树，先访问其左子树，再访问根节点，最后访问右子树。

下面是C++递归遍历二叉树的中序遍历示例代码：

template <typename T>
void inorderTraversal(TreeNode<T>* root) {
    if (!root) return;
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

后序遍历

后序遍历是指对于一棵二叉树，先访问其左子树和右子树，最后访问根节点。

下面是C++递归遍历二叉树的后序遍历示例代码：

template <typename T>
void postorderTraversal(TreeNode<T>* root) {
    if (!root) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->val << " ";
}

非递归遍历二叉树

递归遍历二叉树的缺点是可能由于函数调用过多导致内存溢出，而非递归遍历避免了这种问题。

前序遍历

前序遍历的非递归方法需要使用栈，将当前节点压入栈中，然后将其右子节点和左子节点分别压入栈中，这样每次弹出栈顶节点时就是先访问其左子节点，然后访问右子节点。

下面是C++非递归遍历二叉树的前序遍历示例代码：

template <typename T>
void preorderTraversal2(TreeNode<T>* root) {
    if (!root) return;
    stack<TreeNode<T>*> s;
    s.push(root);
    while (!s.empty()) {
        auto node = s.top();
        s.pop();
        cout << node->val << " ";
        if (node->right) s.push(node->right);
        if (node->left) s.push(node->left);
    }
}

中序遍历

中序遍历的非递归方法也需要使用栈，将根节点和其左子节点一直压入栈中，直至最左边的叶子节点；然后弹出当前节点并访问，再将当前节点的右子节点压入栈中，继续执行上述过程。

下面是C++非递归遍历二叉树的中序遍历示例代码：

template <typename T>
void inorderTraversal2(TreeNode<T>* root) {
    if (!root) return;
    stack<TreeNode<T>*> s;
    auto node = root;
    while (node || !s.empty()) {
        while (node) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        s.pop();
        cout << node->val << " ";
        node = node->right;
    }
}

后序遍历

后序遍历的非递归方法较为复杂，需要使用两个栈，其中一个栈用来保存经过中右左遍历的结果，另一个栈则用来保存中右左遍历的顺序。

下面是C++非递归遍历二叉树的后序遍历示例代码：

template <typename T>
void postorderTraversal2(TreeNode<T>* root) {
    if (!root) return;
    stack<TreeNode<T>*> s1, s2;
    s1.push(root);
    while (!s1.empty()) {
        auto node = s1.top();
        s1.pop();
        s2.push(node);
        if (node->left) s1.push(node->left);
        if (node->right) s1.push(node->right);
    }
    while (!s2.empty()) {
        auto node = s2.top();
        s2.pop();
        cout << node->val << " ";
    }
}

以上就是C++二叉树数据结构的完整攻略，希望对你有所帮助。