解题思路:
思路类似二分查找吧,就是把数据存储形式换成了二叉树,将比父节点小的值插入左子树,比父节点大的值插入右子树,将全部数据插入完成后即可开始查找,比父节点小的值就去左子树上查找,比父节点大的值就去右子树查找,如果查找到叶子节点仍没有查找成功便是查找失败。
注意事项:
就是插入的时候建立的新节点要与父节点连接上,我是用返回值的方式连接的,c语言可以通过指针间接访问父节点并将父节点的指针域指向新建立的节点。由于我没将二叉查找树转化为二叉平衡树,思路并不复杂,没什么其他的注意事项了。
参考代码:
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int k = scanner.nextInt(); //以输入的第一个值创建根节点root Node root = new Node(scanner.nextInt()); //将剩下的n-1个输入值插入树中 for (int i = 1; i < n; i++) { root = root.put(root, scanner.nextInt()); } //k次循环以查找k个值,查找成功则输出1,查找失败则输出0 for (int i = 0; i < k; i++) { if (root.searchNode(root, scanner.nextInt())) { System.out.print("1 "); }else { System.out.print("0 "); } } System.out.println(); } } //树的节点实现类 class Node{ public int value;//保存节点的值 public Node left;//保存节点的左儿子 public Node right;//保存节点的右儿子 public Node(int value) { this.value = value; } //插入节点 public Node put(Node node, int value) { //递归的终止条件,因为题中输入的值都是不相等的,故一定会递归到空节点上,此时创建一个节点 if (node == null) { return new Node(value); } //如果插入的值小于该节点的值,则递归到该节点的左子树上插入 if(value < node.value) { node.left = put(node.left, value); }else {//如果插入的值大于该节点的值,则递归到该节点的右子树上插入 node.right = put(node.right, value); } //将完成插入操作的节点返回 return node; } //查找值 public boolean searchNode(Node node, int value) { //如果节点为空则代表递归到叶子节点仍没有查找成功,故返回false表明查找失败 if (node == null) { return false; } //如果查找值小于节点值,则递归到左子树查找 if (value < node.value) { return searchNode(node.left, value); }else if (value > node.value) {//如果查找值大于节点值,则递归到右子树查找 return searchNode(node.right, value); }else{//如果查找值等于节点值,则查找成功 return true; } } }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:568 |
母牛的故事 (C语言代码)浏览:1298 |
程序员的表白 (C语言代码)浏览:655 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:1030 |
母牛的故事 (C语言代码)浏览:715 |
printf基础练习2 (C语言代码)浏览:617 |
1025题解浏览:732 |
A+B for Input-Output Practice (III) (C语言代码)浏览:564 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:398 |
出圈】指针malloc版浏览:355 |