Compartir tecnología

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Concepto de árbol de búsqueda binaria

El árbol de búsqueda binaria, también conocido como árbol de clasificación binaria o árbol de búsqueda binaria, es un tipo de árbol binario que tiene las siguientes tres características.

1.二叉搜索树的左子树上的所有节点的val值均小于根节点的val值；
2.二叉搜索树的右子树上的所有节点的val值均大于根节点的val值；
3.二叉搜索树树的做右子树均为二叉搜索树。
1
2
3

En pocas palabras, todos los nodos de este árbol binario satisfacen: hijo izquierdo <nodo padre <hijo derecho.

Operaciones de árbol de búsqueda binaria

Búsqueda de árbol de búsqueda binaria

La búsqueda en un árbol de búsqueda binario es algo similar a la búsqueda binaria. Si la búsqueda es más pequeña que el nodo raíz, vaya al subárbol izquierdo y si es más grande que el nodo raíz, vaya al subárbol derecho. Puedes buscar la altura un máximo de veces. Si llega al vacío y no se encuentra, significa que el valor no existe.

Inserción de árbol de búsqueda binaria

Primero, siga el método de búsqueda e inserte el nodo cuando esté vacío. Esto completa la inserción del árbol de búsqueda binario.

Eliminación del árbol de búsqueda binaria.

La eliminación de nodos en el árbol de búsqueda binaria debe realizarse según diferentes situaciones.

1.删除节点没有孩子，则可以直接删除。
2.删除节点有左孩子，被删除节点的父节点指向左孩子，然后直接删除该节点、
3.删除节点有右孩子，被删除节点的父节点指向右孩子，然后直接删除该节点。
4.删除节点有左右孩子，则找到右孩子中的最小值（中序遍历可以找到），用这个最小值取代该节点。
1
2
3
4