设计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是二叉树的节点数。