Бинарное дерево поиска организовано в соответствии со структурой бинарного дерева. Такое дерево может быть представлено структурой связанного списка, где каждый узел является объектом. Помимо данных, узел также включает поля left, right и p, которые указывают на левого и правого сына узла соответственно. Если узел не существует, он равен NULL.
Это либо пустое дерево, либо двоичное дерево со следующими свойствами:
1) Если левое поддерево не пусто, то значения всех узлов левого поддерева меньше значения его корневого узла;
(2) Если правое поддерево не пусто, то значения всех узлов правого поддерева больше значения его корневого узла;
(3) Левое и правое поддеревья также являются деревьями двоичного поиска соответственно;
Очевидно, что вышеуказанные свойства удовлетворяются, тогда обход двоичного дерева поиска по порядку означает обход в порядке от меньшего к большему, поэтому оно называется деревом сортировки. Конечно, приведенные выше значения «меньше» и «больше» можно изменить в соответствии с вашими предпочтениями. собственные потребности.
Несколько распространенных операций с двоичными деревьями поиска: поиск, удаление и вставка.
ХДУ 3791:
Описание проблемы
Определите, являются ли две последовательности одной и той же последовательностью двоичного дерева поиска.
Вход
Начните с числа n. (1<=n<=20) означает, что необходимо оценить n чисел, и ввод заканчивается, когда n= 0.
Следующая строка представляет собой последовательность. Длина последовательности меньше 10 и содержит числа (0~9). На основе этой последовательности можно построить двоичное дерево поиска.
В следующих n строках содержится n последовательностей. Формат каждой последовательности такой же, как и у первой последовательности. Определите, могут ли эти две последовательности образовывать одно и то же двоичное дерево поиска.
Выход
Если последовательности одинаковы, выведите YES, в противном случае выведите NO.
Пример ввода
2
567432
543267
576342
0
Пример вывода
ДА
НЕТ
Объяснение: После вставки чисел по порядку используйте обход предварительного порядка двоичного дерева, чтобы определить, одинаковы ли два двоичных дерева.
Java-код
Скопируйте код кода следующим образом:
импортировать java.util.Scanner;
общественный класс Main{
public static void main(String args[]){
Сканер in=новый сканер(System.in);
BinarySearchTree<Character> root = null;
в то время как (in.hasNext ()) {
интервал т=in.nextInt();
если (т == 0) перерыв;
root = новый BinarySearchTree<Character>();
Строковый результат = ноль;
Строка result1 = ноль;
Строка s=in.next();
for(int i=0;i<s.length();i++){
root.insert(s.charAt(i));
}
результат = root.printTree(root.getRoot());
for(int i=0;i<t;i++){
root = новый BinarySearchTree<Character>();
s=in.next();
for(int j=0;j<s.length();j++){
root.insert(s.charAt(j));
}
result1 = root.printTree(root.getRoot());
if(result.equals(result1)) System.out.println("ДА");
еще System.out.println("НЕТ");
}
}
}
}
class BinaryNode< T расширяет Comparable<T>> {//узел дерева двоичного поиска
BinaryNode<T> слева;
BinaryNode<T> правильно;
Т-элемент;
public BinaryNode(T theElement){
это (Элемент, ноль, ноль);
}
public BinaryNode (T theElement, BinaryNode lt, BinaryNode rt) {
элемент = Элемент;
слева = <
право = рт;
}
общественный T getElement() {
вернуть этот.элемент;
}
общественный BinaryNode<T> getLeft(){
верните это.лево;
}
общественный BinaryNode<T> getRight(){
верните это.право;
}
публичная строка toString(){
возвращаемый элемент + "";
}
}
class BinarySearchTree< T расширяет Comparable<T>>{//Двоичное дерево поиска
частный BinaryNode<T> root;//корневой узел
общедоступный BinarySearchTree(){//Конструктор
корень = ноль;
}
public BinarySearchTree(BinaryNode< T> t){//Конструктор
корень = т;
}
общественная недействительность makeEmpty () {
корень = ноль;
}
общедоступное логическое значение isEmpty(){
вернуть корень == ноль;
}
общественный BinaryNode<T> getRoot(){
вернуть корень;
}
общественный T найти (T x) {
вернуть find(x, root).element;
}
общественная недействительная вставка (T x) {
корень = вставить (х, корень);
}
общественная недействительность printTree () {
printTree (корень);
}
частный BinaryNode< T> find(T x, BinaryNode< T> t){//Операция поиска
если (т == ноль) {
вернуть ноль;
}
если (x.compareTo (t.element) <0) {
вернуть find(x, t.left);
}
иначе если(x.compareTo(t.element) == 0){
вернуть т;
}
еще{
вернуть find(x, t.right);
}
}
частный BinaryNode< T> Insert(T x, BinaryNode< T> t){//Операция вставки
если (т == ноль) {
t = новый BinaryNode<T>(x, null, null);
}
иначе, если(x.compareTo(t.element) <0){
т.левый = вставить (х, т.левый);
}
иначе if(x.compareTo(t.element) > 0){
т.справа = вставить(х, т.справа);
}
еще;
вернуть т;
}
частный StringBuffer sb = новый StringBuffer ();
public String printTree(BinaryNode< T> t){//Предварительный обход двоичного дерева поиска
если (т! = ноль) {
sb.append(t.element);
printTree(t.left);
printTree(t.right);
}
вернуть sb.toString();
}
}
