ツリーjavaコード実装
84471 ワード
package com.ccnu.edu.cn;
import java.util.ArrayDeque;
import java.util.Comparator;
/**
* Created by on 2017/12/3.
*
* compare ， SortClassImpl ， _compare(), ， _compare()
*/
public class BinarySearchTree<K, V> extends SortClassImpl<K> {
private Comparator extends K> comparator;
//
private int count;
//
private Node<K, V> root;
//
// count ， ,
private Node<K, V>[] datas;
private Object[] data;
private int index;
// ，
private class Node<K, V> {
private K key;
private V value;
private Node<K, V> leftChild;
private Node<K, V> rightChild;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
public BinarySearchTree() {
this.comparator = null;
}
//
public BinarySearchTree(Comparator extends K> comparator) {
this.comparator = comparator;
}
public int getCount() {
return count;
}
/**
* key
*
* @return
*/
public Object[] getKeys() {
data = new Object[count];
if (datas.length > 0) {
for (int i = 0; i < count; i++) {
data[i] = datas[i].key;
}
}
return data;
}
/**
* value
*
* @return
*/
public Object[] getValues() {
data = new Object[count];
if (datas.length > 0) {
for (int i = 0; i < count; i++) {
data[i] = datas[i].value;
}
}
return data;
}
/**
*
*
* @param key
* @param value
*/
public void insert(K key, V value) {
root = _insert(root, key, value);
}
/**
* ，
*
* @param key
* @param value
*/
public void insert1(K key, V value) {
root = _insert1(root, key, value);
}
/**
* key
*
* @param key
* @return
*/
public boolean containKeys(K key) {
boolean flag = _containKeys(root, key);
return flag;
}
/**
* key value
*
* @param key
* @return
*/
public V getValue(K key) {
if (!_containKeys(root, key))
throw new RuntimeException("Binary search tree don't have key");
return _getValue(root, key);
}
/**
* 、 、 , 。
*/
public void tranverse(int i) {
datas = new Node[count];
index = 0;
if (i == 0)
//
_preOrder(root);
else if (i == 1)
//
_middleOrder(root);
else if (i == 2)
//
_afterOrder(root);
}
/**
* ，
*
* @return
*/
public Node<K, V> getMaxKeyNode() {
if (root != null)
return _getMaxKeyNode(root);
else
return null;
}
/**
*
*
* @return
*/
public Node<K, V> getMinKeyNode() {
if (root == null)
return null;
return _getMinKeyNode(root);
}
public Node<K, V> removeMaxNode() {
return _removeMaxNode(root);
}
public Node<K, V> removeMinNode() {
return _removeMinNode(root);
}
public Node<K, V> removeKey(K key) {
return _removeKey(root, key);
}
/**
* node key ， node
* ， ， ， .
*
* @param node
* @param key
* @return
*/
private Node<K, V> _removeKey(Node<K, V> node, K key) {
if (_compare(key, node.key) == 1) {
node.rightChild = _removeKey(node.rightChild, key);
return node;
} else if (_compare(key, node.key) == -1) {
node.leftChild = _removeKey(node.leftChild, key);
return node;
} else {
if (node.leftChild == null) {
count--;
return node.rightChild;
}
if (node.rightChild == null) {
count--;
return node.leftChild;
}
// ， ，
//
Node<K, V> rootNode = _getMinKeyNode(node.rightChild);
rootNode.leftChild = node.leftChild;
rootNode.rightChild = _removeMinNode(node.rightChild);
count--;
return rootNode;
}
}
/**
* node ， ， node
*
* @param node
* @return
*/
private Node<K, V> _removeMaxNode(Node<K, V> node) {
if (node.rightChild == null) {
count--;
return node.leftChild;
}
// ，
node.rightChild = _removeMaxNode(node.rightChild);
return node;
}
/**
* node ， ， node
*
* @param node
* @return
*/
private Node<K, V> _removeMinNode(Node<K, V> node) {
if (node.leftChild == null) {
count--;
return node.rightChild;
}
node.leftChild = _removeMinNode(node.leftChild);
return node;
}
/**
* node , node ，
*
* @param node
* @return
*/
private Node<K, V> _getMaxKeyNode(Node<K, V> node) {
if (node.rightChild == null)
return node;
else
return _getMaxKeyNode(node.rightChild);
}
/**
* node , node ，
*
* @param node
* @return
*/
private Node<K, V> _getMinKeyNode(Node<K, V> node) {
if (node.leftChild == null)
return node;
return _getMinKeyNode(node.leftChild);
}
/**
* node ，
*
* @param node
*/
private void _middleOrder(Node<K, V> node) {
if (node == null)
return;
_middleOrder(node.leftChild);
datas[index++] = node;
_middleOrder(node.rightChild);
}
/**
* node
*
* @param node
*/
private void _preOrder(Node<K, V> node) {
if (node == null)
return;
datas[index++] = node;
_preOrder(node.leftChild);
_preOrder(node.rightChild);
}
/**
* node
*
* @param node
*/
private void _afterOrder(Node<K, V> node) {
if (node == null)
return;
_afterOrder(node.leftChild);
_afterOrder(node.rightChild);
datas[index++] = node;
}
/**
* ，
*/
public void transLevel() {
// ，
ArrayDeque<Node<K, V>> queue = new ArrayDeque();
// ，
datas = new Node[count];
//
queue.addLast(root);
while (!queue.isEmpty()) {
Node<K, V> head = queue.getFirst();
datas[index++] = queue.pop();
if (head.leftChild != null)
queue.addLast(head.leftChild);
if (head.rightChild != null)
queue.addLast(head.rightChild);
}
}
/**
* node ， key value
*
* @param node
* @param key
* @return
*/
private V _getValue(Node<K, V> node, K key) {
if (_compare(node.key, key) == 0)
return node.value;
//
if (_compare(node.key, key) == 1)
return _getValue(node.leftChild, key);
else
return _getValue(node.rightChild, key);
}
/**
* node ， key
*
* @param node
* @param key
* @return
*/
private boolean _containKeys(Node<K, V> node, K key) {
if (node == null)
return false;
//
if (_compare(node.key, key) == 1)
return _containKeys(node.leftChild, key);
//
else if (_compare(node.key, key) == -1)
return _containKeys(node.rightChild, key);
else
return true;
}
/**
* ，
*
* @param key
* @param value
*/
private Node<K, V> _insert1(Node<K, V> root, K key, V value) {
//
Node<K, V> newNode = new Node<>(key, value);
//
Node<K, V> currentNode = root;
// ， ， currentNode null ，
Node<K, V> parentNode = root;
if (root == null) {
count++;
root = newNode;
} else {
// ， currentNode == null，
while (currentNode != null) {
parentNode = currentNode;
if (_compare(currentNode.key, key) == 1)
currentNode = currentNode.leftChild;
else if (_compare(currentNode.key, key) == -1)
currentNode = currentNode.rightChild;
else {
currentNode.key = key;
break;
}
}
if (currentNode == null) {
count++;
if (_compare(parentNode.key, key) == 1)
parentNode.leftChild = newNode;
else
parentNode.rightChild = newNode;
}
}
//
return root;
}
/**
* ，
*
* node
*
* @param node
* @param key
* @param value
* @return
*/
private Node<K, V> _insert(Node<K, V> node, K key, V value) {
//
Node<K, V> newNode = new Node<>(key, value);
if (node == null) {
count++; // ，
return newNode;
}
if (_compare(node.key, key) == -1)
node.rightChild = _insert(node.rightChild, key, value);
else if (_compare(node.key, key) == 1)
node.leftChild = _insert(node.leftChild, key, value);
else {
node.key = key;
return node;
}
return node;
}
}