C语言用设计算法判断结点E是否为结点E1和E2的共同祖先。
时间: 2024-06-13 21:08:17 浏览: 10
以下是C语言的算法,用于判断结点E是否为结点E1和E2的共同祖先:
```
// 定义二叉树结构体
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 判断结点E是否为结点E1和E2的共同祖先
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
if (root == NULL || root == p || root == q) {
return root;
}
struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
struct TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left == NULL) {
return right;
} else if (right == NULL) {
return left;
} else {
return root;
}
}
```
相关问题
C语言用二叉树设计算法判断结点E是否为结点E1和E2的共同祖先。
以下是C语言用二叉树设计算法判断结点E是否为结点E1和E2的共同祖的步骤:
1. 定义二叉树结构体,包含左右子树指针和节点值等信息。
2. 定义一个函数,输入参数为二叉树的根节点指针、两个节点E1和E2的指针,输出参数为节点E1和E2的共同祖先节点指针。
3. 在函数中,首先判断根节点是否为空或者等于E1或E2,如果是则返回根节点。
4. 递归遍历左右子树,分别查找E1和E2的位置。
5. 如果E1和E2分别在左右子树中,则返回根节点。
6. 如果E1和E2都在左子树中,则递归遍历左子树。
7. 如果E1和E2都在右子树中,则递归遍历右子树。
以下是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL || root == p || root == q) {
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != NULL && right != NULL) {
return root;
} else if (left != NULL) {
return left;
} else {
return right;
}
}
int main() {
// 创建二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->left->val = 4;
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right->val = 5;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->val = 6;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 7;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 查找共同祖先
TreeNode* p = root->left->left;
TreeNode* q = root->left->right;
TreeNode* ancestor = lowestCommonAncestor(root, p, q);
printf("The lowest common ancestor of %d and %d is %d.\n", p->val, q->val, ancestor->val);
return 0;
}
```
c语言 判断当前结点是否为头结点
在C语言中,数据结构中的头结点通常是指链表的第一个节点,可以用来引导整个链表的操作。判断当前节点是否为头结点,我们需要考虑链表的结构以及节点的指针关系。
通常情况下,链表的头结点会被定义为一个指向链表第一个节点的指针。因此,我们可以通过比较当前节点的指针和头结点指针的值来判断当前节点是否为头结点。
具体操作如下:
1. 首先,我们需要定义一个链表节点的结构体,其中包含数据域和指针域。
```c
typedef struct Node {
int data;
struct Node* next;
} Node;
```
2. 定义链表头结点的指针变量,通常命名为`head`。
```c
Node* head = NULL;
```
3. 假设我们要判断的节点为`currentNode`,通过比较其指针和头结点指针的值来判断是否为头结点。
```c
if (currentNode == head) {
printf("当前节点为头结点\n");
} else {
printf("当前节点不是头结点\n");
}
```
通过以上代码,我们可以根据当前节点的指针是否等于头结点的指针来判断当前节点是否为头结点。值得注意的是,在实际应用中,我们需要根据具体的链表结构和操作需求来判断当前节点是否为头结点。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)