Technologieaustausch

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

Konzept des binären Suchbaums

Der binäre Suchbaum, auch als binärer Sortierbaum oder binärer Suchbaum bekannt, ist eine Art Binärbaum. Er weist die folgenden drei Merkmale auf.

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

Vereinfacht ausgedrückt erfüllen alle Knoten dieses Binärbaums: linkes Kind < Elternknoten < rechtes Kind.

Binäre Suchbaumoperationen

Binäre Suchbaumsuche

Die Suche in einem binären Suchbaum ähnelt in gewisser Weise der binären Suche. Wenn die Suche kleiner als der Wurzelknoten ist, gehen Sie zum linken Teilbaum, und wenn sie größer als der Wurzelknoten ist, gehen Sie zum rechten Teilbaum. Die Höhe kann maximal oft durchsucht werden. Wenn sie leer ist und nicht gefunden wird, bedeutet dies, dass der Wert nicht vorhanden ist.

Einfügen eines binären Suchbaums

Befolgen Sie zunächst die Suchmethode und fügen Sie den Knoten ein, wenn er leer ist. Damit ist das Einfügen des binären Suchbaums abgeschlossen.

Löschung des binären Suchbaums

Das Löschen von Knoten im binären Suchbaum muss je nach Situation erfolgen.

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