Java réalise les détails graphiques de la recherche, de l'insertion, de la suppression et de la traversée des arbres de recherche binaires

Cet article présente principalement la recherche, l'insertion, la suppression, le parcours, etc. de l'arbre de recherche binaire implémenté en Java. Il a une très bonne valeur de référence. Jetons un coup d'œil avec l'éditeur

Récemment, je veux en savoir plus sur l'implémentation spécifique de HashMap dans JDK1.8, mais parce que l'implémentation de HashMap utilise le rouge-noir. arbres, je pense donc qu'il est nécessaire de revoir d'abord les connaissances pertinentes sur les arbres rouge-noir, j'ai donc écrit ce mémo d'essai. Veuillez indiquer s'il y a des erreurs ~

Pour apprendre les arbres rouge-noir, je. Je pense qu'il est nécessaire d'apprendre des arbres de recherche binaires. Pour commencer l'apprentissage, cet essai présente principalement Java pour implémenter la recherche, l'insertion, la suppression, le parcours, etc. d'un arbre de recherche binaire.

L'arbre de recherche binaire doit remplir les quatre conditions suivantes :

Si le sous-arbre gauche d'un nœud n'est pas vide, alors les valeurs de tous les nœuds sur le le sous-arbre gauche est égal à la valeur de son nœud racine

Si le sous-arbre droit d'un nœud n'est pas vide, alors les valeurs de tous les nœuds du sous-arbre droit sont supérieures à la valeur de sa racine node;

Les sous-arbres gauche et droit de n'importe quel nœud sont également respectivement des arbres de recherche binaires

Il n'y a pas de nœuds avec des valeurs de clé égales ;

Exemple d'arbre de recherche binaire :

Figure 1

Suivant basé sur la figure 1, nous introduisons les opérations associées à l’arbre de recherche binaire.

Tout d'abord, il devrait y avoir une classe liée à l'objet nœud, nommée Node.

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() {
 }
}

La classe Node contient la valeur clé, qui est utilisée pour déterminer la position correspondante du nœud dans l'arborescence. La valeur value représente le contenu. à stocker, et contient également des points à gauche et à droite Deux références aux nœuds enfants.

Ensuite, regardons la classe correspondante de l'arbre de recherche :

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) {//后序遍历树
 }
}

Le framework représentant l'arbre dans la classe , y compris la recherche, l'insertion et le parcours , supprimez les méthodes correspondantes, parmi lesquelles l'opération de suppression de nœud est la plus compliquée, qui sera présentée une par une ensuite.

1. Trouver un nœud

En raison de la particularité de la définition de l'arbre de recherche binaire, il vous suffit de comparer la valeur de la clé d'entrée à partir de la racine. est inférieur à La valeur clé de la racine est comparée au sous-arbre gauche de la racine, et la valeur clé supérieure à la racine est comparée au sous-arbre droit de la racine, et ainsi de suite. S'il est trouvé, le nœud correspondant est renvoyé, sinon, null est renvoyé.

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. L'insertion de nœuds

est similaire à l'opération de recherche, de par la particularité du arbre de recherche binaire, le nœud à insérer doit également être comparé à partir du nœud racine. S'il est plus petit que le nœud racine, il sera comparé au sous-arbre gauche du nœud racine. Sous-arbre droit. Jusqu'à ce que le sous-arbre gauche soit vide ou que le sous-arbre droit soit vide, insérez-le dans Pour la position vide correspondante, pendant le processus de comparaison, vous devez faire attention à sauvegarder les informations du nœud parent et si la position à insérer est la bonne. le sous-arbre gauche ou le sous-arbre droit du nœud parent, afin qu'il puisse être inséré dans la position correcte.

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. Parcours d'un arbre de recherche binaire

L'opération de parcours est exactement la même que celle d'un arbre de recherche binaire. arbre binaire ordinaire. Pas besoin d’entrer dans les détails.

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. Supprimez le nœud spécifié.

L'opération de suppression de nœuds dans un arbre de recherche binaire est compliquée et peut être divisée dans les trois situations suivantes.

1. Le nœud à supprimer est un nœud feuille et peut être supprimé directement.

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 Le nœud à supprimer n'a qu'un seul nœud enfant

Par exemple, pour supprimer le nœud avec la valeur de clé 11 dans la figure 1, il vous suffit de pointer l'enfant gauche du nœud avec la valeur de clé 13 vers le nœud avec la valeur de clé 12 pour supprimer le nœud avec la clé valeur 11.

Le code obtenu à partir de l'analyse ci-dessus est le suivant (suivi des points de suspension de la méthode de suppression ci-dessus) :

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 , le nœud à supprimer a à la fois des enfants gauche et droit.

Par exemple, si vous supprimez le nœud avec la valeur clé 10 dans la figure 1, vous devez remplacer le nœud avec la valeur clé 10 par le nœud successeur dans l'ordre (nœud ​​11). et supprimez le nœud successeur dans l'ordre du nœud avec une valeur clé de 10. Selon les règles pertinentes de parcours dans l'ordre, le nœud successeur direct dans l'ordre du nœud avec une valeur clé de 10 doit être le nœud avec la plus petite valeur de clé dans son sous-arbre droit. Par conséquent, le nœud successeur dans l'ordre ne doit pas contenir de nœuds enfants ou ne contenir qu'un seul enfant droit. La suppression du nœud successeur dans l'ordre appartient aux situations décrites en 1 et. 2 ci-dessus. Dans la figure 1, le nœud successeur direct dans l'ordre du nœud avec la valeur de clé 10 est 11, et le nœud 11 contient un enfant droit 12.

Ainsi, la suppression du nœud avec la valeur clé 10 dans la figure 1 est divisée en les étapes suivantes :

a. Trouver le nœud successeur direct dans l'ordre du nœud avec. valeur de clé 10 (c'est-à-dire le nœud 11 avec la plus petite valeur dans son sous-arbre droit) et supprimez ce nœud successeur direct dans l'ordre.

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. Attribuez la clé et la valeur du nœud successeur au nœud à supprimer. . clé, valeur. (Après le code des points de suspension dans le cas 2)

else { //要删除的节点既有左孩子又有右孩子
 //思路：用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
 //右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
 Node directPostNode = getDirectPostNode(currentNode);
 currentNode.key = directPostNode.key;
 currentNode.value = directPostNode.value;
}

L'opération de suppression du nœud spécifié se termine.

Enfin, le code complet ainsi que le code de test simple et les résultats du test sont donnés :

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);
 }
}

Résultats des tests :

Ce qui précède contient les détails graphiques et textuels sur la façon de trouver, d'insérer, de supprimer et de parcourir un arbre de recherche binaire en Java. Veuillez faire attention. vers du contenu plus pertinent. Site Web PHP chinois (www.php.cn) !