Java代码实现在一颗三叉链表表示的二叉树中计算二叉树的深度
时间: 2024-01-23 12:15:12 浏览: 32
以下是Java代码实现在一颗三叉链表表示的二叉树中计算二叉树的深度:
```java
public class BinaryTreeDepth {
// 三叉链表二叉树节点类
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode parent;
TreeNode(int val) {
this.val = val;
}
}
// 计算二叉树深度的方法
public int getDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
```
在上面的代码中,我们使用了递归方法计算二叉树的深度。对于每个节点,我们计算其左右子树的深度,然后取较大值加1作为该节点所在子树的深度。最终,我们得到的结果就是整个二叉树的深度。
相关问题
Java代码实现在一颗三叉链表表示的二叉树中删除二叉树中的一个结点
以下是Java代码实现在一颗三叉链表表示的二叉树中删除二叉树中的一个结点的示例:
```java
public class ThreeLinkBinaryTree {
private TreeNode root;
public class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode parent;
public TreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
this.parent = null;
}
}
public ThreeLinkBinaryTree() {
root = null;
}
public void insert(int data) {
TreeNode newNode = new TreeNode(data);
if (root == null) {
root = newNode;
} else {
TreeNode current = root;
while (true) {
if (data < current.data) {
if (current.left == null) {
current.left = newNode;
newNode.parent = current;
break;
} else {
current = current.left;
}
} else {
if (current.right == null) {
current.right = newNode;
newNode.parent = current;
break;
} else {
current = current.right;
}
}
}
}
}
public boolean delete(int data) {
TreeNode current = findNode(data);
if (current == null) {
return false;
}
if (current.right == null) {
transplant(current, current.left);
} else if (current.left == null) {
transplant(current, current.right);
} else {
TreeNode successor = minimum(current.right);
if (successor.parent != current) {
transplant(successor, successor.right);
successor.right = current.right;
successor.right.parent = successor;
}
transplant(current, successor);
successor.left = current.left;
successor.left.parent = successor;
}
return true;
}
private TreeNode findNode(int data) {
TreeNode current = root;
while (current != null && current.data != data) {
if (data < current.data) {
current = current.left;
} else {
current = current.right;
}
}
return current;
}
private void transplant(TreeNode u, TreeNode v) {
if (u.parent == null) {
root = v;
} else if (u == u.parent.left) {
u.parent.left = v;
} else {
u.parent.right = v;
}
if (v != null) {
v.parent = u.parent;
}
}
private TreeNode minimum(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
}
```
在上述代码中,我们通过 `findNode` 方法来查找需要删除的节点。如果需要删除的节点没有左孩子或右孩子,我们可以直接用它的左孩子或右孩子来替换它。如果需要删除的节点有左孩子和右孩子,我们需要找到它的后继节点,并用后继节点来替换它。然后,我们将需要删除的节点的左子树和右子树连接到后继节点上。最后,我们要注意更新它们的父节点关系。
需要注意的是,在这个三叉链表表示的二叉树中,每个节点都有一个指向其父节点的指针,这样我们就可以方便地进行删除操作。
Java代码实现在一颗三叉链表表示的二叉树中返回指定结点的父母结点
以下是Java代码实现:
```java
public class TriTreeNode {
int data;
TriTreeNode left;
TriTreeNode right;
TriTreeNode parent;
// constructor
public TriTreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
this.parent = null;
}
}
public class TriTree {
TriTreeNode root;
// constructor
public TriTree() {
root = null;
}
// method to find the parent node of a given node
public TriTreeNode findParent(TriTreeNode node) {
if (node == null || node == root) {
return null;
} else {
return node.parent;
}
}
}
```
这里定义了两个类:TriTreeNode表示三叉链表中的结点,TriTree表示三叉链表。在TriTreeNode中,除了data、left和right,还有一个parent表示父结点。在TriTree中,定义了一个方法findParent,接受一个TriTreeNode参数,返回该结点的父结点。如果该结点为空或者是根结点,返回null。否则,返回该结点的父结点。