C++中樹節(jié)點(diǎn)的遞歸與非遞歸遍歷

在C++中，樹節(jié)點(diǎn)的遞歸和非遞歸遍歷是常見的操作，可以通過不同的方法來實(shí)現(xiàn)。

遞歸遍歷樹節(jié)點(diǎn)可以使用深度優(yōu)先搜索（DFS）的方法，通常使用遞歸函數(shù)來實(shí)現(xiàn)。例如，對于二叉樹的前序遍歷，可以按照“根-左-右”的順序進(jìn)行遍歷，代碼示例如下：

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

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

非遞歸遍歷樹節(jié)點(diǎn)通常需要借助?；蜿?duì)列來實(shí)現(xiàn)。例如，對于二叉樹的前序遍歷，可以使用一個棧來模擬遞歸調(diào)用的過程，代碼示例如下：

void preorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    
    stack<TreeNode*> st;
    st.push(root);
    
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        cout << node->val << " ";
        
        if (node->right) {
            st.push(node->right);
        }
        if (node->left) {
            st.push(node->left);
        }
    }
}

以上是前序遍歷的實(shí)現(xiàn)，其他遍歷方式（中序遍歷、后序遍歷）也可以通過類似的方式來實(shí)現(xiàn)。

總的來說，遞歸遍歷樹節(jié)點(diǎn)簡單直觀，但可能會面臨棧溢出的風(fēng)險(xiǎn)；非遞歸遍歷相對復(fù)雜，但效率更高，適合大規(guī)模數(shù)據(jù)。在實(shí)際應(yīng)用中，可以根據(jù)具體情況選擇合適的遍歷方法。