java二叉树寻找父节点
时间: 2023-10-14 14:32:07 浏览: 59
可以通过在二叉树中进行遍历来寻找某个节点的父节点。具体步骤如下:
1. 从根节点开始遍历二叉树,如果当前节点为null,则返回null。
2. 如果当前节点的左子节点或右子节点为目标节点,则当前节点就是目标节点的父节点,返回当前节点。
3. 如果目标节点不在当前节点的左右子树中,则分别递归遍历当前节点的左右子树,直到找到目标节点或遍历完整个树。
以下是Java代码实现:
```java
public TreeNode findParent(TreeNode root, TreeNode target) {
if (root == null || root == target) {
return null;
}
if (root.left == target || root.right == target) {
return root;
}
TreeNode left = findParent(root.left, target);
if (left != null) {
return left;
}
return findParent(root.right, target);
}
```
其中,TreeNode代表二叉树的节点对象,包含一个值和左右子节点。
相关问题
java二叉树寻找兄弟结点
要寻找二叉树中某个结点的兄弟结点,需要先找到该结点的父节点,然后再找到父节点的另一个子结点即可。
实现代码如下:
```java
public TreeNode findSibling(TreeNode root, TreeNode node) {
if (root == null || node == null || root == node) {
return null;
}
TreeNode parent = getParent(root, node);
if (parent == null) {
return null;
}
if (parent.left == node) {
return parent.right;
} else {
return parent.left;
}
}
private TreeNode getParent(TreeNode root, TreeNode node) {
if (root == null || root == node) {
return null;
}
if (root.left == node || root.right == node) {
return root;
}
TreeNode parent = getParent(root.left, node);
if (parent != null) {
return parent;
}
return getParent(root.right, node);
}
```
其中,`findSibling` 方法接受二叉树的根结点和目标结点作为参数,返回目标结点的兄弟结点。该方法先调用 `getParent` 方法找到目标结点的父节点,然后根据父节点的左右子结点来找到目标结点的兄弟结点。
`getParent` 方法用于找到目标结点的父节点。该方法递归地从根结点开始向下遍历二叉树,直到找到目标结点的父节点为止。如果没有找到父节点,返回 `null`。
java定义二叉树链式存储节点类
以下是Java定义二叉树链式存储节点类的示例:
```java
public class BinaryTreeNode {
private int data;
private BinaryTreeNode left;
private BinaryTreeNode right;
public BinaryTreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
public int getData() {
return data;
}
public void setData(int data {
this.data = data;
}
public BinaryTreeNode getLeft() {
return left;
}
public void setLeft(BinaryTreeNode left) {
this.left = left;
}
public BinaryTreeNode getRight() {
return right;
}
public void setRight(BinaryTreeNode right) {
this.right = right;
}
}
```