给我一段用c++实现二叉树寻找父亲节点的代码
时间: 2024-05-20 11:15:50 浏览: 12
以下是用C语言实现寻找二叉树父节点的代码示例:
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* getParent(struct TreeNode* root, struct TreeNode* child) {
if (root == NULL || root == child) {
return NULL; // 找到根节点或子节点为空,退出
}
if (root->left == child || root->right == child) {
return root; // 找到目标节点,返回父节点
} else {
struct TreeNode* parent = getParent(root->left, child);
if (parent == NULL) { // 如果在左子树找不到,递归右子树
parent = getParent(root->right, child);
}
return parent; // 返回找到的父节点
}
}
这个函数接收一个二叉树的根节点和一个子节点,返回该节点的父节点。如果无法找到父节点或输入的节点为空,返回NULL。注意要在程序中释放分配的内存,以避免内存泄漏问题。
相关问题
帮我用c++写一段求二叉树深度的代码
以下为使用C语言实现求二叉树深度的代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int maxDepth(struct TreeNode* root) {
if (root == NULL) {
return 0;
} else {
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
}
int main() {
// 构造一个二叉树
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = 1;
struct TreeNode* node2 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node2->val = 2;
struct TreeNode* node3 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node3->val = 3;
struct TreeNode* node4 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node4->val = 4;
struct TreeNode* node5 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node5->val = 5;
root->left = node2;
root->right = node3;
node2->left = node4;
node2->right = NULL;
node3->left = NULL;
node3->right = node5;
node4->left = NULL;
node4->right = NULL;
node5->left = NULL;
node5->right = NULL;
// 求二叉树深度
int depth = maxDepth(root);
printf("The depth of the binary tree is: %d\n", depth);
// 释放内存
free(node5);
free(node4);
free(node3);
free(node2);
free(root);
return 0;
}
```
这里我们构造了一个二叉树,并使用`maxDepth`函数求出了其深度。其中,`maxDepth`函数采用递归的方式实现,对于每一个节点,我们分别计算其左子树和右子树的深度,并取两者中的较大值,最后加上1即为该节点所在子树的深度。如果该节点为空,则返回0。最终,整棵树的深度即为根节点的深度。
帮我写一段二叉树算法C++代码
好的,下面是一个简单的二叉树遍历算法的C++代码:
```c++
#include <iostream>
using namespace std;
// 二叉树节点结构
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int data) {
this->data = data;
left = nullptr;
right = nullptr;
}
};
// 二叉树遍历函数
void traverse(TreeNode* node) {
if (node == nullptr) {
return;
}
traverse(node->left);
traverse(node->right);
cout << node->data << " ";
}
int main() {
// 构建一个二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
// 遍历二叉树
cout << "二叉树遍历结果: ";
traverse(root);
return 0;
}
```
这个程序创建了一个二叉树,并使用递归函数`traverse()`遍历二叉树。这里使用的是后序遍历算法,即先遍历左子树,再遍历右子树,最后访问根节点。