数据结构与算法——二叉树
1、概念
- 父节点：当前节点的上一个节点
- 子节点：当前节点的下一个节点（二叉树有左右两个子节点）
- 兄弟节点：拥有同一个父节点的若干节点
- 根节点：没有父节点的节点
- 叶子节点：没有子节点的节点
- 层：根节点的层数为1，子节点的层数为2，以此类推
- 高度：最底层叶子节点的高度为0，父节点所在层高度为1，以此类推
- 深度：高度的逆序，根节点深度为0，子节点深度为1，以此类推
2、特殊类型
- 满二叉树：除了叶子节点，每个节点都有左右两个子节点
- 完全二叉树：除了最后一个非叶子节点的子节点可能只有左节点（也可能左右节点都有，但不可能只有右节点），其他非叶子节点都有左右两个子节点
- 二叉查找树：每个节点的左节点都小于他，右节点都大于他
- 平衡二叉查找树：任何节点的左右子树高度不超过1，典型的有AVL树、红黑树等
- 堆：是一颗完全二叉树，大顶堆的每个节点都大于他的左右子节点，小顶堆的每个节点都小于他的左右子节点
3、二叉查找树
public class BinarySearchTree<E> {
private static class TreeNode<E> {
private int key;
private E data;
public TreeNode(int key, E data) {
this.key = key;
this.data = data;
}
}
private int size = 1;
//底层用数组存储而不是用链表，是为了节省内存
TreeNode<E>[] treeNodes;
/**
* 数组最大容量，-8是因为数组对象的头中_length存的数组长度正好8位
*/
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
public BinarySearchTree(int initialCapacity) {
this.treeNodes = new TreeNode[initialCapacity + 1];
}
/**
* 获取指定key的对象
*/
public E get(int key) {
int i = 1;
while (i < treeNodes.length) {
final TreeNode<E> treeNode = treeNodes[i];
if (treeNode == null) {
//没有子节点了
return null;
} else if (key == treeNode.key) {
//key相同说明当前节点就是要找的对象
return treeNode.data;
} else if (key < treeNode.key) {
//key比当前节点小，说明要找的对象在左子树
i = i * 2;
} else {
//比当前节点大，说明要找的节点在右子树
i = i * 2 + 1;
}
}
return null;
}
/**
* 添加元素
*/
public void set(int key, E element) {
int i = 1;
while (i < treeNodes.length) {
final TreeNode<E> treeNode = treeNodes[i];
if (treeNode == null) {
break;
} else if (key == treeNode.key) {
treeNode.data = element;
return;
} else if (key < treeNode.key) {
i = i * 2;
} else {
i = i * 2 + 1;
}
}
if (i > treeNodes.length - 1) {
grow(i + 1);
}
treeNodes[i] = new TreeNode<>(key, element);
size++;
}
/**
* 移除元素
*/
public E remove(int key) {
if (size <= 1) {
return null;
}
int i = 1;
TreeNode<E> removeTreeNode = null;
while (i < treeNodes.length) {
removeTreeNode = treeNodes[i];
if (key == removeTreeNode.key) {
i = i * 2;
} else if (key > removeTreeNode.key) {
i = i * 2 + 1;
} else {
break;
}
}
//先找到key对应的节点所在的位置
int j = i;
//然后在左子树找到最小的节点
while (treeNodes[j * 2] != null) {
j *= 2;
}
//用左子树的最小节点覆盖被移除的节点，没有左子树就直接移除
treeNodes[i] = j != i ? treeNodes[j] : null;
size--;
return removeTreeNode.data;
}
/**
* 扩容
*/
private void grow(int minCapacity) {
int oldCapacity = treeNodes.length;
//扩容为原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0) {
//扩容后还是达不到需要的最小容量，那干脆就不扩容1.5倍了，直接设置成需要的最小容量
newCapacity = minCapacity;
}
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (minCapacity < 0) {
//需要的最小容量是负的，说明溢出了
new OutOfMemoryError();
}
//如果需要的最小容量比原始的系统上限还大，那就配成Integer的最大值
newCapacity = minCapacity > MAX_ARRAY_SIZE ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
treeNodes = Arrays.copyOf(treeNodes, newCapacity);
}
/**
* 前序遍历，本节点->左节点->右节点
*/
public void preorderTraversal() {
System.out.println("==========");
if (size <= 1) {
return;
}
preorderTraversal(1);
System.out.println("==========");
}
private void preorderTraversal(int parentIndex) {
int leftIndex = parentIndex * 2;
if (parentIndex < treeNodes.length && treeNodes[parentIndex] != null) {
System.out.println(treeNodes[parentIndex].key + ":" + treeNodes[parentIndex].data);
}
if (leftIndex < treeNodes.length && treeNodes[leftIndex] != null) {
preorderTraversal(leftIndex);
}
int rightIndex = parentIndex * 2 + 1;
if (rightIndex < treeNodes.length && treeNodes[rightIndex] != null) {
preorderTraversal(rightIndex);
}
}
/**
* 中序遍历，左节点->本节点->右节点
*/
public void inorderTraversal() {
System.out.println("==========");
if (size <= 1) {
return;
}
inorderTraversal(1);
System.out.println("==========");
}
private void inorderTraversal(int parentIndex) {
int leftIndex = parentIndex * 2;
if (leftIndex < treeNodes.length && treeNodes[leftIndex] != null) {
preorderTraversal(leftIndex);
}
if (parentIndex < treeNodes.length && treeNodes[parentIndex] != null) {
System.out.println(treeNodes[parentIndex].key + ":" + treeNodes[parentIndex].data);
}
int rightIndex = parentIndex * 2 + 1;
if (rightIndex < treeNodes.length && treeNodes[rightIndex] != null) {
preorderTraversal(rightIndex);
}
}
/**
* 后序遍历，左节点->右节点->本节点
*/
public void postorderTraversal() {
System.out.println("==========");
if (size <= 1) {
return;
}
postorderTraversal(1);
System.out.println("==========");
}
private void postorderTraversal(int parentIndex) {
int leftIndex = parentIndex * 2;
if (leftIndex < treeNodes.length && treeNodes[leftIndex] != null) {
preorderTraversal(leftIndex);
}
int rightIndex = parentIndex * 2 + 1;
if (rightIndex < treeNodes.length && treeNodes[rightIndex] != null) {
preorderTraversal(rightIndex);
}
if (parentIndex < treeNodes.length && treeNodes[parentIndex] != null) {
System.out.println(treeNodes[parentIndex].key + ":" + treeNodes[parentIndex].data);
}
}
}
4、堆
以大顶堆为例
public class MyBigTopHeap<E> {
public static class TreeNode<E> {
private int key;
private E data;
public int getKey() {
return key;
}
public TreeNode(int key, E data) {
this.key = key;
this.data = data;
}
}
private int size = 1;
TreeNode<E>[] treeNodes;
public MyBigTopHeap(int initialCapacity) {
this.treeNodes = new TreeNode[initialCapacity + 1];
}
public MyBigTopHeap(TreeNode<E>[] arr) {
this.treeNodes = arr;
this.size = arr.length-1;
}
/**
* 数组最大容量，-8是因为数组对象的头中_length存的数组长度正好8位
*/
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 插入元素
*/
public void set(int key, E element) {
if (size >= treeNodes.length) {
grow(size);
}
treeNodes[size++] = new TreeNode<>(key, element);
heapifyFromBottomToTop(size - 1);
}
/**
* 移除元素
*/
public E remove(int key) {
//找到匹配的节点
final int keyIndex = findKeyIndex(key, 1);
if (keyIndex == 0) {
return null;
}
E element = treeNodes[keyIndex].data;
//通过把尾结点覆盖到当前节点，来移除当前节点
treeNodes[keyIndex] = treeNodes[size - 1];
//这时候有两个相同节点，把尾结点移除
treeNodes[--size] = null;
heapifyFromBottomToTop(size - 1);
return element;
}
/**
* 获取元素
*/
public E get(int key) {
final int keyIndex = findKeyIndex(key, 1);
return keyIndex == 0 ? null : treeNodes[keyIndex].data;
}
private int findKeyIndex(int key, int startIndex) {
if (startIndex >= size || treeNodes[startIndex] == null) {
return 0;
}
if (key == treeNodes[startIndex].key) {
//当前节点匹配，直接返回数据
return startIndex;
} else if (key < treeNodes[startIndex].key) {
//给定key比当前节点key要小，说明子树中依然有可能找到对应key
//先找左子树
final int leftIndex = findKeyIndex(key, startIndex * 2);
//左子树没找到再找右子树
return leftIndex != 0 ? leftIndex : findKeyIndex(key, startIndex * 2 + 1);
}
//当前节点已经比给定key小了还没找到，子树中的所有节点都比给定key小，所以再找也没有意义，直接返回空
return 0;
}
/**
* 自底向上堆化
* 其实就是将某个节点一直向父节点交换，直到找到符合的位置（父节点比自己大，子节点比自己小）
*/
public void heapifyFromBottomToTop(int startIndex) {
while (startIndex > 1) {
int i = startIndex;
while (i > 1){
int parentIndex = i / 2;
if (treeNodes[i].key > treeNodes[parentIndex].key) {
//如果当前节点比父节点大，就交换
TreeNode<E> startNode = treeNodes[i];
treeNodes[i] = treeNodes[parentIndex];
treeNodes[parentIndex] = startNode;
}
i/=2;
}
//从底层逆序遍历
startIndex--;
}
}
/**
* 自顶向下堆化
* 其实就是将某个节点一直跟子节点的最大值交换，直到找到符合的位置（父节点比自己大，子节点比自己小）
*/
public void heapifyFromTopToBottom(int startIndex) {
while (startIndex >= 1) {
int i = startIndex;
while (i*2 <= size){
//进来就说明至少有一个左子节点，可以比较交换
final int startKey = treeNodes[i].key;
int leftChildIndex = i * 2;
final int leftKey = treeNodes[leftChildIndex].key;
int rightChildIndex = leftChildIndex+1;
boolean hasRightChild = rightChildIndex < size && treeNodes[rightChildIndex] != null;
int tempIndex;
if (hasRightChild) {
//有右节点，则从左、右、自己三个节点中选出最大的节点放到自己的位置
final int rightKey = treeNodes[rightChildIndex].key;
final int maxKey = Math.max(Math.max(leftKey, rightKey), startKey);
tempIndex = maxKey == startKey ? i : maxKey == leftKey ? leftChildIndex : rightChildIndex;
}else {
//没有右节点，则从左节点和自己中选出最大的节点，放到自己的位置
final int maxKey = Math.max(leftKey, startKey);
tempIndex = maxKey == startKey ? i : leftChildIndex;
}
if(i== tempIndex){
//交换节点就是自己，那就不交换了
break;
}
TreeNode<E> startNode = treeNodes[i];
treeNodes[i] = treeNodes[tempIndex];
treeNodes[tempIndex] = startNode;
i=tempIndex;
}
//从底层逆序遍历
startIndex--;
}
}
/**
* 排序
*/
public void sort() {
heapifyFromTopToBottom(size/2);
for (int i = treeNodes.length - 1; i > 1; i--) {
final TreeNode<E> treeNode = treeNodes[i];
treeNodes[i] = treeNodes[1];
treeNodes[1] = treeNode;
heapifyFromBottomToTop(i - 1);
}
}
/**
* 扩容
*/
private void grow(int minCapacity) {
int oldCapacity = treeNodes.length;
//扩容为原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0) {
//扩容后还是达不到需要的最小容量，那干脆就不扩容1.5倍了，直接设置成需要的最小容量
newCapacity = minCapacity;
}
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (minCapacity < 0) {
//需要的最小容量是负的，说明溢出了
new OutOfMemoryError();
}
//如果需要的最小容量比原始的系统上限还大，那就配成Integer的最大值
newCapacity = minCapacity > MAX_ARRAY_SIZE ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
treeNodes = Arrays.copyOf(treeNodes, newCapacity);
}
}
5、红黑树
后面回来补
扫一扫
3172
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
