In diesem Artikel wird hauptsächlich das Suchen, Einfügen, Löschen, Durchlaufen usw. des in Java implementierten binären Suchbaums vorgestellt. Es hat einen sehr guten Referenzwert. Schauen wir es uns mit dem Editor an.
Kürzlich möchte ich etwas über die spezifische Implementierung von HashMap in JDK1.8 lesen, aber weil die Implementierung von HashMap Rot-Schwarz verwendet Bäume, daher denke ich, dass es notwendig ist, zuerst das relevante Wissen über rot-schwarze Bäume zu überprüfen, deshalb habe ich dieses Essay-Memo geschrieben. Bitte weisen Sie darauf hin, wenn es Fehler gibt ~
Um rot-schwarze Bäume zu lernen, habe ich Ich denke, es ist notwendig, aus binären Suchbäumen zu lernen. Um mit dem Lernen zu beginnen, stellt dieser Aufsatz hauptsächlich das Suchen, Einfügen, Löschen, Durchlaufen usw. des in Java implementierten binären Suchbaums vor.
Der binäre Suchbaum muss die folgenden vier Bedingungen erfüllen:
Wenn der linke Teilbaum eines Knotens nicht leer ist, werden die Werte aller Knoten auf dem Der linke Teilbaum ist kleiner als der Wert seines Wurzelknotens.
Wenn der rechte Teilbaum eines Knotens nicht leer ist, sind die Werte aller Knoten im rechten Teilbaum größer als der Wert seines Wurzelknotens Knoten;
Der linke und der rechte Teilbaum eines Knotens sind jeweils auch binäre Suchbäume.
Es gibt keine Knoten mit gleichen Schlüsselwerten.
Beispiel für einen binären Suchbaum:
Abbildung 1
Weiter basierend auf Abbildung 1. Wir stellen die zugehörigen Operationen des binären Suchbaums vor.
Zunächst sollte es eine Klasse geben, die sich auf das Knotenobjekt bezieht und den Namen Node trägt.
class Node {
int key;
int value;
Node leftChild;
Node rightChild;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
public void displayNode() {
}
}Die Node-Klasse enthält den Schlüsselwert, der zur Bestimmung der entsprechenden Position des Knotens im Baum verwendet wird. Der Wertwert repräsentiert den Inhalt zu speichern und enthält außerdem Punkte nach links und rechts. Zwei Verweise auf untergeordnete Knoten.
Schauen wir uns als Nächstes die entsprechende Klasse des Suchbaums an:
class Tree {
Node root;//保存树的根
public Node find(int key) {//查找指定节点
}
public void insert(int key, int value) {//插入节点
}
public boolean delete(int key) {//删除指定节点
}
private Node getDirectPostNode(Node delNode) {//得到待删除节点的直接后继节点
}
public void preOrder(Node rootNode) {//先序遍历树
}
public void inOrder(Node rootNode) {//中序遍历树
}
public void postOrder(Node rootNode) {//后序遍历树
}
}Das Framework, das den Baum in der Klasse darstellt, einschließlich Suchen, Einfügen und Durchlaufen löschen die entsprechenden Methoden, von denen die Knotenlöschoperation die komplizierteste ist und im Folgenden einzeln vorgestellt wird.
1. Suchen Sie einen Knoten
Aufgrund der Besonderheit der Definition des binären Suchbaums müssen Sie ihn nur von der Wurzel aus anhand des Eingabeschlüsselwerts vergleichen . Wenn er kleiner ist als der Schlüsselwert der Wurzel, wird er mit dem linken Teilbaum der Wurzel verglichen, und der Schlüsselwert, der größer als die Wurzel ist, wird mit dem rechten Teilbaum der Wurzel verglichen, und so weiter wird zurückgegeben, andernfalls wird null zurückgegeben.
public Node find(int key) {
Node currentNode = root;
while (currentNode != null && currentNode.key != key) {
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
} else {
currentNode = currentNode.rightChild;
}
}
return currentNode;
}2. Das Einfügen von Knoten
ähnelt aufgrund der Besonderheit des Binärer Suchbaum: Der einzufügende Knoten muss auch vom Wurzelknoten aus verglichen werden. Wenn er kleiner als der Wurzelknoten ist, wird er mit dem linken Teilbaum des Wurzelknotens verglichen Rechter Teilbaum. Bis der linke Teilbaum leer ist oder der rechte Teilbaum leer ist, fügen Sie ihn ein. Für die entsprechende leere Position müssen Sie während des Vergleichsvorgangs darauf achten, die Informationen des übergeordneten Knotens zu speichern und ob die einzufügende Position vorhanden ist den linken Teilbaum oder den rechten Teilbaum des übergeordneten Knotens, damit er an der richtigen Position eingefügt werden kann.
public void insert(int key, int value) {
if (root == null) {
root = new Node(key, value);
return;
}
Node currentNode = root;
Node parentNode = root;
boolean isLeftChild = true;
while (currentNode != null) {
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
isLeftChild = true;
} else {
currentNode = currentNode.rightChild;
isLeftChild = false;
}
}
Node newNode = new Node(key, value);
if (isLeftChild) {
parentNode.leftChild = newNode;
} else {
parentNode.rightChild = newNode;
}
}3. Durchlaufen eines binären Suchbaums
Der Durchlaufvorgang ist genau derselbe wie der Durchlauf eines gewöhnlicher Binärbaum. Es besteht keine Notwendigkeit, auf Details einzugehen.
public void preOrder(Node rootNode) {
if (rootNode != null) {
System.out.println(rootNode.key + " " + rootNode.value);
preOrder(rootNode.leftChild);
preOrder(rootNode.rightChild);
}
}
public void inOrder(Node rootNode) {
if (rootNode != null) {
inOrder(rootNode.leftChild);
System.out.println(rootNode.key + " " + rootNode.value);
inOrder(rootNode.rightChild);
}
}
public void postOrder(Node rootNode) {
if (rootNode != null) {
postOrder(rootNode.leftChild);
postOrder(rootNode.rightChild);
System.out.println(rootNode.key + " " + rootNode.value);
}
}4. Löschen Sie den angegebenen Knoten.
Das Löschen von Knoten in einem binären Suchbaum ist kompliziert und kann in die folgenden drei Situationen unterteilt werden.
1. Der zu löschende Knoten ist ein Blattknoten und kann direkt gelöscht werden.
public boolean delete(int key) {
Node currentNode = root;//用来保存待删除节点
Node parentNode = root;//用来保存待删除节点的父亲节点
boolean isLeftChild = true;//用来确定待删除节点是父亲节点的左孩子还是右孩子
while (currentNode != null && currentNode.key != key) {
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
isLeftChild = true;
} else {
currentNode = currentNode.rightChild;
isLeftChild = false;
}
}
if (currentNode == null) {
return false;
}
if (currentNode.leftChild == null && currentNode.rightChild == null) {//要删除的节点为叶子节点
if (currentNode == root)
root = null;
else if (isLeftChild)
parentNode.leftChild = null;
else
parentNode.rightChild = null;
}
......
}2. Der zu löschende Knoten hat nur einen untergeordneten Knoten
Um beispielsweise den Knoten mit dem Schlüsselwert 11 in Abbildung 1 zu löschen, müssen Sie nur das linke untergeordnete Element des Knotens mit dem Schlüsselwert 13 auf den Knoten mit dem Schlüsselwert 12 verweisen, um den Knoten mit dem Schlüssel zu löschen Wert 11.
Der aus der obigen Analyse erhaltene Code lautet wie folgt (gefolgt von den Auslassungspunkten der obigen Löschmethode):
else if (currentNode.rightChild == null) {//要删除的节点只有左孩子
if (currentNode == root)
root = currentNode.leftChild;
else if (isLeftChild)
parentNode.leftChild = currentNode.leftChild;
else
parentNode.rightChild = currentNode.leftChild;
} else if (currentNode.leftChild == null) {//要删除的节点只有右孩子
if (currentNode == root)
root = currentNode.rightChild;
else if (isLeftChild)
parentNode.leftChild = currentNode.rightChild;
else
parentNode.rightChild = currentNode.rightChild;
}
......3, der zu löschende Knoten hat sowohl linke als auch rechte untergeordnete Elemente.
Wenn Sie beispielsweise den Knoten mit dem Schlüsselwert 10 in Abbildung 1 löschen, müssen Sie den Knoten mit dem Schlüsselwert 10 durch den geordneten Nachfolgeknoten (Knoten) ersetzen 11).Knoten und löschen Sie den In-Order-Nachfolgeknoten des Knotens mit einem Schlüsselwert von 10. Gemäß den relevanten Regeln der In-Order-Traversierung den direkten In-Order-Nachfolgeknoten des Knotens mit einem Schlüsselwert von 10 muss der Knoten mit dem kleinsten Schlüsselwert in seinem rechten Teilbaum sein. Daher darf der In-Order-Nachfolgeknoten keine oder nur einen rechten Unterknoten enthalten. Das Löschen des In-Order-Nachfolgeknotens gehört zu den in 1 und beschriebenen Situationen 2 oben. In Abbildung 1 ist der direkte Folgeknoten in der Reihenfolge des Knotens mit dem Schlüsselwert 10 11, und Knoten 11 enthält ein rechtes Kind 12.
Das Löschen des Knotens mit dem Schlüsselwert 10 in Abbildung 1 ist in die folgenden Schritte unterteilt:
a. Suchen Sie den direkten Nachfolgeknoten des Knotens mit Schlüsselwert 10 (d. h. der Knoten 11 mit dem kleinsten Wert in seinem rechten Teilbaum) und löschen Sie diesen direkten Nachfolgeknoten in der Reihenfolge.
private Node getDirectPostNode(Node delNode) {//方法作用为得到待删除节点的直接后继节点
Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
Node direcrPostNode = delNode;//用来保存待删除节点的直接后继节点
Node currentNode = delNode.rightChild;
while (currentNode != null) {
parentNode = direcrPostNode;
direcrPostNode = currentNode;
currentNode = currentNode.leftChild;
}
if (direcrPostNode != delNode.rightChild) {//从树中删除此直接后继节点
parentNode.leftChild = direcrPostNode.rightChild;
direcrPostNode.rightChild = null;
}
return direcrPostNode;//返回此直接后继节点
}b Weisen Sie dem zu löschenden Knoten den Schlüssel und den Wert des Nachfolgeknotens zu . Schlüssel, Wert. (Nach dem Auslassungscode in Fall 2)
else { //要删除的节点既有左孩子又有右孩子
//思路：用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
//右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
Node directPostNode = getDirectPostNode(currentNode);
currentNode.key = directPostNode.key;
currentNode.value = directPostNode.value;
}Der Vorgang zum Löschen des angegebenen Knotens endet.
Abschließend werden der vollständige Code und der einfache Testcode sowie die Testergebnisse angegeben:
class Node {
int key;
int value;
Node leftChild;
Node rightChild;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
public void displayNode() {
}
}
class Tree {
Node root;
public Node find(int key) {
Node currentNode = root;
while (currentNode != null && currentNode.key != key) {
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
} else {
currentNode = currentNode.rightChild;
}
}
return currentNode;
}
public void insert(int key, int value) {
if (root == null) {
root = new Node(key, value);
return;
}
Node currentNode = root;
Node parentNode = root;
boolean isLeftChild = true;
while (currentNode != null) {
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
isLeftChild = true;
} else {
currentNode = currentNode.rightChild;
isLeftChild = false;
}
}
Node newNode = new Node(key, value);
if (isLeftChild) {
parentNode.leftChild = newNode;
} else {
parentNode.rightChild = newNode;
}
}
public boolean delete(int key) {
Node currentNode = root;
Node parentNode = root;
boolean isLeftChild = true;
while (currentNode != null && currentNode.key != key) {
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
isLeftChild = true;
} else {
currentNode = currentNode.rightChild;
isLeftChild = false;
}
}
if (currentNode == null) {
return false;
}
if (currentNode.leftChild == null && currentNode.rightChild == null) {
//要删除的节点为叶子节点
if (currentNode == root)
root = null;
else if (isLeftChild)
parentNode.leftChild = null;
else
parentNode.rightChild = null;
} else if (currentNode.rightChild == null) {//要删除的节点只有左孩子
if (currentNode == root)
root = currentNode.leftChild;
else if (isLeftChild)
parentNode.leftChild = currentNode.leftChild;
else
parentNode.rightChild = currentNode.leftChild;
} else if (currentNode.leftChild == null) {//要删除的节点只有右孩子
if (currentNode == root)
root = currentNode.rightChild;
else if (isLeftChild)
parentNode.leftChild = currentNode.rightChild;
else
parentNode.rightChild = currentNode.rightChild;
} else { //要删除的节点既有左孩子又有右孩子
//思路：用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
//右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
Node directPostNode = getDirectPostNode(currentNode);
currentNode.key = directPostNode.key;
currentNode.value = directPostNode.value;
}
return true;
}
private Node getDirectPostNode(Node delNode) {//方法作用为得到待删除节点的直接后继节点
Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
Node direcrPostNode = delNode;//用来保存待删除节点的直接后继节点
Node currentNode = delNode.rightChild;
while (currentNode != null) {
parentNode = direcrPostNode;
direcrPostNode = currentNode;
currentNode = currentNode.leftChild;
}
if (direcrPostNode != delNode.rightChild) {//从树中删除此直接后继节点
parentNode.leftChild = direcrPostNode.rightChild;
direcrPostNode.rightChild = null;
}
return direcrPostNode;//返回此直接后继节点
}
public void preOrder(Node rootNode) {
if (rootNode != null) {
System.out.println(rootNode.key + " " + rootNode.value);
preOrder(rootNode.leftChild);
preOrder(rootNode.rightChild);
}
}
public void inOrder(Node rootNode) {
if (rootNode != null) {
inOrder(rootNode.leftChild);
System.out.println("key: " + rootNode.key + " " + "value: " + rootNode.value);
inOrder(rootNode.rightChild);
}
}
public void postOrder(Node rootNode) {
if (rootNode != null) {
postOrder(rootNode.leftChild);
postOrder(rootNode.rightChild);
System.out.println(rootNode.key + " " + rootNode.value);
}
}
}
public class BinarySearchTreeApp {
public static void main(String[] args) {
Tree tree = new Tree();
tree.insert(6, 6);//插入操作,构造图一所示的二叉树
tree.insert(3, 3);
tree.insert(14, 14);
tree.insert(16, 16);
tree.insert(10, 10);
tree.insert(9, 9);
tree.insert(13, 13);
tree.insert(11, 11);
tree.insert(12, 12);
System.out.println("删除前遍历结果");
tree.inOrder(tree.root);//中序遍历操作
System.out.println("删除节点10之后遍历结果");
tree.delete(10);//删除操作
tree.inOrder(tree.root);
}
}Testergebnisse:
Oben finden Sie die Grafik- und Textdetails zum Suchen, Einfügen, Löschen und Durchlaufen eines binären Suchbaums in Java. Bitte beachten Sie zu weiteren verwandten Inhalten. PHP-chinesische Website (m.sbmmt.com)!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
