binary search tree problem

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