用c语言设计一个算法，返回二叉树T的先序序列的最后一个结点的指针

以下是用C语言设计的返回二叉树T的先序序列的最后一个结点的指针的算法：

typedef struct TreeNode{
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;

TreeNode* LastNode(TreeNode* T){
    if(T == NULL) return NULL;
    TreeNode* p = T;
    stack<TreeNode*> s;
    while(p != NULL || !s.empty()){
        while(p != NULL){
            printf("%d ",p->data); //先序遍历
            if(p->right != NULL) s.push(p->right); //右子树入栈
            p = p->left;
        }
        if(!s.empty()){
            p = s.top();
            s.pop();
        }
    }
    return p; //返回最后一个结点指针
}

该算法使用了先序遍历二叉树的方法，同时使用了栈来存储右子树，以便在遍历完左子树后能够访问右子树。最后返回的是最后一个访问的结点的指针。

相关问题

设计c语言算法实现设计一个非递归算法以输出二叉树t中先序序列中最后一个结点的值。

下面是一个非递归算法以输出二叉树t中先序序列中最后一个结点的值：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int lastNodeValue(TreeNode *root) {
    if (root == NULL) {
        return -1;
    }

    TreeNode *stack[100];
    int top = -1;
    TreeNode *p = root;
    TreeNode *pre = NULL;
    while (p || top >= 0) {
        if (p) {
            stack[++top] = p;
            p = p->left;
        } else {
            p = stack[top];
            if (p->right == NULL || p->right == pre) {
                if (top == 0) {
                    return p->val;
                } else {
                    pre = p;
                    top--;
                    p = NULL;
                }
            } else {
                p = p->right;
            }
        }
    }

    return -1;
}

int main() {
    // 构造二叉树
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->val = 1;
    root->left = (TreeNode *)malloc(sizeof(TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->val = 3;
    root->right->left = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->left->val = 4;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->right->val = 5;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    // 输出先序序列中最后一个结点的值
    int val = lastNodeValue(root);
    printf("%d\n", val);

    return 0;
}

代码思路是用栈来实现二叉树的非递归遍历，具体来说：

1. 初始化一个栈和一个指针p指向根节点。
2. 如果p非空，就将p入栈，并将p指向它的左子节点。
3. 如果p为空，就将栈顶元素弹出，并将p指向它的右子节点。
4. 如果p的右子节点为空或者已经被访问过，说明p是一个叶子节点，此时判断栈是否为空，如果为空，说明已经遍历完整棵树，直接返回p的值。如果栈不为空，说明p是某个节点的左子节点或者右子节点，需要将它弹出，然后将pre指针指向p，将p置为NULL，等待下一轮循环。

这种算法的时间复杂度是O(n)，其中n是二叉树的节点数。

用顺序存储结构来存储一颗具有n个结点的二叉树，用c语言编写算法实现对该二叉树进行先序遍历，输出先序遍历序列。

假设二叉树的结点结构体定义如下：

typedef struct TreeNode {
    char data;  // 结点存储的数据
    struct TreeNode* left;  // 左子结点指针
    struct TreeNode* right;  // 右子结点指针
} TreeNode;

则使用顺序存储结构来存储该二叉树的数组定义如下：

TreeNode* tree[MAX_SIZE];  // MAX_SIZE为数组的最大容量

其中数组下标为i的元素表示二叉树中第i个结点的指针，如果二叉树中只有n个结点，则数组中前n个元素是有效的，后面的元素可以不用管。

先序遍历的递归算法如下：

void preOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%c ", root->data);  // 输出当前结点的值
    preOrder(root->left);  // 递归遍历左子树
    preOrder(root->right);  // 递归遍历右子树
}

使用数组表示二叉树，只需要将root结点的下标设为0，左子结点的下标为2*i+1，右子结点的下标为2*i+2，则先序遍历的非递归算法如下：

void preOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    int stack[MAX_SIZE];  // 定义一个栈
    int top = -1;  // 栈顶指针
    stack[++top] = 0;  // 将root结点的下标入栈
    while (top >= 0) {
        int i = stack[top--];  // 弹出栈顶元素
        printf("%c ", tree[i]->data);  // 输出当前结点的值
        // 将右子结点的下标入栈，注意要先入栈右子结点
        if (tree[i]->right != NULL) {
            stack[++top] = 2*i+2;
        }
        // 将左子结点的下标入栈
        if (tree[i]->left != NULL) {
            stack[++top] = 2*i+1;
        }
    }
}