Ein binärer Suchbaum ist entsprechend der binären Baumstruktur organisiert. Ein solcher Baum kann durch eine verknüpfte Listenstruktur dargestellt werden, in der jeder Knoten ein Objekt ist. Zusätzlich zu den Daten enthält der Knoten auch die Felder left, right und p, die auf den linken bzw. rechten Sohn des Knotens verweisen. Wenn der Knoten nicht existiert, ist er NULL.
Es handelt sich entweder um einen leeren Baum oder um einen Binärbaum mit den folgenden Eigenschaften:
1) Wenn der linke Teilbaum nicht leer ist, sind die Werte aller Knoten im linken Teilbaum kleiner als der Wert seines Wurzelknotens;
(2) Wenn der rechte Teilbaum nicht leer ist, sind die Werte aller Knoten im rechten Teilbaum größer als der Wert seines Wurzelknotens;
(3) Der linke und der rechte Teilbaum sind jeweils auch binäre Suchbäume;
Offensichtlich sind die oben genannten Eigenschaften erfüllt. Das Durchlaufen des binären Suchbaums in der Reihenfolge bedeutet, dass er in der Reihenfolge von klein nach groß durchlaufen wird, weshalb er als Sortierbaum bezeichnet wird. Natürlich können die oben genannten Kleiner- und Größer-Werte je nach Bedarf geändert werden eigene Bedürfnisse.
Mehrere gängige Operationen binärer Suchbäume: Suchen, Löschen und Einfügen.
HDU 3791:
Problembeschreibung
Bestimmen Sie, ob zwei Sequenzen dieselbe binäre Suchbaumsequenz sind
Eingang
Beginnen Sie mit einer Zahl n, (1<=n<=20) bedeutet, dass es n Zahlen gibt, die beurteilt werden müssen, und die Eingabe endet, wenn n=0.
Die nächste Zeile ist eine Sequenz. Die Länge der Sequenz beträgt weniger als 10 und enthält Zahlen (0 bis 9). Basierend auf dieser Sequenz kann ein binärer Suchbaum erstellt werden.
Es gibt n Sequenzen in den nächsten n Zeilen. Das Format jeder Sequenz ist das gleiche wie das der ersten Sequenz. Bitte bestimmen Sie, ob diese beiden Sequenzen denselben binären Suchbaum bilden können.
Ausgabe
Wenn die Sequenzen gleich sind, geben Sie JA aus, andernfalls geben Sie NEIN aus
Beispieleingabe
2
567432
543267
576342
0
Beispielausgabe
JA
NEIN
Erläuterung: Nachdem Sie die Zahlen der Reihe nach eingefügt haben, verwenden Sie die Binärbaum-Vorbestellungsdurchquerung, um zu bestimmen, ob die beiden Binärbäume gleich sind.
Java-Code
Kopieren Sie den Codecode wie folgt:
import java.util.Scanner;
öffentliche Klasse Main{
public static void main(String args[]){
Scanner in=neuer Scanner(System.in);
BinarySearchTree<Character> root=null;
while(in.hasNext()){
int t=in.nextInt();
if(t==0) break;
root=new BinarySearchTree<Character>();
String result=null;
String result1=null;
String s=in.next();
for(int i=0;i<s.length();i++){
root.insert(s.charAt(i));
}
result=root.printTree(root.getRoot());
for(int i=0;i<t;i++){
root=new 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("YES");
sonst System.out.println("NO");
}
}
}
}
Klasse BinaryNode< T erweitert Comparable<T>> {//Binärer Suchbaumknoten
BinaryNode<T> links;
BinaryNode<T> right;
T-Element;
public BinaryNode(T theElement){
this(theElement, null, null);
}
public BinaryNode(T theElement, BinaryNode lt, BinaryNode rt){
element = theElement;
links = <
rechts = rt;
}
öffentliches T getElement(){
return this.element;
}
public BinaryNode<T> getLeft(){
return this.left;
}
public BinaryNode<T> getRight(){
return this.right;
}
öffentlicher String toString(){
Rückgabeelement + „“;
}
}
Klasse BinarySearchTree< T erweitert Comparable<T>>{//Binärer Suchbaum
privater BinaryNode<T> root;//Root-Knoten
öffentlicher BinarySearchTree(){//Konstruktor
root = null;
}
public BinarySearchTree(BinaryNode< T> t){//Constructor
Wurzel = t;
}
public void makeEmpty(){
root = null;
}
öffentlicher boolescher Wert isEmpty(){
return root == null;
}
public BinaryNode<T> getRoot(){
root zurückgeben;
}
öffentliches T find(T x){
return find(x, root).element;
}
public void insert(T x){
root = insert(x, root);
}
public void printTree(){
printTree(root);
}
private BinaryNode< T> find(T x, BinaryNode< T> t){//Find-Operation
if(t==null){
null zurückgeben;
}
if(x.compareTo(t.element) < 0){
return find(x, t.left);
}
sonst if(x.compareTo(t.element) == 0){
Rückkehr t;
}
anders{
return find(x, t.right);
}
}
privater BinaryNode< T> insert(T x, BinaryNode< T> t){//Insert-Vorgang
if(t==null){
t = new BinaryNode<T>(x, null, null);
}
sonst if(x.compareTo(t.element) < 0){
t.left = insert(x, t.left);
}
sonst if(x.compareTo(t.element) > 0){
t.right = insert(x, t.right);
}
anders;
Rückkehr t;
}
private StringBuffer sb=new StringBuffer();
public String printTree(BinaryNode< T> t){//Durchlauf des binären Suchbaums vorbestellen
if(t != null){
sb.append(t.element);
printTree(t.left);
printTree(t.right);
}
return sb.toString();
}
}
