数据结构与算法C语言第三版二叉树求结点祖先

二叉树求结点祖先需要考虑两种情况：一是当前节点为目标节点，此时不需要继续递归向下寻找祖先；二是当前节点不是目标节点，则需要递归向下继续查找祖先。

以下是一个简单的C语言程序，可以求出二叉树中任意一个节点的所有祖先：

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

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

// 递归函数，用于查找节点的祖先
int findAncestors(TreeNode *root, int target) {
    if (root == NULL) {  // 如果节点为空，直接返回0
        return 0;
    }
    if (root->val == target) {  // 如果找到目标节点，返回1
        return 1;
    }
    // 向左子树递归查找
    if (findAncestors(root->left, target) || findAncestors(root->right, target)) {
        printf("%d ", root->val);  // 打印祖先节点
        return 1;
    }
    return 0;
}

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 = NULL;

    // 查找节点4的祖先
    int target = 4;
    printf("The ancestors of %d are: ", target);
    findAncestors(root, target);
    printf("\n");

    return 0;
}

在上面的程序中，我们使用了递归的方式查找节点的祖先。如果当前节点为空，直接返回0；如果当前节点为目标节点，返回1。如果当前节点不是目标节点，则需要继续向下递归查找。如果在左子树或右子树中找到了目标节点，说明当前节点是目标节点的祖先节点，打印出来，并返回1。如果左右子树都没有找到目标节点，则返回0。通过不断递归，可以查找到目标节点的所有祖先节点。