Un arbre de recherche binaire est organisé selon la structure de l'arbre binaire. Un tel arbre peut être représenté par une structure de liste chaînée, où chaque nœud est un objet. En plus des données, le nœud comprend également les champs left, right et p, qui pointent respectivement vers les fils gauche et droit du nœud. Si le nœud n'existe pas, il est NULL.
Il s'agit soit d'un arbre vide, soit d'un arbre binaire avec les propriétés suivantes :
1) Si le sous-arbre de gauche n'est pas vide, alors les valeurs de tous les nœuds du sous-arbre de gauche sont inférieures à la valeur de son nœud racine ;
(2) Si le sous-arbre droit n'est pas vide, alors les valeurs de tous les nœuds du sous-arbre droit sont supérieures à la valeur de son nœud racine ;
(3) Les sous-arbres gauche et droit sont également respectivement des arbres de recherche binaires ;
Évidemment, les propriétés ci-dessus sont satisfaites, alors parcourir l'arbre de recherche binaire dans l'ordre signifie parcourir dans l'ordre du petit au grand, c'est pourquoi on l'appelle un arbre de tri. Bien sûr, les éléments inférieur et supérieur ci-dessus peuvent être modifiés en fonction de votre. propres besoins.
Plusieurs opérations courantes des arbres de recherche binaires : rechercher, supprimer et insérer.
HDU3791 :
Description du problème
Déterminer si deux séquences sont la même séquence d'arbre de recherche binaire
Saisir
Commencez par un nombre n, (1<=n<=20) signifie qu'il y a n nombres qui doivent être jugés, et l'entrée se termine lorsque n= 0.
La ligne suivante est une séquence. La longueur de la séquence est inférieure à 10 et contient des nombres (0~9). Sur la base de cette séquence, un arbre de recherche binaire peut être construit.
Il y a n séquences dans les n lignes suivantes. Le format de chaque séquence est le même que celui de la première séquence. Veuillez déterminer si ces deux séquences peuvent former le même arbre de recherche binaire.
Sortir
Si les séquences sont les mêmes, affichez OUI, sinon affichez NON.
Exemple d'entrée
2
567432
543267
576342
0
Exemple de sortie
OUI
NON
Explication : Après avoir inséré les nombres dans l'ordre, utilisez le parcours de pré-commande d'arbre binaire pour déterminer si les deux arbres binaires sont identiques.
Code Java
Copiez le code comme suit :
importer java.util.Scanner ;
classe publique principale{
public static void main(String args[]){
Scanner dans = nouveau scanner (System.in);
BinarySearchTree<Character> root=null ;
while(in.hasNext()){
int t=in.nextInt();
si(t==0) pause ;
root=nouveau BinarySearchTree<Character>();
Résultat de chaîne=null ;
Chaîne result1=null ;
String s=in.next();
pour(int i=0;i<s.length();i++){
root.insert(s.charAt(i));
}
result=root.printTree(root.getRoot());
pour(int i=0;i<t;i++){
root=nouveau BinarySearchTree<Character>();
s=in.next();
pour(int j=0;j<s.length();j++){
root.insert(s.charAt(j));
}
result1=root.printTree(root.getRoot());
if(result.equals(result1)) System.out.println("OUI");
sinon System.out.println("NON");
}
}
}
}
class BinaryNode< T extends Comparable<T>> {//nœud d'arbre de recherche binaire
BinaryNode<T> gauche ;
BinaryNode<T> à droite ;
Élément T ;
public BinaryNode (T l'élément) {
ceci(l'Élément, null, null);
}
public BinaryNode (T theElement, BinaryNode lt, BinaryNode rt){
élément = l'Élément ;
gauche = <
droite = rt;
}
public TgetElement(){
renvoie cet élément ;
}
public BinaryNode<T>getLeft(){
renvoie this.left;
}
public BinaryNode<T>getRight(){
retournez ceci.droit;
}
chaîne publique toString(){
élément de retour + "" ;
}
}
class BinarySearchTree< T extends Comparable<T>>{//Arbre de recherche binaire
racine privée BinaryNode<T> ;//nœud racine
public BinarySearchTree(){//Constructeur
racine = nul ;
}
public BinarySearchTree(BinaryNode< T> t){//Constructeur
racine = t ;
}
public void makeEmpty(){
racine = nul ;
}
public booléen isEmpty(){
retourner racine == null ;
}
public BinaryNode<T> getRoot(){
retourner la racine ;
}
public T trouver (T x){
return find(x, root).element;
}
insertion de vide public (T x) {
racine = insert(x, racine);
}
public void printTree(){
printTree(racine);
}
private BinaryNode< T> find(T x, BinaryNode< T> t){//Opération de recherche
si(t==null){
renvoie null ;
}
si(x.compareTo(t.element) < 0){
return find(x, t.left);
}
sinon if(x.compareTo(t.element) == 0){
retourner t ;
}
autre{
return find(x, t.right);
}
}
private BinaryNode< T> insert(T x, BinaryNode< T> t){//Opération d'insertion
si(t==null){
t = nouveau BinaryNode<T>(x, nul, nul);
}
sinon if(x.compareTo(t.element) < 0){
t.left = insert(x, t.left);
}
sinon if(x.compareTo(t.element) > 0){
t.right = insert(x, t.right);
}
autre;
retourner t ;
}
private StringBuffer sb=new StringBuffer();
public String printTree(BinaryNode< T> t){//Parcours de pré-commande de l'arbre de recherche binaire
si(t != nul){
sb.append(t.element);
printTree(t.left);
printTree(t.right);
}
return sb.toString();
}
}
