当前位置:网站首页>binary search tree problem
binary search tree problem
2022-08-05 07:04:00 【Chengqiuming】
An original problem description
Binary Search Tree - HDU 3791 - Virtual Judgehttps://vjudge.net/problem/HDU-3791
Two Inputs and Outputs
1 input
Start a number n, (1<=n<=20) means that there are n numbers to be judged, and the input ends when n=0.
The next line is a sequence, the length of the sequence is less than 10, contains numbers (0~9), and there are no repeated numbers. According to this sequence, a binary search tree can be constructed.
There are n sequences in the next n lines. The format of each sequence is the same as the first sequence. Please judge whether the two sequences can form the same binary search tree.
2 output
If the sequence is the same, output YES, otherwise output NO
Three input and output samples
1 Input example
2
567432
543267
576342
0
2 Sample output
YES
NO
Three Analysis
Inorder traversal and preorder traversal of a tree can uniquely determine a binary tree.Therefore, a binary search tree can be constructed first. At this time, the in-order traversal is the same. If the pre-order traversal is the same, it is the same binary search tree.
Four Algorithms Design
1 Using a binary search tree, first store each number in the binary search tree to get a preorder traversal.
2 Store each number in the following line into the binary search tree, get pre-order traversal, compare whether they are equal, if they are equal, output "YES", otherwise output "NO".
Five codes
package hdu3791;import java.util.Scanner;public class HDU3791 {static int cnt;static String a; // input stringstatic char b[] = new char[15]; // original sequence preorder sequencestatic char c[] = new char[15]; // preorder sequence for other sequencesstatic Node root;static Node insert(Node root, int num) { //Insert x into binary search tree tif (root == null) {// if the tree is emptyreturn new Node(num);}// A temporary node points to the root node for the return valueNode tmp = root;Node pre = root;while (root != null && root.num != num) {// save the parent nodepre = root;if (num > root.num) {root = root.rc;} else {root = root.lc;}}// add via parent nodeif (num > pre.num) {pre.rc = new Node(num);} else {pre.lc = new Node(num);}return tmp;}static void preorder(Node t, char b[]) {//Inorder traversalif (t != null) {b[cnt++] = (char) (t.num + '0');preorder(t.lc, b);preorder(t.rc, b);}}public static void main(String[] args) {int n;Scanner scanner = new Scanner(System.in);while (true) {n = scanner.nextInt();if (n == 0) {return;}cnt = 0;root = null;a = scanner.next();for (int i = 0; i < a.length(); i++)root = insert(root, a.charAt(i) - '0');preorder(root, b);b[cnt] = '\0';while (n--> 0) {cnt = 0;root = null;a = scanner.next();for (int i = 0; i < a.length(); i++)root = insert(root, a.charAt(i) - '0');preorder(root, c);c[cnt] = '\0';String sb = new String(b);String sc = new String(c);if (sb.equals(sc))System.out.println("YES");elseSystem.out.println("NO");}}}}class Node {int num;Node lc;Node rc;Node(int num) {this.num = num;}}
Six Tests
边栏推荐
猜你喜欢
随机推荐
【MyCat简单介绍】
export使用
《基于R语言的自动数据收集》--第3章 XML和JSON
MySQL:连接查询 | 内连接,外连接
如何将.asd恢复为Word文档
360度反馈调查表中的问题示范
Day9 of Hegong Daqiong team vision team training - camera calibration
TCP的粘包拆包问题+解决方案
给网站套上Cloudflare(以腾讯云为例)
Promise (三) async/await
矩阵的构造
Kioxia and Aerospike Collaborate to Improve Database Application Performance
LaTeX uses frame to make PPT pictures without labels
概率与期望部分题解
女生做软件测试会不会成为一个趋势?
lingo入门——河北省第三届研究生建模竞赛B题
盒子模型小练习
h5页面回退到微信小程序并携带参数
Mysql主从延迟的原因和解决方案
golang-条件语句