首页用C语言设计一个求结点x在二叉树中的双亲结点算法，表明注释

用C语言设计一个求结点x在二叉树中的双亲结点算法，表明注释

时间: 2025-02-12 15:26:26 浏览: 35

在C语言中，设计一个函数来查找二叉树中给定节点x的双亲结点，我们需要遍历整个二叉树直到找到目标节点或到达根节点（如果x就是根）。这里我们可以采用递归的方式来实现。下面是一个简单的示例： ```c #include <stdio.h> // 定义二叉树结点结构体 typedef struct TreeNode { int val; // 节点值 struct TreeNode *left; // 左子节点指针 struct TreeNode *right; // 右子节点指针 } TreeNode; // 求结点x在二叉树中的双亲结点 TreeNode* findParent(TreeNode* root, TreeNode* x) { if (root == NULL || root == x) { // 如果根为空，或找到了目标x，返回NULL（表示x是根） return NULL; } // 遍历左子树寻找x if (root->val > x->val) { return findParent(root->left, x); // 如果目标比当前节点小，继续在左子树搜索 } else { return root; // 否则，说明x在当前节点或其右子树中，直接返回当前节点（即x的父节点） } } // 示例：用于测试该函数 int main() { // 创建一个简单二叉树 TreeNode* tree = (TreeNode*)malloc(sizeof(TreeNode)); tree->val = 5; tree->left = (TreeNode*)malloc(sizeof(TreeNode)); tree->left->val = 3; tree->left->left = (TreeNode*)malloc(sizeof(TreeNode)); tree->left->left->val = 2; tree->right = (TreeNode*)malloc(sizeof(TreeNode)); tree->right->val = 7; tree->right->right = (TreeNode*)malloc(sizeof(TreeNode)); tree->right->right->val = 8; TreeNode* node = findParent(tree, tree->left); // 找到结点3的父节点5 printf("Parent of node %d is node %d\n", ((TreeNode*)node)->val, tree->val); return 0; } ```

阅读全文