Un árbol de búsqueda binario está organizado según la estructura del árbol binario. Un árbol de este tipo puede representarse mediante una estructura de lista vinculada, donde cada nodo es un objeto. Además de los datos, el nodo también incluye los campos izquierdo, derecho y p, que apuntan al hijo izquierdo y al hijo derecho del nodo respectivamente. Si el nodo no existe, es NULL.
Es un árbol vacío o un árbol binario con las siguientes propiedades:
1) Si el subárbol izquierdo no está vacío, entonces los valores de todos los nodos en el subárbol izquierdo son menores que el valor de su nodo raíz;
(2) Si el subárbol derecho no está vacío, entonces los valores de todos los nodos en el subárbol derecho son mayores que el valor de su nodo raíz;
(3) Los subárboles izquierdo y derecho también son árboles de búsqueda binarios respectivamente;
Obviamente, se satisfacen las propiedades anteriores, luego atravesar el árbol de búsqueda binaria en orden significa atravesar en orden de pequeño a grande, razón por la cual se llama árbol de clasificación. Por supuesto, el menor y mayor que anterior se puede cambiar de acuerdo con su. propias necesidades.
Varias operaciones comunes de los árboles de búsqueda binarios: buscar, eliminar e insertar.
HDU 3791:
Descripción del problema
Determinar si dos secuencias son la misma secuencia de árbol de búsqueda binaria
Aporte
Comience con un número n, (1 <= n <= 20) significa que hay n números que deben juzgarse y la entrada finaliza cuando n = 0.
La siguiente línea es una secuencia. La longitud de la secuencia es inferior a 10 y contiene números (0 ~ 9). No hay números repetidos en función de esta secuencia.
Hay n secuencias en las siguientes n líneas. El formato de cada secuencia es el mismo que el de la primera secuencia. Determine si estas dos secuencias pueden formar el mismo árbol de búsqueda binario.
Producción
Si las secuencias son las mismas, envíe SÍ; de lo contrario, envíe NO
Entrada de muestra
2
567432
543267
576342
0
Salida de muestra
SÍ
NO
Explicación: Después de insertar los números en orden, utilice el recorrido de pedido previo del árbol binario para determinar si los dos árboles binarios son iguales.
código java
Copie el código de código de la siguiente manera:
importar java.util.Scanner;
clase pública principal {
principal vacío estático público (String args []) {
Escáner en = nuevo escáner (System.in);
BinarySearchTree<Carácter> root=null;
mientras(en.hasNext()){
int t=en.nextInt();
si(t==0) romper;
root=new BinarySearchTree<Carácter>();
Resultado de cadena = nulo;
Resultado de cadena1 = nulo;
Cadena s=in.next();
for(int i=0;i<s.length();i++){
root.insert(s.charAt(i));
}
resultado=root.printTree(root.getRoot());
para(int i=0;i<t;i++){
root=new BinarySearchTree<Carácter>();
s=en.siguiente();
for(int j=0;j<s.length();j++){
root.insert(s.charAt(j));
}
resultado1=root.printTree(root.getRoot());
if(resultado.equals(resultado1)) System.out.println("SÍ");
else System.out.println("NO");
}
}
}
}
clase BinaryNode< T extiende Comparable<T>> {//Nodo del árbol de búsqueda binaria
BinaryNode<T> izquierda;
BinaryNode<T> derecha;
elemento T;
public BinaryNode(T elElemento){
this(elElemento, nulo, nulo);
}
public BinaryNode(T theElement, BinaryNode lt, BinaryNode rt){
elemento = elElemento;
izquierda = <
derecha = rt;
}
público T getElement(){
devolver este elemento;
}
público BinaryNode<T> getLeft(){
devolver esto.izquierda;
}
público BinaryNode<T> getRight(){
devolver esto.derecho;
}
cadena pública toString(){
elemento de retorno + "";
}
}
clase BinarySearchTree< T extiende Comparable<T>>{//árbol de búsqueda binaria
privado BinaryNode<T> root;//nodo raíz
público BinarySearchTree(){//Constructor
raíz = nulo;
}
público BinarySearchTree(BinaryNode< T> t){//Constructor
raíz = t;
}
vacío público makeEmpty(){
raíz = nulo;
}
público booleano está vacío(){
devolver raíz == nulo;
}
público BinaryNode<T> getRoot(){
devolver raíz;
}
público T encontrar(T x){
devolver buscar(x, raíz).elemento;
}
inserción de vacío público (T x) {
raíz = insertar(x, raíz);
}
printTree público vacío(){
imprimirárbol(raíz);
}
BinaryNode privado< T> find(T x, BinaryNode< T> t){// Operación de búsqueda
si(t==nulo){
devolver nulo;
}
if(x.compareTo(t.elemento) < 0){
devolver buscar(x, t.izquierda);
}
de lo contrario si(x.compareTo(t.elemento) == 0){
devolver t;
}
demás{
devolver buscar(x, t.derecha);
}
}
operación privada BinaryNode< T> insert(T x, BinaryNode< T> t){//Insertar
si(t==nulo){
t = nuevo BinaryNode<T>(x, nulo, nulo);
}
de lo contrario si(x.compareTo(t.element) < 0){
t.izquierda = insertar(x, t.izquierda);
}
de lo contrario si(x.compareTo(t.element) > 0){
t.derecha = insertar(x, t.derecha);
}
demás;
devolver t;
}
stringBuffer privado sb=nuevo StringBuffer();
public String printTree(BinaryNode< T> t){// Recorrido de pedido previo del árbol de búsqueda binaria
si(t!= nulo){
sb.append(t.elemento);
printTree(t.izquierda);
printTree(t.derecha);
}
devolver sb.toString();
}
}
