c++逆序递归遍历单链表

逆序递归遍历单链表的算法如下：

1. 如果单链表为空，直接返回。
2. 递归遍历单链表的下一个节点。
3. 输出当前节点的值。

具体实现代码如下：

void reverse_print(Node* head) {
    if (head == NULL) {
        return;
    }
    reverse_print(head->next);
    printf("%d ", head->data);
}

其中，Node表示单链表的节点类型，包含data和next两个成员变量。reverse_print函数为逆序递归遍历单链表的函数，其参数为单链表的头节点指针。函数首先判断单链表是否为空，如果为空直接返回；否则，递归遍历单链表的下一个节点，然后输出当前节点的值。递归调用结束后，整个单链表就被逆序遍历了一遍。

相关问题

c++逆序输出二叉树

在C++中，可以使用递归和栈两种方法来逆序输出二叉树。其中，递归方法比较简单，可以通过后序遍历的方式实现。具体实现代码如下：

void reverse_PostOrder(BiTree T) {
    if(T != NULL) {
        reverse_PostOrder(T->lchild);
        reverse_PostOrder(T->rchild);
        cout << T->data << " ";
    }
}

另外一种方法是使用栈来实现。具体实现代码如下：

void reverse_PostOrder(BiTree T, SqStack &S) {
    if(T != NULL) {
        Push(S, T);
        reverse_PostOrder(T->rchild, S);
        reverse_PostOrder(T->lchild, S);
    }
}

void Print(BiTree T) {
    SqStack S;
    InitStack(S);
    reverse_PostOrder(T, S);
    while(!isEmpty(S)) {
        BiTree p;
        Pop(S, p);
        cout << p->data << " ";
    }
}

C++实现1.采用先序遍历方法输出所有从叶子结点到根结点的逆路径。2.采用先序遍历方法输出第一条最长的逆路径。3.采用后序非递归遍历方法输出所有从叶子结点到根节点的逆路径。4.采用层次遍历方法输出所有所有从叶子结点到根结点的逆路径。写出调试分析

以下是C++代码实现：

#include<iostream>
#include<stack>
#include<queue>
using namespace std;

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

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

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

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

void reversePath(TreeNode* root, stack<int>& path) {
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL) {
        path.push(root->val);
        while (!path.empty()) {
            cout << path.top() << " ";
            path.pop();
        }
        cout << endl;
        return;
    }
    path.push(root->val);
    reversePath(root->left, path);
    reversePath(root->right, path);
    path.pop();
}

void longestPath(TreeNode* root, stack<int>& path, stack<int>& longest) {
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL) {
        path.push(root->val);
        if (path.size() > longest.size()) {
            longest = path;
        }
        path.pop();
        return;
    }
    path.push(root->val);
    longestPath(root->left, path, longest);
    longestPath(root->right, path, longest);
    path.pop();
}

void reversePathNonRecursion(TreeNode* root) {
    if (root == NULL) return;
    stack<TreeNode*> s;
    TreeNode* cur = root;
    TreeNode* pre = NULL;
    while (cur || !s.empty()) {
        while (cur) {
            s.push(cur);
            cur = cur->left;
        }
        cur = s.top();
        if (cur->right == NULL || cur->right == pre) {
            if (cur->left == NULL && cur->right == NULL) {
                stack<int> path;
                while (!s.empty()) {
                    path.push(s.top()->val);
                    s.pop();
                }
                while (!path.empty()) {
                    cout << path.top() << " ";
                    path.pop();
                }
                cout << endl;
            }
            pre = cur;
            s.pop();
            cur = NULL;
        }
        else {
            cur = cur->right;
        }
    }
}

void reversePathLevelOrder(TreeNode* root) {
    if (root == NULL) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        if (cur->left == NULL && cur->right == NULL) {
            stack<int> path;
            while (cur != NULL) {
                path.push(cur->val);
                cur = cur->parent;
            }
            while (!path.empty()) {
                cout << path.top() << " ";
                path.pop();
            }
            cout << endl;
        }
        if (cur->right) {
            cur->right->parent = cur;
            q.push(cur->right);
        }
        if (cur->left) {
            cur->left->parent = cur;
            q.push(cur->left);
        }
    }
}

int main() {
    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);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    cout << "1.采用先序遍历方法输出所有从叶子结点到根结点的逆路径：" << endl;
    stack<int> path;
    reversePath(root, path);

    cout << "2.采用先序遍历方法输出第一条最长的逆路径：" << endl;
    stack<int> longest;
    longestPath(root, path, longest);
    while (!longest.empty()) {
        cout << longest.top() << " ";
        longest.pop();
    }
    cout << endl;

    cout << "3.采用后序非递归遍历方法输出所有从叶子结点到根节点的逆路径：" << endl;
    reversePathNonRecursion(root);

    cout << "4.采用层次遍历方法输出所有所有从叶子结点到根结点的逆路径：" << endl;
    reversePathLevelOrder(root);

    return 0;
}

调试分析：

上述代码中，我们定义了一个二叉树的结点结构体 `TreeNode`，其中包含一个整数值 `val`、左右子树指针 `left` 和 `right`，以及一个指向父结点的指针 `parent`（用于后续的层次遍历方法）。接下来，我们实现了先序、中序和后序遍历二叉树的函数 `preOrder`、`inOrder` 和 `postOrder`，以及逆路径相关的四个函数 `reversePath`、`longestPath`、`reversePathNonRecursion` 和 `reversePathLevelOrder`。

其中，`reversePath` 函数采用先序遍历方法，输出所有从叶子结点到根结点的逆路径，我们在遍历过程中使用一个栈 `path` 存储遍历路径，当遍历到叶子结点时，我们将 `path` 中的元素逆序输出即可。

`longestPath` 函数与 `reversePath` 函数类似，不同之处在于我们需要找到第一条最长的逆路径，因此我们需要在遍历过程中记录当前最长的路径 `longest`，每当遍历到一个叶子结点时，如果当前路径比 `longest` 更长，则更新 `longest`。

`reversePathNonRecursion` 函数采用后序非递归遍历方法，输出所有从叶子结点到根节点的逆路径。我们使用一个栈 `s` 存储遍历路径，每当遍历到一个结点时，如果它的左右子树都为空（即为叶子结点），则将 `s` 中的元素逆序输出即可。注意，我们在遍历过程中需要记录上一个遍历的结点 `pre`，每当遍历到一个结点时，如果它的右子树为空或者右子树已经被遍历过，那么就可以遍历当前结点了。

`reversePathLevelOrder` 函数采用层次遍历方法，输出所有从叶子结点到根结点的逆路径。我们使用一个队列 `q` 存储待遍历的结点，每当遍历到一个叶子结点时，我们可以使用 `parent` 指针从当前结点回溯到根结点，并将遍历路径存储到一个栈 `path` 中，最后将 `path` 中的元素逆序输出即可。注意，在遍历过程中需要为每个结点设置 `parent` 指针。