ืคืึธืจืคึผืืื
ืืขืจ ืึทืจืืืงื ืืื ืืืขืื ืืืื ืขืจื ืืืื ืืืืืขืจ. ืืื ืืขืฆืื ืก ืืขืืืื ืึทื ืึทืจืืืงื ืืืขืื ืืึธืจื ืืึธื ืืื ื ืืฉื ืฆืึธืื ืคืื ืืืืื ื ืฆื ืืืื ืขืจื ืืืืืขืจ, ืืืฒึทื ืื ืืขืืึธืื ืคืื ืืืื, ืืืื ืก ืืื ืืืืกืืขืงื ืืขื ืขื ื ืืฉื ืืึทืืืึทืืืง. ืืืฆื ืืื ืืึทืฉืืึธืกื ืฆื ืฉืจืืึทืื ืึทื ืึทืจืืืงื ืืืขืื ืืืืืขืจ. ืืืืืจ ืื ืืืืืขื.
ื ืืืื ืืื ืึท ืืึทืื ืกืืจืืงืืืจ ืืืึธืก ืืืฉืืืื ืคืื ื ืึธืืื ืคืืจืืื ืื ืืืจื ืขืืืฉืึทื. ืืืจ ืงืขื ืขื ืืึธืื ืึทื ืึท ืืืื ืืื ืึท ืกืคึผืขืฆืืขื ืคืึทื ืคืื ืึท ืืจืึทืคืืง. ืืึธ ืืื ืึท ืืืึทืฉืคึผืื ืืืื:
ืืึธืก ืืื ื ืืฉื ืึท ืืืื ืขืจื ืืืื ืืืื! ืึทืืฅ ืืื ืืขืฉื ืืื!
ืืืึธืงืึทืืืืึทืจื
ืืืึธืจืฆื
ืืืื ืืืึธืจืฆื - ืืึธืก ืืื ืืืึทื ืฉืคึผืืฅ ื ืึธืืข. ืืื ืืขื ืืืืฉืคึผืื, ืืึธืก ืืื ื ืึธืืข ื. ืืื ืึท ืืืื, ืืืืื ืืืื ืืืขื ืงืขื ืขื ืคืืจื ืคืื ืื ืืืึธืจืฆื ืฆื ืงืืื ืื ืืขืจืข ื ืึธืืข! ืืื ืคืึทืงื, ืงืืื ื ืึธืืข ืงืขื ืขื ืืืื ืืขืจืขืื ื ืืื ืืขืจ ืืืึธืจืฆื ืคืื ืื ืกืืืืจืืข ืงืึธืจืึทืกืคึผืึทื ืืื ื ืฆื ืืขื ื ืึธืืข.
ืขืืืขืจื / ืงืื ืืกืงืื ืืขืจ
ืึทืืข ื ืึธืืื ืึทืืืฅ ืืขืจ ืืืึธืจืฆื ืืึธืื ืคึผืื ืงื ืืืื ืืจืขื ืืืึธืก ืคืืจื ืึทืจืืืฃ ืฆื ืื ืื ืืขืจ ื ืึธืืข. ืืขืจ ื ืึธืืข ืืืื ืืืืื ืื ืงืจืึทื ื ืืืื ืขืจ ืืื ืืขืจืืคื ืคืึธืืขืจ ืืขื ื ืึธืืข. ื ื ืึธืืข ืืืื ืืื ืืขืจ ืื ืงืจืึทื ื ืืืื ืขืจ ืืื ืคืืจืืื ืื ืฆื ืขืก ืืื ืืขืจืืคื ืึธืคึผืฉืืึทืืืื ื ืืขื ื ืึธืืข. ืืื ืก ื ืืฆื ืึท ืืืึทืฉืคึผืื. ืืึธืืืจ ื ืขืืขื ื ืึธืืข ื, ืืขืจ ืคืึธืืขืจ ืืืขื ืืืื ื ืึธืืข ื, ืืื ืืืจืข ืงืื ืืขืจ ืืืขืื ืืืื ื ืึธืืขืก D, E ืืื F.
Sheet
ื ื ืึธืืข ืืืึธืก ืืื ืงืืื ืงืื ืืขืจ ืืืขื ืืืื ืืขืจืืคื ืึท ืืืึทื ืคืื ืืขื ืืืื. ืืื ืืขื ืืืึทืฉืคึผืื, ืื ืืืขืืขืจ ืืืขื ืืืื ื ืึธืืื D, E, F, G, I, J, K.
ืืึธืก ืืื ืื ืืจืื ื ืืขืจืืื ืึธืืึธืืืข. ืื ืืขืจืข ืงืึทื ืกืขืคึผืก ืืืขื ืืืื ืืืกืงืึทืกื ืืืืึทืืขืจ. ืึทืืื, ืึท ืืืื ืขืจื ืืืื ืืื ืึท ืืืื ืืื ืืืึธืก ืืขืืขืจ ื ืึธืืข ืืืขื ืืึธืื ื ืื ืืขืจ ืืื ืฆืืืื ืงืื ืืขืจ. ืืื ืืืจ ืืขืกื, ืืขืจ ืืืื ืคืื ืืขื ืืืึทืฉืคึผืื ืืืขื ื ืืฉื ืืืื ืืืื ืขืจื, ืืืืึทื ืื ื ืึธืืื ื ืืื ื ืืึธืื ืืขืจ ืืื ืฆืืืื ืงืื ืืขืจ. ืืึธ ืืื ืึท ืืืืฉืคึผืื ืคืื ืึท ืืืื ืขืจื ืืืื:
ืื ืืืื ื ืึธืืื ืงืขื ืขื ืึทื ืืืึทืืื ืงืืื ืืื ืคึฟืึธืจืืึทืฆืืข. ื ืืืื ืขืจื ืืื ืืืื ืืื ืึท ืืืื ืขืจื ืืืื ืืืึธืก ืืื ืื ืคืืืืขื ืืข ืคึผืจืึธืคึผืขืจืืืขืก:
- ืืืืืข ืืื ืงืก ืืื ืจืขืื ืกืืืืจืืขืก ืืขื ืขื ืืืื ืขืจื ืืืื ืืืืืขืจ.
- ืึทืืข ื ืึธืืื ืคืื ืื ืืื ืงืก ืกืืืืจืืข ืคืื โโืึท ืึทืจืืืืจืึทืจืืฉ ื ืึธืืข X ืืึธืื ืืึทืื ืฉืืืกื ืืืึทืืืขืก ืืืืื ืืงืขืจ ืืื ืื ืืืขืจื ืคืื ืื ืืึทืื ืฉืืืกื ืคืื ื ืึธืืข X ืืื.
- ืึทืืข ื ืึธืืื ืืื ืื ืจืขืื ืกืืืืจืืข ืคืื โโืึท ืึทืจืืืืจืึทืจืืฉ ื ืึธืืข X ืืึธืื ืืึทืื ืฉืืืกื ืืืึทืืืขืก ืืจืขืกืขืจ ืืื ืึธืืขืจ ืืืืึทื ืฆื ืื ืืืขืจื ืคืื ืื ืืึทืื ืฉืืืกื ืคืื ื ืึธืืข X ืืื.
ืฉืืืกื - ืงืืื ืืึทืจืึทืงืืขืจืืกืืืฉ ืคืื ืื ื ืึธืืข (ืืืฉื, ืึท ื ืืืขืจ). ืืขืจ ืฉืืืกื ืืื ืืืจืฃ ืึทืืื ืืืจ ืงืขื ืขื ืืขืคึฟืื ืขื ืืขื ืืืื ืขืืขืืขื ื ืฆื ืืืึธืก ืืขื ืฉืืืกื ืงืึธืจืึทืกืคึผืึทื ืื. ืืืึทืฉืคึผืื ืคืื ืึท ืืืื ืขืจื ืืืื ืืืื:
ืืืื ืืืื ืื ื
ืืืขื ืืืจ ืคึผืจืึธืืจืขืก, ืืื ืืืขื ืฆืืฉืืขืื ืขืืืขืืข (ืขืคืฉืขืจ ืืขืจืขื ืืืงื) ืงืึธื ืืจืขืงืืขื ืฆื ืคึฟืึทืจืืขืกืขืจื ืืืื ืคืืจืฉืืื ื. ืื ืคืื ืงืึธื ืืืขื ืืืื ืืื ืื ืกืืฃ ืคืื ืืขื ืึทืจืืืงื.
ื ืืืื ืืืฉืืืื ืคืื ื ืึธืืื. ื ืึธืืข ืกืืจืืงืืืจ:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
//...ะพััะฐะปัะฝัะต ะผะตัะพะดั ัะทะปะฐ
}
ืืขืืขืจ ื ืึธืืข ืืื ืฆืืืื ืงืื ืืขืจ (ืขืก ืืื ืืึทื ืฅ ืืขืืืขื ืึทื ืื leftChild ืืื / ืึธืืขืจ rightChild ืงืื ืืขืจ ืืืขื ืึทื ืืืึทืืื ืึท ื ืึทื ืืืขืจื). ืืืจ ืืืกืืึธืืข ืืืื ืืขืืขื ืึทื ืืื ืืขื ืคืึทื ืื ื ืืืขืจ ืืึทืื ืืขื ืขื ืื ืืึทืื ืกืืึธืจื ืืื ืื ื ืึธืืข; ืฉืืืกื - ื ืึธืืข ืฉืืืกื.
ืืืจ ืืึธืื ืืืืกืืขืฉืืขืื ืื ืงื ืืคึผ, ืืืฆื ืืึธืืืจ ืจืขืื ืืืขืื ืืจืื ืืืขื ืคึผืจืึธืืืขืืก ืืืขืื ืืืืืขืจ. ืืขืจื ืึธื, ืืื ืืขื ืืืึธืจื "ืืืื" ืืื ืืืขื ืืืื ืขื ืืขื ืืึทืืจืืฃ ืคืื ืึท ืืืื ืขืจื ืืืื ืืืื. ืืืื ืขืจื ืืืื ืกืืจืืงืืืจ:
public class BinaryTree<T> {
private Node<T> root;
//ะผะตัะพะดั ะดะตัะตะฒะฐ
}
ืืืจ ื ืึธืจ ืืึทืจืคึฟื ืื ืืืึธืจืฆื ืคืื ืืขื ืืืื ืืื ืึท ืงืืึทืก ืคืขืื, ืืืืึทื ืคึฟืื ืืขืจ ืืืึธืจืฆื, ื ืืฆื ืื getLeftChild() ืืื getRightChild() ืืขืืืึธืืก, ืืืจ ืงืขื ืขื ืืึทืงืืืขื ืฆื ืงืืื ื ืึธืืข ืืื ืืขื ืืืื.
ืึทืืืขืจืืืึทืื ืืื ืึท ืืืื
ืืืื
ืืื ืก ืืึธืื ืืืจ ืืึธืื ืึท ืงืึทื ืกืืจืึทืงืืึทื ืืืื. ืืื ืฆื ืืขืคึฟืื ืขื ืึทื ืขืืขืืขื ื ืืื ืื ืฉืืืกื ืฉืืืกื? ืืืจ ืืึทืจืคึฟื ืฆื ืกืึทืงืืืขื ืืฉืึทืื ืืึทื ืคืื ืื ืืืึธืจืฆื ืึทืจืึธืคึผ ืื ืืืื ืืื ืคืึทืจืืืืึทืื ืื ืืืขืจื ืคืื ืฉืืืกื ืืื ืืขืจ ืฉืืืกื ืคืื ืืขืจ ืืืืึทืืขืจ ื ืึธืืข: ืืืื ืืขืจ ืฉืืืกื ืืื ืืืืื ืืงืขืจ ืืื ืืขืจ ืฉืืืกื ืคืื ืืขืจ ืืืืึทืืขืจ ื ืึธืืข, ืืืื ืฆื ืื ืืื ืงืก ืงืื ื ืคืื ืื ื ืึธืืข, ืืืื ืขืก ืืื. ืืขืจ, ืฆื ืื ืจืขืื ืืืื ืขืจ, ืืืื ืื ืฉืืืกืืขื ืืขื ืขื ืืืืึทื, ืืขืจ ืืขืืืืื ื ืึธืืข ืืื ืืขืคึฟืื ืขื! ืืึทืืืึทืืืง ืงืึธื:
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
ืืืื ืื ืงืจืึทื ื ืืืขืจื ื ืื, ืืขืืึธืื ืืขืจ ืืืื ืืื ืจืืืฉื ืื ืกืืฃ ืคืื ืื ืืืื (ืืื ืึท ืงืึทื ืกืขืคึผืืฉืืึทื ืืืจืื, ืืืจ ืืขื ื ืืื ืึท ื ืื-ืขืืืืกืืึทื ื ืึธืจื ืืื ืืขื ืืืื - ืึท ืึธืคึผืฉืืึทืืืื ื ืคืื ืึท ืืืึทื).
ืืื ืก ืืึทืืจืึทืืื ืื ืืคืขืงืืืืื ืึทืก ืคืื ืื ืืืื ืึทืืืขืจืืืึทื ืืืืฃ ืึท ืืึทืืึทื ืกื ืืืื (ืึท ืืืื ืืื ืืืึธืก ื ืึธืืื ืืขื ืขื ืคืื ืื ืืขืจืืขืืืืื ืืขืจ ืึธืืขืจ ืืืืื ืืงืขืจ ืืืืึทื ืื). ืืขืจื ืึธื ืื ืืืื ืขืคืขืงืืืืืงืืึทื ืืืขื ืืืื ืึธ (ืืึธื (n)), ืืื ืื ืืึธืืึทืจืืืื ืืื ืืึทืืข 2. ืงืืง: ืืืื ืขืก ืืขื ืขื n ืขืืขืืขื ืื ืืื ืึท ืืึทืืึทื ืกื ืืืื, ืืึธืก ืืืื ืึทื ืขืก ืืืขื ืืืื ืืึธื (n) ืฆื ืืึทืืข 2 ืืขืืืขืืก ืคืื ืื ืืืื. ืืื ืืื ืืืื, ืืื ืืืื ืฉืจืื ืคืื ืื ืฆืืงื, ืืืจ ืืืื ืึทืจืึธืคึผ ืืืื ืืืจืื.
Insert
ืืืื ืืืจ ืึธื ืืึทืคึผื ืื ืขืกืึทื ืก ืคืื ืื ืืืื, ืขืก ืืืขื ื ืืฉื ืืืื ืฉืืืขืจ ืฆื ืคึฟืึทืจืฉืืืื ืื ืื ืกืขืจืฉืึทื. ืืืจ ื ืึธืจ ืืึทืจืคึฟื ืฆื ืืืื ืึทืจืึธืคึผ ืฆื ืึท ืืืึทื ืคืื ืืขื ืืืื (ืืืื ืื ืึทืจืึธืคึผืืึทื ื ืึผืืืื ืืืกืงืจืืืื ืืื ืื ืืืื) ืืื ืืืขืจื ืืืึทื ืึธืคึผืฉืืึทืืืื ื - ืืื ืงืก ืึธืืขืจ ืจืขืื, ืืืคึผืขื ืืื ื ืืืืฃ ืื ืฉืืืกื. ืืืคึผืืึทืืขื ืืืืฉืึทื:
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
ืืื ืืขื ืคืึทื, ืืื ืึทืืืฉืึทื ืฆื ืืขื ืงืจืึทื ื ื ืึธืืข, ืขืก ืืื ื ืืืืืง ืฆื ืงืจืึธื ืืื ืคึฟืึธืจืืึทืฆืืข ืืืขืื ืื ืคืึธืืขืจ ืคืื ืืขื ืงืจืึทื ื ื ืึธืืข. ืืืขื ืงืจืึทื ื ืืืขืจื ืืืืึทื ืฆื ื ืึทื, ืื ืคืึธืืขืจ ืืืขืจืืึทืืึทืื ืืืขื ืึทื ืืืึทืืื ืืขื ืืืึทื ืืืึธืก ืืืจ ืืึทืจืคึฟื.
ืื ืขืคืขืงืืืืืงืืึทื ืคืื ืื ืกืขืจืฉืึทื ืืืขื ืืึธื ืืืื ืื ืืขืืืข ืืื ืึทื ืคืื ืืืื - ืึธ (ืืึธื (n)).
ืืึทืืืึทืืืงืื ื
ืืึทืืืึทืืืงืื ื ืืื ืื ืืขืจืกื ืฉืืืขืจ ืึธืคึผืขืจืึทืฆืืข ืืืึธืก ืืืขื ืืึทืจืคึฟื ืฆื ืืืื ืืขืืื ืืืืฃ ืึท ืืืื. ืขืก ืืื ืงืืึธืจ ืึทื ืขืจืฉืืขืจ ืืืจ ืืึทืจืคึฟื ืฆื ืืขืคึฟืื ืขื ืืขื ืขืืขืืขื ื ืืืึธืก ืืืจ ืืขื ืขื ืืขืืื ืืขื ืฆื ืืืกืืขืงื. ืึธืืขืจ ืืืึธืก ืืขืืึธืื? ืืืื ืืืจ ืคืฉืื ืฉืืขืื ืืืื ืจืขืคึฟืขืจืขื ืฅ ืฆื ื ืึทื, ืืืจ ืืืขืื ืคืึทืจืืืจื ืืื ืคึฟืึธืจืืึทืฆืืข ืืืขืื ืื ืกืืืืจืืข ืคืื โโืืืึธืก ืืขืจ ื ืึธืืข ืืื ืืขืจ ืืืึธืจืฆื. ืืืื ืืึทืืืึทืืืงืื ื ืืขืืืึธืืก ืืขื ืขื ืฆืขืืืืื ืืื ืืจืืึท ืงืึทืกืขืก.
ืขืจืฉืืขืจ ืคืึทื. ืืขืจ ื ืึธืืข ืืืึธืก ืืื ืืืืกืืขืืขืงื ืืื ืงืืื ืงืื ืืขืจ
ืืืื ืืขืจ ื ืึธืืข ืืืึธืก ืืื ืืืืกืืขืืขืงื ืืื ืงืืื ืงืื ืืขืจ, ืืึธืก ืืืื ืึทื ืขืก ืืื ืึท ืืืึทื. ืืขืจืืืขืจ, ืืืจ ืงืขื ืขื ืคืฉืื ืฉืืขืื ืื leftChild ืึธืืขืจ rightChild ืคืขืืืขืจ ืคืื ืืืื ืคืึธืืขืจ ืฆื ื ืึทื.
ืฆืืืืืืข ืคืื. ืืขืจ ื ืึธืืข ืฆื ืืืขืจื ืืืืกืืขืืขืงื ืืื ืืืื ืงืื ื
ืืขืจ ืคืึทื ืืื ืืืื ื ืืฉื ืืืืขืจ ืงืึธืืคึผืืืฆืืจื. ืืืืืจ ืืื ืืืืงืขืจื ืฆื ืืื ืืขืจ ืืืืฉืคืื. ืืื ืก ืืึธืื ืืืจ ืืึทืจืคึฟื ืฆื ืืืกืืขืงื ืึทื ืขืืขืืขื ื ืืื ืฉืืืกื 14. ืฉืืืืขื ืึทื ืืื ื ืขืก ืืื ืื ืจืขืื ืึธืคึผืฉืืึทืืืื ื ืคืื ืึท ื ืึธืืข ืืื ืฉืืืกื 10, ืืขืืึธืื ืงืืื ืคืื ืืืึทื ืงืื ืืกืงืื ืืขืจ (ืืื ืืขื ืคืึทื ืื ืจืขืื ืืืื ืขืจ) ืืืขื ืืึธืื ืึท ืฉืืืกื ืืจืขืกืขืจ ืืื 10, ืึทืืื ืืืจ ืงืขื ืขื ืืืืื "ืฉื ืืึทืื" ืขืก ืืืืก ืคืื ืื ืืืื, ืืื ืคืึทืจืืื ืื ืื ืคืึธืืขืจ ืืืืึทื ืฆื ืื ืงืื ื ืคืื ืื ื ืึธืืข ืืืึธืก ืืื ืืืืกืืขืืขืงื, ื"ื. ืคืึทืจืืื ืื ืื ื ืึธืืข ืืื ืฉืืืกื 10 ืฆื ื ืึธืืข 13. ืื ืกืืืืึทืฆืืข ืืืึธืื ืืืื ืขื ืืขื ืืืื ืขืก ืืื ื ืืืืืง ืฆื ืืืกืืขืงื ืึท ื ืึธืืข ืืืึธืก ืืื ืื ืืื ืงืก ืงืื ื ืคืื ืืืื ืคืึธืืขืจ. ืืจืึทืืื ืืืขืื ืืื ืืื - ืึทื ืคึผืื ืืืขื ืึทื ืึทืืึทืืืฉื.
ืืจืืื ืคืึทื. ื ื ืึธืืข ืืื ืฆืืืื ืงืื ืืขืจ
ืื ืืขืจืกื ืฉืืืขืจ ืคืึทื. ืืื ืก ืงืืง ืืืึท ืึท ื ืืึท ืืืึทืฉืคึผืื.
ืืืื ืคึฟืึทืจ ืึท ืกืึทืงืกืขืกืขืจ
ืืื ืก ืืึธืื ืืืจ ืืึทืจืคึฟื ืฆื ืืืกืืขืงื ืึท ื ืึธืืข ืืื ืฉืืืกื 25. ืืืขืจ ืืึธื ืืืจ ืฉืืขืื ืืื ืืืึทื ืึธืจื? ืืืื ืขืจ ืคืื ืืืื ืข ืื ืืขื ืืขืจืก (ืงืื ืืขืจ ืึธืืขืจ ืงืื ืืกืงืื ืืขืจ ืคืื ืงืื ืืกืงืื ืืขืจ) ืืืื ืืืขืจื ืกืึทืงืกืขืกืขืจ(ืืขืจ ืืืื ืขืจ ืืืืก ืืืขื ื ืขืืขื ืืขื ืึธืจื ืคืื ืื ื ืึธืืข ืืื ืึทืืืขืงืืขื ืืืขื).
ืืื ืฆื ืคึฟืึทืจืฉืืืื ืืืขืจ ืืึธื ืืืขืจื ืืขืจ ืกืึทืงืกืขืกืขืจ? ืื ืืืึทืืืืืื, ืืึธืก ืืื ืึท ื ืึธืืข ืืื ืืขื ืืืื ืืืขืืขื ืก ืฉืืืกื ืืื ืืขืจ ืืืืึทืืขืจ ืืจืขืกืืขืจ ืคืื ืื ื ืึธืืข ืืืึธืก ืืื ืืืืกืืขืืขืงื. ืื ืึทืืืขืจืืืึทื ืืื ืืื ืืืื. ืืข ืืึทืจืฃ ืืืื ืฆื ืืฒึทื ืจืขืืื ืึธืคึผืฉืืึทื (ืฉืืขื ืืืง ืฆืื ืจืขืืื, ืืืฒึทื ืืขื ืืึธื ืฉืืื ืืขืืึธืื, ืึทื ืืขืจ ืกืึทืงืกืขืกึพืฉืืืกื ืืื ืืจืขืกืขืจ ืืื ืืขืจ ืฉืืืกื ืคึฟืื ืืขื ื ืึธืืข, ืืืึธืก ืืข ืืืขืจื ืืืืกืืขืืขืงื), ืืื ืืขืจื ืึธื ืืืจืืืืื ืื ืงืืื ืคึฟืื ืืื ืงืข ืงืื ืืกืงืื ืืขืจ ืคึฟืื ืืขื ืจืขืืื ืึธืคึผืฉืืึทื. . ืืื ืืขื ืืืึทืฉืคึผืื, ืืืจ ืืืึธืื ืืืื ืฆื ืื ื ืึธืืข ืืื ืฉืืืกื 35, ืืื ืืึทื ืืืื ืึทืจืึธืคึผ ืฆื ืื ืืืึทื ืืืจื ืื ืงืืื ืคืื ืืืึทื ืืื ืงืก ืงืื ืืขืจ - ืืื ืืขื ืคืึทื, ืื ืงืืื ืืืฉืืืื ืืืืื ืคืื ืื ื ืึธืืข ืืื ืฉืืืกื 30. ืฉืืจืขื ื ืืขืจืขืื, ืืืจ ืงืืงื ืคึฟืึทืจ ืื ืงืืขื ืกืืขืจ ื ืึธืืข ืืื ืื ืืึทื ื ืคืื ื ืึธืืื ืืจืขืกืขืจ ืืื ืื ืืืึธืก ืืืจ ืืขื ืขื ืงืืงื ืคึฟืึทืจ ื ืึธืืข.
ืกืึทืงืกืขืกืขืจ ืืืื ืืขืืึธื ืงืึธื:
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;//ัะพะดะธัะตะปั ะฟัะตะตะผะฝะธะบะฐ
Node<T> successor = deleteNode;//ะฟัะตะตะผะฝะธะบ
Node<T> current = successor.getRightChild();//ะฟัะพััะพ "ะฟัะพะฑะตะณะฐััะธะน" ัะทะตะป
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
//ะฝะฐ ะฒัั
ะพะดะต ะธะท ัะธะบะปะฐ ะธะผะตะตะผ ะฟัะตะตะผะฝะธะบะฐ ะธ ัะพะดะธัะตะปั ะฟัะตะตะผะฝะธะบะฐ
if (successor != deleteNode.getRightChild()) {//ะตัะปะธ ะฟัะตะตะผะฝะธะบ ะฝะต ัะพะฒะฟะฐะดะฐะตั ั ะฟัะฐะฒัะผ ะฟะพัะพะผะบะพะผ ัะดะฐะปัะตะผะพะณะพ ัะทะปะฐ
parentSuccessor.setLeftChild(successor.getRightChild());//ัะพ ะตะณะพ ัะพะดะธัะตะปั ะทะฐะฑะธัะฐะตั ัะตะฑะต ะฟะพัะพะผะบะฐ ะฟัะตะตะผะฝะธะบะฐ, ััะพะฑั ะฝะต ะฟะพัะตัััั ะตะณะพ
successor.setRightChild(deleteNode.getRightChild());//ัะฒัะทัะฒะฐะตะผ ะฟัะตะตะผะฝะธะบะฐ ั ะฟัะฐะฒัะผ ะฟะพัะพะผะบะพะผ ัะดะฐะปัะตะผะพะณะพ ัะทะปะฐ
}
return successor;
}
ืืึทื ืฅ ืงืึธื ืคึฟืึทืจ ืื ืืืกืืขืงื ืืืคึฟื:
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;//ะ ะทะฐะฒะธัะธะผะพััะธ ะพั ัะพะณะพ, ัะฒะปัะตััั ะปะธ ัะดะฐะปัะตะผัะน ัะทะตะป ะปะตะฒัะผ ะธะปะธ ะฟัะฐะฒัะผ ะฟะพัะพะผะบะพะผ ัะฒะพะตะณะพ ัะพะดะธัะตะปั, ะฑัะปะตะฒัะบะฐั ะฟะตัะตะผะตะฝะฝะฐั isLeftChild ะฑัะดะตั ะฟัะธะฝะธะผะฐัั ะทะฝะฐัะตะฝะธะต true ะธะปะธ false ัะพะพัะฒะตัััะฒะตะฝะฝะพ.
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {//ะฟะตัะฒัะน ัะปััะฐะน
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {//ะฒัะพัะพะน ัะปััะฐะน
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {//ััะตัะธะน ัะปััะฐะน
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
ืื ืงืึทืืคึผืืขืงืกืืื ืงืขื ืขื ืืืื ืืขืจื ืขื ืืขืจื ืฆื O (ืืึธื (n)).
ืืขืคึฟืื ืขื ืืึทืงืกืืืื / ืืื ืืืื ืืื ืึท ืืืื
ืขืก ืืื ืงืืึธืจ ืืื ืืขืจ ืืึธื ืืื ืฆื ืืขืคึฟืื ืขื ืื ืืื ืืืื / ืืึทืงืกืืืื ืืืขืจื ืืื ืึท ืืืื - ืืืจ ืืึทืจืคึฟื ืฆื ืกืึทืงืืืขื ืืฉืึทืื ืืึทื ืฆืืืืืขื ืื ืงืืื ืคืื ืืื ืงืก / ืจืขืื ืขืืขืืขื ืื ืคืื ืืขื ืืืื, ืจืืกืคึผืขืงืืืืืื; ืืืขื ืืืจ ืืึทืงืืืขื ืฆื ืืขื ืืืึทื, ืขืก ืืืขื ืืืื ืื ืืื ืืืื / ืืึทืงืกืืืื ืขืืขืืขื ื.
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
ืงืึทืืคึผืืขืงืกืืื - ืึธ (ืืึธื (n))
ืกืึทืืขืืจืืงืึทื ืืืืคึผืึทืก
ืืจืึทืืืขืจืกืึทื ืืื ืืืืืื ืืขืืขืจ ื ืึธืืข ืคืื โโืืขื ืืืื ืืื ืกืืจ ืฆื ืืึธื ืขืืืขืืข ืงืึทืืฃ ืืื ืืื.
ืจืขืงืืจืกืืืืข ืกืืืืขืืจืืง ืืจืึทืืืขืจืกืึทื ืึทืืืขืจืืืึทื:
- ืืึธื ืึท ืงืึทืืฃ ืืืืฃ ืื ืืื ืงืก ืงืื ื
- ืืึธื ืึท ืงืึทืืฃ ืืื ืืื
- ืืึธื ืึท ืงืึทืืฃ ืืืืฃ ืื ืจืขืื ืงืื ื
ืงืึธื:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//ะะดะตัั ะผะพะถะตั ะฑััั ะฒัะต, ััะพ ัะณะพะดะฝะพ
inOrder(current.getRightChild());
}
}
ืกืึธืฃ
ืฆืื ืกืืฃ! ืืืื ืืื ืืึธืื ื ืืฉื ืืขืจืงืืขืจื ืขืคึผืขืก ืึธืืขืจ ืืึธืื ืงืืื ืืึทืืขืจืงืื ืืขื, ืืืืข ืืึธืื ืืื ืืื ืื ืืึทืืขืจืงืื ืืขื. ืืื ืฆืืืขืืืื, ืืื ืฆืืฉืืขืื ืื ืืึทื ืฅ ืงืึธื.
Node.java:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node<T> newNode) {
leftChild = newNode;
}
public void setRightChild(Node<T> newNode) {
rightChild = newNode;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.java:
public class BinaryTree<T> {
private Node<T> root;
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;
Node<T> successor = deleteNode;
Node<T> current = successor.getRightChild();
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
if (successor != deleteNode.getRightChild()) {
parentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(deleteNode.getRightChild());
}
return successor;
}
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
ืคึผืก
ืืืืืฉืขื ืขืจืืืฉืึทื ืฆื O (n)
ืคืืืข ืคืื โโโโืืืจ ืงืขื ืืึธืื ืืืืขืจืงื: ืืืึธืก ืืืื ืืืจ ืืึทืื ืืขื ืืืื ืึทื ืืึทืืึทื ืกื? ืคึฟืึทืจ ืืืึทืฉืคึผืื, ืฉืืขืื ื ืึธืืื ืืื ืื ืงืจืืกืื ื ืฉืืืกืืขื ืืื ืึท ืืืื: 1,2,3,4,5,6 ... ืืขืืึธืื ืืขืจ ืืืื ืืืขื ืขืคึผืขืก ืจืืืขืืืึทื ืึท ืืื ืืงื ืจืฉืืื. ืืื ืืึธ, ืืขืจ ืืืื ืืืขื ืคืึทืจืืืจื ืืืึทื ืืืื ืกืืจืืงืืืจ, ืืื ืืขืจืืืขืจ ืื ืขืคืขืงืืืืืงืืึทื ืคืื ืืึทืื ืึทืงืกืขืก. ืื ืงืึทืืคึผืืขืงืกืืื ืคืื ืืืื, ืื ืกืขืจืฉืึทื, ืืื ืืืืืฉืึทื ืึทืคึผืขืจืืืฉืึทื ื ืืืขื ืืืขืจื ืื ืืขืืืข ืืื ืึทื ืคืื ืึท ืืื ืืงื ืจืฉืืื: O(n). ืืึธืก ืืื ืืืื ืขืจ ืคืื ืื ืืขืจืกื ืืืืืืืง, ืืื ืืืื ืืืื ืื ื, ืืืกืึทืืืืึทื ืืืืืฉืื ืคืื ืืืื ืขืจื ืืืืืขืจ.
ืืืืื ืจืขืืืกืืจืืจื ื ืืฆืขืจืก ืงืขื ืขื ืึธื ืืืื ื ืขืืขื ืืื ืื ืืืขืจืืืืง. ืืืืข.
ืืื ืืื ื ืืฉื ืืขืืืขื ืืืืฃ ืื ืืึทื ืคึฟืึทืจ ืืืืขืจ ืืึทื ื, ืืื ืืื ืืืึธืื ืืื ืฆื ืืืืกื ืืืึธืก ืึทืจืืืงืืขื ืืืขืื ืืืึธืก ืืขืืขืก ืืืึธืื ืืืจ ืืื ืฆื ืืขื ืืขืจ?
-
ืืึทืืึท ืกืืจืึทืงืืฉืขืจื
-
ืึทืืืขืจืืืึทืื (ืืคึผ, ืจืขืงืืจืกืืึธื, ืืึทืื ืงืึทืืคึผืจืขืฉืึทื, ืืื"ื ื)
-
ืึทืคึผืคึผืืืงืึทืืืึธื ืคืื ืืึทืื ืกืืจืึทืงืืฉืขืจื ืืื ืึทืืืขืจืืืึทืื ืืื ืคืึทืงืืืฉ ืืขืื
-
ืคึผืจืึธืืจืึทืืืื ื ืึทื ืืจืืื ืึทืคึผืืึทืงืืืฉืึทื ื ืืื ื'ืืื
-
ืคึผืจืึธืืจืึทืืืื ื ืืืขื ืึทืคึผืืึทืงืืืฉืึทื ื ืืื Java
2 ืืืืขืจื ืืืึธืืืึทื. 1 ืืื ืืฆืขืจ ืืื ืืื ืืคืืขืืืืื.
ืืงืืจ: www.habr.com