用dart语言实现的二叉树，实现了插入、查找、删除，中序遍历、前序、后序遍历等功能。
class BinaryTree<E extends Comparable> {
Node<E> _root;
int _nodeNumbers;
BinaryTree() : _nodeNumbers = 0;
factory BinaryTree.from(Iterable<E> elements) {
var tree = BinaryTree<E>();
for (var e in elements) tree.insert(e);
return tree;
}
bool get isEmpty => _root == null;
int get nodeNumbers => _nodeNumbers;
void clear() {
_root = null;
_nodeNumbers = 0;
}
bool delete(E value) {
var deleted = find(value);
if (deleted == null) return false;
_delete(deleted);
_nodeNumbers--;
return true;
}
Node<E> find(E value) {
var current = _root;
while (current != null) {
var c = value.compareTo(current.value);
if (c == 0) break;
current = c < 0 ? current.leftChild : current.rightChild;
}
return current;
}
void insert(E value) {
var inserted = Node(value);
if (isEmpty) {
_root = inserted;
} else {
var current = _root;
while (current != null) {
if (value.compareTo(current.value) <= 0) {
if (current.leftChild == null) {
current.leftChild = inserted;
inserted.parent = current;
break;
} else {
current = current.leftChild;
}
} else {
if (current.rightChild == null) {
current.rightChild = inserted;
inserted.parent = current;
break;
} else {
current = current.rightChild;
}
}
}
}
_nodeNumbers++;
}
void traverse(void func(E value), [TraverseOrder order]) {
_traverse(_root, order, func);
}
E get max {
if (isEmpty) throw TreeEmptyException();
var maxNode = _root;
while (maxNode.rightChild != null) maxNode = maxNode.rightChild;
return maxNode.value;
}
E get min {
if (isEmpty) throw TreeEmptyException();
return _minNode(_root).value;
}
Node<E> _minNode(Node<E> root) {
var minNode = root;
while (minNode.leftChild != null) minNode = minNode.leftChild;
return minNode;
}
void _delete(Node<E> deleted) {
var successor = _successor(deleted);
if (successor != null) _delete(successor);
if (deleted == _root) _root = successor;
_replace(deleted, successor);
}
static void _replace<E>(Node<E> deleted, Node<E> successor) {
if (deleted.parent != null) {
if (deleted.parent.leftChild == deleted)
deleted.parent.leftChild = successor;
else
deleted.parent.rightChild = successor;
}
if (successor != null) {
successor.parent = deleted.parent;
successor.leftChild = deleted.leftChild;
successor.rightChild = deleted.rightChild;
if (deleted.leftChild != null) deleted.leftChild.parent = successor;
if (deleted.rightChild != null) deleted.rightChild.parent = successor;
}
}
Node<E> _successor(Node<E> node) =>
node.rightChild != null ? _minNode(node.rightChild) : node.leftChild;
static void _traverse<E>(Node<E> root, TraverseOrder order, void func(E e)) {
if (root == null) return;
switch (order) {
case TraverseOrder.preOrder:
func(root.value);
_traverse(root.leftChild, order, func);
_traverse(root.rightChild, order, func);
break;
case TraverseOrder.postOrder:
_traverse(root.leftChild, order, func);
_traverse(root.rightChild, order, func);
func(root.value);
break;
default:
_traverse(root.leftChild, order, func);
func(root.value);
_traverse(root.rightChild, order, func);
}
}
}
enum TraverseOrder { preOrder, inOrder, postOrder }
class Node<E> {
E value;
Node<E> parent, leftChild, rightChild;
Node(this.value);
}
class TreeEmptyException implements Exception {
const TreeEmptyException();
String toString() => 'TreeEmptyException';
}