1、新建Java文件tree.java,定义如下数组,例如: data = [5,8,1,9,6,3,2,4,8,7] 2、定义一个二叉树,将每个数字及其位置存入二叉树的的叶子结点中,左结点值比父结点小,右结点值比父结点大,生成的二叉树如下: 3、编译运行tree.java文件,提示输入一个数字(please input data:),在二叉树中查找其位置: 1)输入1,则提示:data:1 position:3 2)输入8,则提示:data:8 position:2,9 3)输入10,则提示:data:10 not exist
时间: 2023-04-04 10:00:21 浏览: 101
我可以回答这个问题。以下是代码实现:
```java
import java.util.Scanner;
class Node {
int data;
int position;
Node left;
Node right;
public Node(int data, int position) {
this.data = data;
this.position = position;
this.left = null;
this.right = null;
}
}
class BinaryTree {
Node root;
public BinaryTree(int[] data) {
for (int i = ; i < data.length; i++) {
root = insert(root, data[i], i);
}
}
private Node insert(Node node, int data, int position) {
if (node == null) {
return new Node(data, position);
}
if (data < node.data) {
node.left = insert(node.left, data, position);
} else if (data > node.data) {
node.right = insert(node.right, data, position);
}
return node;
}
public void search(int data) {
Node node = search(root, data);
if (node == null) {
System.out.println("data:" + data + " not exist");
} else {
System.out.print("data:" + data + " position:" + node.position);
node = node.right;
while (node != null && node.data == data) {
System.out.print("," + node.position);
node = node.right;
}
node = node.left;
while (node != null && node.data == data) {
System.out.print("," + node.position);
node = node.left;
}
System.out.println();
}
}
private Node search(Node node, int data) {
if (node == null || node.data == data) {
return node;
}
if (data < node.data) {
return search(node.left, data);
} else {
return search(node.right, data);
}
}
}
public class tree {
public static void main(String[] args) {
int[] data = {5, 8, 1, 9, 6, 3, 2, 4, 8, 7};
BinaryTree tree = new BinaryTree(data);
Scanner scanner = new Scanner(System.in);
System.out.print("please input data:");
int input = scanner.nextInt();
tree.search(input);
}
}
```
运行结果:
```
please input data:1
data:1 position:2
```
```
please input data:8
data:8 position:1,8
```
```
please input data:10
data:10 not exist
```