二叉树
每个节点最多含有两个子树的树称为二叉树。
二叉树的性质：
- 在非空二叉树中，第i层的节点数不超过2 i-1，i>=1；
- 深度为h的二叉树最多有2 i -1个节点，最少有h个节点，h>=1；
- 对于任意一颗二叉树，如果其叶子节点数为N，而度数为2的节点总数为M，则N=M+1；
其中又分为满二叉树和完全二叉树
- 满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上。
完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。
image.png
完全二叉树是效率很高的数据结构，堆是一种完全二叉树或近似完全二叉树。
/**
* 二叉树
*/
public class BinaryTree<E> {
public BinaryTree(){}
/**
* 循环构建二叉树
*/
private Node<E> buildBinaryTree(E[] array) {
List<Node<E>> nodes = new ArrayList<>(array.length);
for (E value:array){
nodes.add(new Node<>(value));
}
for (int i = 0; i < array.length/2; i++) {
//左孩子
if ((2*i+1)<array.length){
nodes.get(i).setLeftChild(nodes.get(2*i+1));
}
//右孩子
if ((2*i+1)<array.length){
nodes.get(i).setRightChild(nodes.get(2*i+2));
}
}
return nodes.get(0);
}
/**
* 递归构造二叉树
*/
public Node<E> buildBinaryTree(E[] array,int index){
if(index>=array.length){
return null;
}
Node<E> node = new Node<>(array[index]);
if(index*2+1<array.length){
node.setLeftChild(buildBinaryTree(array,index*2+1));
}
if (index*2+2<array.length){
node.setRightChild(buildBinaryTree(array,index*2+2));
}
return node;
}
/**
* 先序遍历（先根节点->遍历左子树->遍历右子树）
* [1,2,4,8,9,5,3,6,7]
*/
public void preOrderTraverse(Node<E> node){
if (node==null){
return;
}
System.out.print(node.getValue()+",");
preOrderTraverse(node.getLeftChild());
preOrderTraverse(node.getRightChild());
}
/**
* 中序遍历（遍历左子树->根节点->遍历右子树）
* [8,4,9,2,5,1,6,3,7]
*/
public void inOrderTraverse(Node<E> node){
if (node==null){
return;
}
inOrderTraverse(node.getLeftChild());
System.out.print(node.getValue()+",");
inOrderTraverse(node.getRightChild());
}
/**
* 后序遍历（遍历左子树->遍历右子树->根节点）
* [7,6,3,5,9,8,4,2,1]
*/
public void postOrderTraverse(Node<E> node){
if (node==null){
return;
}
postOrderTraverse(node.getRightChild());
postOrderTraverse(node.getLeftChild());
System.out.print(node.getValue()+",");
}
/**
* 深度优先搜索
* 简称DFS，其原则是，沿着一条路径一直找到最深的那个节点，
* 当没有子节点的时候，返回上一级节点，寻找其另外的子节点，
* 继续向下遍历，没有就向上返回一级，直到所有的节点都被遍历到，
* 每个节点只能访问一次。
* [1,2,4,8,9,5,3,6,7]
* 非递归
*/
public void depthOrderTraversal(Node<E> root){
Stack<Node<E>> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
Node<E> node = stack.pop();
System.out.print(node.getValue()+",");
if (node.getRightChild()!=null){
stack.push(node.getRightChild());
}
if (node.getLeftChild()!=null){
stack.push(node.getLeftChild());
}
}
}
/**
* 广度优先搜索
* 简称BFS；广度优先遍历的原则就是对每一层的节点依次访问，
* 一层访问结束后，进入下一层，直到最后一个节点，
* 同样的，每个节点都只访问一次。
* [1,2,3,4,5,6,7,8,9]
* 非递归
*/
public void levelOrderTraversal(Node<E> root){
Queue<Node<E>> queue = new LinkedBlockingQueue();
queue.add(root);
while (!queue.isEmpty()){
Node<E> node = queue.remove();
System.out.print(node.getValue()+",");
if (node.getLeftChild()!=null){
queue.add(node.getLeftChild());
}
if (node.getRightChild()!=null){
queue.add(node.getRightChild());
}
}
}
/**
* 深度优先遍历
* 递归
*/
public void dfs(Node<E> root){
if (root==null){
return;
}
System.out.print(root.getValue()+",");
dfs(root.leftChild);
dfs(root.rightChild);
}
/**
* 获取树的深度
*/
public int getDepth(Node node){
if (node==null){
return 0;
}
return 1+(getDepth(node.getLeftChild())>getDepth(node.getRightChild())?getDepth(node.getLeftChild()):getDepth(node.getRightChild()));
}
static class Node<E>{
private E value;
private Node<E> leftChild;
private Node<E> rightChild;
public Node(E e){
value = e;
}
public E getValue() {
return value;
}
public void setValue(E value) {
this.value = value;
}
public Node<E> getLeftChild() {
return leftChild;
}
public void setLeftChild(Node<E> leftChild) {
this.leftChild = leftChild;
}
public Node<E> getRightChild() {
return rightChild;
}
public void setRightChild(Node<E> rightChild) {
this.rightChild = rightChild;
}
}
}
排序二叉树
二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它根节点的值
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它根节点的值
- 没有键值相等的节点
- 对二叉查找树进行中序遍历，即可得到有序的数列
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低为 O ( log n )
/**
* 二叉查找树（排序二叉树）
*/
public class BinarySearchTree {
Node root;
public Node getRoot(){
return root;
}
/**
* 通过数组构造二叉排序树
*/
public void buildBinarySearchTree(int[] array){
root = new Node(array[0]);
for (int i = 1; i < array.length; i++) {
Node child = new Node(array[i]);
buildBinarySearchTree(root,child);
}
}
/**
* 向排序二叉树中插入一个节点
*/
public void buildBinarySearchTree(int value){
Node node = new Node(value);
buildBinarySearchTree(node);
}
/**
* 递归构造二叉排序树
*/
private void buildBinarySearchTree(Node parent,Node child){
//右子树
if (child.getValue()>parent.getValue()){
if (parent.getRight()==null){
parent.setRight(child);
return;
}else{
buildBinarySearchTree(parent.getRight(),child);
}
}
//左子树
if(child.getValue()<parent.getValue()){
if (parent.getLeft()==null){
parent.setLeft(child);
return;
}else{
buildBinarySearchTree(parent.getLeft(),child);
}
}
}
/**
* 非递归构造排序二叉树
*/
private void buildBinarySearchTree(Node node){
if (root==null){
root = node;
return;
}
Node parent = root;
while (true){
//右子树
if (node.getValue()>parent.getValue()){
if (parent.getRight()==null){
parent.setRight(node);
return;
}else{
parent = parent.getRight();
continue;
}
}
//左子树
if (node.getValue()<parent.getValue()){
if (parent.getLeft()==null){
parent.setLeft(node);
return;
}else{
parent = parent.getLeft();
continue;
}
}
}
}
/**
* 中序遍历
*/
public void inOrderTraverse(Node root){
if (root==null){
return;
}
inOrderTraverse(root.getLeft());
System.out.print(root.getValue()+",");
inOrderTraverse(root.getRight());
}
/**
* 获取树的深度
*/
public int getDepth(Node root){
if (root==null){
return 0;
}
return 1+(getDepth(root.getRight())>getDepth(root.getLeft())?getDepth(root.getRight()):getDepth(root.getLeft()));
}
/**
* 查找值
*/
public boolean find(int value){
Node parent = root;
while (parent!=null){
if (value==parent.getValue()){
return true;
}else if (value>parent.getValue()){
parent = parent.getRight();
}else if (value<parent.getValue()){
parent = parent.getLeft();
}
}
return false;
}
/**
* 二叉树节点
*/
static class Node{
int value;
Node left;
Node right;
public Node(int value){
this.value = value;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
}
平衡二叉树
当且仅当任何节点的两棵子树的高度差不大于1的二叉树。其中AVL树是最先发明的自平衡二叉查找树，是最原始典型的平衡二叉树。
平衡二叉树是基于二叉查找树的改进。由于在某些极端的情况下（如在插入的序列是有序的时），二叉查找树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。所以我们通过自平衡操作（即旋转）构建两个子树高度差不超过1的平衡二叉树。
/**
* 平衡二叉树
*/
public class BalancedBinaryTree {
Node root;
public Node getRoot(){
return root;
}
public void insert(int value){
if (null==root){
root = new Node(value);
}else {
insert(root,new Node(value));
}
}
/**
* 插入节点
*/
private void insert(Node parent,Node child){
//查找右节点
if (child.getValue()>parent.getValue()){
if (parent.getRight()==null){
parent.setRight(child);
}else {
insert(parent.getRight(),child);
//回溯的时候平衡树
balance(parent);
}
}
//查找做节点
if (child.getValue()<parent.getValue()){
if (parent.getLeft()==null){
parent.setLeft(child);
}else {
insert(parent.getLeft(),child);
//回溯的时候平衡树
balance(parent);
}
}
}
/**
* 平衡二叉查找树
*/
private void balance(Node parent) {
if (isBalance(parent)){
return;
}
RotationModel model = judgeRotationModel(parent);
switch (model){
case LL:
rightRotation(parent);
break;
case LR:
leftRotation(parent);
rightRotation(parent);
break;
case RL:
rightRotation(parent);
leftRotation(parent);
break;
case RR:
rightRotation(parent);
break;
default:
break;
}
}
/**
* 左旋转
* (这里的balance指的是平衡后)
*/
private void leftRotation(Node balance){
Node leftChild = balance.getLeft();
Node rightGrandSon = leftChild.getRight();
leftChild.setRight(null);
balance.setLeft(rightGrandSon);
rightGrandSon.setLeft(leftChild);
}
/**
* 右旋转
* (这里的balance指的是平衡后)
*/
private void rightRotation(Node balance){
Node parent = searchParent(balance);
Node leftChild = balance.getLeft();
Node rightGrandSon = leftChild.getRight();
if (parent==null){
root = leftChild;
}else {
//将父节点的孩子替换为非平衡节点的左孩子
if (parent.getRight()==balance){
parent.setRight(leftChild);
}else {
parent.setLeft(leftChild);
}
}
//将原本的非平衡节点设置为右节点
leftChild.setRight(balance);
//将右子孙节点设置为原来非平衡节点的左节点
balance.setLeft(rightGrandSon);
}
/**
* 判断节点是否平衡
*/
private boolean isBalance(Node parent) {
return getDepth(parent.getRight())-getDepth(parent.getLeft())<2
&&getDepth(parent.getRight())-getDepth(parent.getLeft())>-2;
}
/**
* 判断二叉树的旋转状态
*/
private RotationModel judgeRotationModel(Node balance){
if (getDepth(balance.getRight())>getDepth(balance.getLeft())){
if (balance.getRight().getRight()==null){
return RotationModel.RL;
}else{
return RotationModel.RR;
}
}else{
if (balance.getLeft().getLeft()==null){
return RotationModel.LR;
}else {
return RotationModel.LL;
}
}
}
/**
* 查找节点的父亲节点
*/
private Node findParent(Node child){
if (child==root){
return null;
}
return findParent(root,child);
}
/**
* 递归查找子节点的父亲节点
*/
private Node findParent(Node parent,Node child){
Node target;
if (parent==null){
return null;
}
if (parent.getLeft()==child||parent.getRight()==child){
target = parent;
}else if (child.getValue()>parent.getValue()){
target = findParent(parent.getRight(),child);
}else {
target = findParent(parent.getLeft(),child);
}
return target;
}
/**
* 迭代查找子节点的父亲节点
*/
private Node searchParent(Node child){
if (child==root){
return null;
}
Node parent = root;
while (parent!=null){
if (parent.getLeft()==child||parent.getRight()==child){
return parent;
} else if (child.getValue()>parent.getValue()){
parent = parent.getRight();
}else {
parent = parent.getLeft();
}
}
return null;
}
/**
* 获取节点的深度
*/
public int getDepth(Node node){
if (node==null){
return 0;
}
return 1+(getDepth(node.getLeft())>getDepth(node.getRight())
?getDepth(node.getLeft()):getDepth(node.getRight()));
}
/**
* 中序遍历
*/
public void inOrderTraverse(Node root){
if (root==null){
return;
}
inOrderTraverse(root.getLeft());
System.out.print(root.getValue()+",");
inOrderTraverse(root.getRight());
}
static class Node{
int value;
Node left;
Node right;
public Node(int value){
this.value = value;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
enum RotationModel{
LL,LR,RR,RL
}
}
红黑树
红黑树也是一种弱平衡或者说自平衡(不是绝对的平衡)的二叉查找树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。红黑树的特点是：
- 根节点必须是黑色
- 所有叶子都是黑色
- 每个红色结点的两个子结点一定都是黑色
- 红黑树中所有的叶子节点后面再接上左右两个空节点，这样可以保持算法的一致性，而且所有的空节点都是黑色。
- 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高相差不超过1，和红黑树相比，AVL树是严格的平衡二叉树，平衡条件必须满足。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，因而它的旋转是非常耗时的。
由于维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。
红黑树一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树。由于是弱平衡，可以看到，在相同的节点情况下，AVL树的高度低于红黑树。相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，我们就用红黑树。
红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。所以红黑树的插入效率更高。
红黑树有两大操作保证平衡：
- recolor
- rotation
image.png
插入节点的场景
image.png
/**
* 红黑树
*/
public class RedBlackTree {
Node root;
public Node getRoot(){
return this.root;
}
/**
* 向树中插入节点
*/
public void insert(int value){
if (root==null){
Node node = new Node(NodeColor.BLACK,value);
root = node;
}else {
Node node = new Node(NodeColor.RED,value);
insert(root,node);
}
}
/**
* 插入节点
*/
private void insert(Node parent,Node node){
//右子树
if (node.getValue()>parent.getValue()){
if (parent.getRight()==null){
parent.setRight(node);
selfBalance(node);
return;
}else {
insert(parent.getRight(),node);
}
}
//左子树
if (node.getValue()<parent.getValue()){
if (parent.getLeft()==null){
parent.setLeft(node);
selfBalance(node);
return;
}else {
insert(parent.getLeft(),node);
}
}
}
/**
* 红黑树的自平衡
*/
private void selfBalance(Node node) {
if (node==null){
return;
}
if (node==root){
if (node.getColor().equals(NodeColor.RED)){
node.setColor(NodeColor.BLACK);
}
return;
}
Node parent = findParent(node);
if (parent==root){
if (parent.getColor().equals(NodeColor.RED)){
parent.setColor(NodeColor.BLACK);
}
return;
}
Node grandParent = findParent(parent);
Node uncle;
if (grandParent.getLeft()==parent){
uncle = grandParent.getRight();
}else {
uncle = grandParent.getLeft();
}
selfBalance(node,parent,uncle,grandParent);
}
/**
* 递归自平衡
*/
private void selfBalance(Node node, Node parent, Node uncle, Node grandParent) {
CaseType type = judgeCaseType(node, parent, uncle, grandParent);
switch (type){
case PB://父亲是黑色节点直接插入，不用处理
break;
case UR://父亲节点和叔叔节点都是红色
parent.setColor(NodeColor.BLACK);
uncle.setColor(NodeColor.BLACK);
grandParent.setColor(NodeColor.RED);
selfBalance(grandParent);
break;
case PR_UB_LL://父亲节点是红色，叔叔节点是黑色或者不存在
parent.setColor(NodeColor.BLACK);
grandParent.setColor(NodeColor.RED);
rightRotation(grandParent);
break;
case PR_UB_LR:
leftRotation(parent);
selfBalance(parent);
break;
case PR_UB_RR:
parent.setColor(NodeColor.BLACK);
grandParent.setColor(NodeColor.RED);
leftRotation(grandParent);
break;
case PR_UB_RL:
rightRotation(parent);
selfBalance(parent);
break;
}
}
/**
* 对当前节点进行左旋
*/
private void leftRotation(Node balance){
Node parent = findParent(balance);
Node rightChild = balance.getRight();
Node leftGrandChild = rightChild.getLeft();
if (parent==root){
root = rightChild;
}else {
if (balance==parent.getLeft()){
parent.setLeft(rightChild);
}else {
parent.setRight(rightChild);
}
}
rightChild.setLeft(balance);
balance.setRight(leftGrandChild);
}
/**
* 对当前节点进行右旋
*/
private void rightRotation(Node balance){
Node parent = findParent(balance);
Node leftChild = balance.getLeft();
Node rightGrandChild = leftChild.getRight();
if (parent==root){
root = leftChild;
}else {
if (balance==parent.getLeft()){
parent.setLeft(leftChild);
}else {
parent.setRight(leftChild);
}
}
leftChild.setRight(balance);
balance.setLeft(rightGrandChild);
}
/**
* 寻找当前节点的父亲节点
*/
private Node findParent(Node current){
if (current==root){
return null;
}
Node parent = root;
while (parent!=null){
if (parent.getLeft()==current||parent.getRight()==current){
return parent;
}else if (current.getValue()>parent.getValue()){
parent = parent.getRight();
}else {
parent = parent.getLeft();
}
}
return null;
}
/**
* 判断节点的场景
*/
public CaseType judgeCaseType(Node node,Node parent,Node uncle,Node grandParent){
if (parent.getColor().equals(NodeColor.BLACK)){
return CaseType.PB;
}else if (uncle!=null&&uncle.getColor().equals(NodeColor.RED)){
return CaseType.UR;
}else if (parent==grandParent.getLeft()&&node==parent.getLeft()){
return CaseType.PR_UB_LL;
}else if (parent==grandParent.getRight()&&node==parent.getLeft()){
return CaseType.PR_UB_RL;
}else if (parent==grandParent.getLeft()&&node==parent.getRight()){
return CaseType.PR_UB_LR;
}else if (parent==grandParent.getRight()&&node==parent.getRight()){
return CaseType.PR_UB_RR;
}else {
throw new RuntimeException("未考虑当前场景,存在错误");
}
}
public void inOrderTraverse(Node root){
if (root==null){
return;
}
inOrderTraverse(root.getLeft());
System.out.print(root.getValue()+"["+root.getColor()+"] ");
inOrderTraverse(root.getRight());
}
/**
* 红黑树节点
*/
@Setter
@Getter
static class Node{
public Node(NodeColor color,int value){
this.color = color;
this.value = value;
}
NodeColor color;
int value;
Node left;
Node right;
}
/**
* 节点颜色
*/
enum NodeColor{
BLACK,RED
}
/**
* 场景类型
* PB——>ParentBlack
* PR——>ParentRed
* UB——>UncleBlack
* UR——>UncleRed
* */
enum CaseType{
PB,//父亲节点是黑色
UR,//父亲节点是红色,叔叔节点也是红色
/* A *
* B *
* C *
* */
PR_UB_LL,//父亲节点是红色,叔叔节点是黑色或者不存在,当前节点和父亲节点是左左结构
/* A *
* B *
* C *
* */
PR_UB_LR,//父亲节点是红色,叔叔节点是黑色或者不存在,当前节点和父亲节点是左右结构
/* A *
* B *
* C *
* */
PR_UB_RL,//父亲节点是红色,叔叔节点是黑色或者不存在,当前节点和父亲节点是右左结构
/* A *
* B *
* C *
* */
PR_UB_RR,//父亲节点是红色,叔叔节点是黑色或者不存在,当前节点和父亲节点是右右结构
;
}
}
Huffman树
哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。
在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。
路径
在一棵树中，一个结点到另一个结点之间的通路，称为路径
路径长度
在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1
结点的权
给每一个结点赋予一个新的数值，被称为这个结点的权。
结点的带权路径长度
指的是从根结点到该结点之间的路径长度与该结点的权的乘积。
WPL
树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL”
构建哈夫曼树的过程
- 在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
- 在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
-
重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。
image.png
/**
* 哈夫曼树
*/
public class HuffmanTree {
Node root;
public Node getRoot(){
return root;
}
private void buildHuffmanTree(List<Node> nodes) {
if (nodes.size()<=0){
return;
}
if (nodes.size()<2){
root = nodes.get(0);
return;
}
Node[] array;
while (nodes.size()>2){
Node left = nodes.get(0);
Node right = nodes.get(1);
Node parent = new Node(null,left.getWeight()+right.getWeight());
parent.setLeft(left);
parent.setRight(right);
nodes.remove(left);
nodes.remove(right);
nodes.add(parent);
array = new Node[nodes.size()];
nodes.toArray(array);
sort(array);
}
root = new Node(null,nodes.get(0).getWeight()+nodes.get(1).getWeight());
root.setLeft(nodes.get(0));
root.setRight(nodes.get(1));
}
public void sort(Node[] array) {
bubbleSort(array);
}
/**
* 比较相邻的两个元素之间的值
*/
private void bubbleSort(Node[] array){
int loop=0,swap=0;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length-1; j++) {
loop++;
if(array[j].getWeight()<array[j+1].getWeight()){
swap++;
Node temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
@Data
static class Node{
public Node(String name,int weight){
this.name = name;
this.weight = weight;
}
private String name;//节点
private int weight;//节点权值
private Node left;
private Node right;
}
}
