Uma árvore de pesquisa binária é organizada de acordo com a estrutura da árvore binária. Tal árvore pode ser representada por uma estrutura de lista encadeada, onde cada nó é um objeto. Além dos dados, o nó também inclui os campos left, right e p, que apontam para o filho esquerdo e o filho direito do nó respectivamente. Se o nó não existir, é NULL.
É uma árvore vazia ou uma árvore binária com as seguintes propriedades:
1) Se a subárvore esquerda não estiver vazia, então os valores de todos os nós da subárvore esquerda serão menores que o valor de seu nó raiz;
(2) Se a subárvore direita não estiver vazia, então os valores de todos os nós da subárvore direita são maiores que o valor de seu nó raiz;
(3) As subárvores esquerda e direita também são árvores de busca binária, respectivamente;
Obviamente, as propriedades acima são satisfeitas, então percorrer a árvore de pesquisa binária em ordem significa percorrer a ordem de pequeno para grande, e é por isso que é chamada de árvore de classificação. Claro, o menor e maior que acima pode ser alterado de acordo com o seu. próprias necessidades.
Várias operações comuns de árvores de pesquisa binária: pesquisar, excluir e inserir.
UDH 3791:
Descrição do problema
Determine se duas sequências são a mesma sequência da árvore de pesquisa binária
Entrada
Comece com um número n, (1<=n<=20) significa que há n números que precisam ser julgados e a entrada termina quando n= 0.
A próxima linha é uma sequência. O comprimento da sequência é menor que 10 e contém números (0 a 9). Com base nesta sequência, uma árvore de pesquisa binária pode ser construída.
Existem n sequências nas próximas n linhas. O formato de cada sequência é o mesmo da primeira sequência. Determine se essas duas sequências podem formar a mesma árvore de pesquisa binária.
Saída
Se as sequências forem iguais, imprima SIM, caso contrário, imprima NÃO
Exemplo de entrada
2
567432
543267
576342
0
Saída de amostra
SIM
NÃO
Explicação: Depois de inserir os números em ordem, use a travessia de pré-ordem da árvore binária para determinar se as duas árvores binárias são iguais.
Código Java
Copie o código do código da seguinte forma:
importar java.util.Scanner;
classe pública Principal{
public static void main(String args[]){
Scanner in=novo Scanner(System.in);
BinarySearchTree<Caracter> root=null;
enquanto(in.hasNext()){
int t=in.nextInt();
se(t==0) quebra;
root=new BinarySearchTree<Caracter>();
String resultado=nulo;
String resultado1=nulo;
String s=in.next();
for(int i=0;i<s.length();i++){
root.insert(s.charAt(i));
}
resultado=root.printTree(root.getRoot());
for(int i=0;i<t;i++){
root=new BinarySearchTree<Caracter>();
s=in.próximo();
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("SIM");
senão System.out.println("NÃO");
}
}
}
}
class BinaryNode< T extends Comparable<T>> {//Nó da árvore de pesquisa binária
BinaryNode<T> esquerda;
BinaryNode<T> certo;
Elemento T;
public BinaryNode(T theElement){
this(oElemento, null, null);
}
public BinaryNode(T theElement, BinaryNode lt, BinaryNode rt){
elemento = oElemento;
esquerda = <
direita = rt;
}
public T getElement(){
retorne este.elemento;
}
public BinaryNode<T> getLeft(){
retorne isto.esquerda;
}
public BinaryNode<T> getRight(){
retorne isso.certo;
}
String pública paraString(){
elemento de retorno + "";
}
}
class BinarySearchTree<T estende Comparable<T>>{//Árvore de pesquisa binária
private BinaryNode<T> root; //nó raiz
public BinarySearchTree(){//Construtor
raiz = nulo;
}
public BinarySearchTree(BinaryNode< T> t){//Construtor
raiz = t;
}
public void makeEmpty(){
raiz = nulo;
}
booleano público isEmpty(){
retornar raiz == nulo;
}
public BinaryNode<T> getRoot(){
retornar raiz;
}
público T encontrar(T x){
retornar encontrar(x, raiz).elemento;
}
inserção de vazio público(T x){
raiz = inserir(x, raiz);
}
public void printTree(){
printTree(raiz);
}
private BinaryNode< T> find(T x, BinaryNode< T> t){//operação Find
if(t==nulo){
retornar nulo;
}
if(x.compareTo(t.element) < 0){
retornar encontrar (x, t.esquerda);
}
senão if(x.compareTo(t.element) == 0){
retornar t;
}
outro{
retornar encontrar(x, t.direita);
}
}
private BinaryNode< T> insert(T x, BinaryNode< T> t){//Inserir operação
if(t==nulo){
t = novo BinaryNode<T>(x, nulo, nulo);
}
senão if(x.compareTo(t.element) < 0){
t.esquerda = inserir(x, t.esquerda);
}
senão if(x.compareTo(t.element) > 0){
t.direita = inserir(x, t.direita);
}
outro;
retornar t;
}
private StringBuffer sb=new StringBuffer();
public String printTree(BinaryNode< T> t){//Pré-encomenda da travessia da árvore de pesquisa binária
if(t != nulo){
sb.append(t.element);
printTree(t.esquerda);
printTree(t.direita);
}
retornar sb.toString();
}
}
