Java代码实现构造一颗三叉链表表示的二叉树,实现在二叉树中查找一个结点
时间: 2024-01-23 16:15:11 浏览: 28
以下是Java代码实现构造一颗三叉链表表示的二叉树,以及在二叉树中查找一个节点的示例代码:
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode parent;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
this.parent = null;
}
}
class BinaryTree {
private TreeNode root;
public BinaryTree() {
this.root = null;
}
public void insert(int val) {
TreeNode newNode = new TreeNode(val);
if (root == null) {
root = newNode;
} else {
TreeNode current = root;
TreeNode parent;
while (true) {
parent = current;
if (val < current.val) {
current = current.left;
if (current == null) {
parent.left = newNode;
newNode.parent = parent;
return;
}
} else {
current = current.right;
if (current == null) {
parent.right = newNode;
newNode.parent = parent;
return;
}
}
}
}
}
public TreeNode search(int val) {
TreeNode current = root;
while (current != null && current.val != val) {
if (val < current.val) {
current = current.left;
} else {
current = current.right;
}
}
return current;
}
}
```
在这段代码中,我们定义了一个`TreeNode`类,表示二叉树中的一个节点。节点包含了一个`val`属性,表示节点的值,以及`left`、`right`和`parent`属性,分别表示节点的左子节点、右子节点和父节点。我们还定义了一个`BinaryTree`类,表示三叉链表表示的二叉树。该类包含了一个`root`属性,表示二叉树的根节点。
在`BinaryTree`类中,我们实现了一个`insert`方法,用于向二叉树中插入一个节点。该方法的实现与普通的二叉树插入方法类似,只不过我们需要在插入节点时同时设置节点的父节点。我们还实现了一个`search`方法,用于在二叉树中查找一个节点。该方法的实现也与普通的二叉树查找方法类似。
以下是使用示例代码:
```java
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(1);
tree.insert(9);
TreeNode node = tree.search(7);
if (node != null) {
System.out.println("Found node: " + node.val);
} else {
System.out.println("Node not found.");
}
}
```
在这个示例中,我们创建了一颗二叉树,并向其中插入了一些节点。然后,我们调用`search`方法查找值为7的节点。如果找到了该节点,则输出节点的值;否则输出`Node not found.`。