二叉树
二叉树是n个结点的有限集合，该集合或者为空集，或者有一个根节点和两棵互不相交的，分别称为根结点的左子树和右子树的二叉树组成。
1.每个节点最多有两棵子树
2.左子树和右子树是有顺序的，次序不能任意颠倒
3.即使树中某结点只有一颗子树，也要区分它是左子树还是右子树。
满二叉树：
所有分支节点都存在左子树和右子树，并且所有叶子结点都在一层上。
1.叶子结点只能出现在最下一层
2.非叶子结点的度一定是2
3.在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
完全二叉树：
对一棵具有n个结点的二叉树按层序编号，编号为i的结点与同样深度的满二叉树中编号为i的结点的二叉树中位置完全相同。
1.叶子结点只能出现在最下两层
2.最下层的叶子一定集中在左部连续位置
3.倒数二层，若有叶子结点，一定都在右部连续位置
4.如果结点度为1，则该结点只有左孩子
5.同样结点数的二叉树，完全二叉树的深度最小。
二叉树的性质：
1.二叉树的第i层至多有2的i-1次方的结点
2.深度为k的二叉树至多有2的k次方-1个结点。
3.在任何一棵二叉树，叶子结点数为n0,度为2的结点数为n2.---->n0=n2+1
4.具有n个结点的完全二叉树的深度为log以2为低n的对数，向下取整后+1
5.一棵具有n个结点的完全二叉树的结点按层序编号，对任一节点i（1<=i<=n）有：
（1）如果i=1,则结点i是二叉树的跟，无双亲；如果i>1，则其双亲是结点i/2向下取整
（2）如果2i>n，则结点i无左孩子，否则其左孩子是结点2i
（3）如果2i+1>n，则结点i无右孩子，否则其右孩子是结点2i+1
——————————————————二叉树存储结构——————————————————
二叉链表：
二叉树的每个结点最多有两个孩子，一个数据域，两个指针域
结点数据结构：
private static class LinkedBinaryNode {
Object data;
private LinkedBinaryNode leftChildNode;
private LinkedBinaryNode rightChildNode;
public LinkedBinaryNode(Object data) {
this.data = data;
}
public LinkedBinaryNode(Object data, LinkedBinaryNode leftChildNode, LinkedBinaryNode rightChildNode) {
this.data = data;
this.leftChildNode = leftChildNode;
this.rightChildNode = rightChildNode;
}
}
初始化：
/**
* 数据量
*/
private int size;
/**
* 根节点
*/
private LinkedBinaryNode root;
public LinkedBinaryTree() {
}
插入结点：
public void addRoot(Object o) {
root = new LinkedBinaryNode(o);
size++;
}
public void addL(Object o, LinkedBinaryNode node) {
node.leftChildNode = new LinkedBinaryNode(o);
size++;
}
public void addR(Object o, LinkedBinaryNode node) {
node.rightChildNode = new LinkedBinaryNode(o);
size++;
}
删除结点：
public void removeR(LinkedBinaryNode linkedBinaryNode) {
if (linkedBinaryNode != null && linkedBinaryNode.rightChildNode != null) {
linkedBinaryNode.rightChildNode = null;
size--;
}
}
public void removeL(LinkedBinaryNode linkedBinaryNode) {
if (linkedBinaryNode != null && linkedBinaryNode.leftChildNode != null) {
linkedBinaryNode.leftChildNode = null;
size--;
}
}
——————————————————遍历二叉树————————————————————
前序遍历：
先访问根结点，然后前序遍历左子树，再前序遍历右子树
public void pre(LinkedBinaryNode linkedBinaryNode) {
if (linkedBinaryNode == null) {
return;
}
System.out.print(linkedBinaryNode.data + " ");
pre(linkedBinaryNode.leftChildNode);
pre(linkedBinaryNode.rightChildNode);
}
中序遍历：
中序遍历根结点的左子树，然后是访问根结点，再中序遍历右子树
public void mid(LinkedBinaryNode linkedBinaryNode) {
if (linkedBinaryNode == null) {
return;
}
mid(linkedBinaryNode.leftChildNode);
System.out.print(linkedBinaryNode.data + " ");
mid(linkedBinaryNode.rightChildNode);
}
后序遍历：
从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点
public void after(LinkedBinaryNode linkedBinaryNode) {
if (linkedBinaryNode == null) {
return;
}
after(linkedBinaryNode.leftChildNode);
after(linkedBinaryNode.rightChildNode);
System.out.print(linkedBinaryNode.data + " ");
}
层序遍历：
从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序逐个访问。
public void level(LinkedBinaryNode root){
if(root == null){
return;
}
Queue<LinkedBinaryNode> queue = new ArrayDeque<>();
queue.add(root);
while(!queue.isEmpty()){
LinkedBinaryNode node = queue.poll();
System.out.println(node.data);
if(node.leftChildNode !=null){
queue.add(node.leftChildNode);
}
if(node.rightChildNode !=null){
queue.add(node.rightChildNode);
}
}
}
————————————————————线索二叉树—————————————————
指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，二叉树称为线索二叉树
线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程。
线索化的实质就是将二叉链表中的空指针改为指向前驱和后继的线索，线索化的过程就是在遍历的过程中修改空指针的过程。
private static class BinaryThreadNode {
private int val;
private BinaryThreadNode left;
private BinaryThreadNode right;
//true指向前驱
private Boolean lflag;
//true指向后继
private Boolean rflag;
public BinaryThreadNode(int val) {
this.val = val;
}
}
//始终指向刚刚访问过的结点
private BinaryThreadNode preNode;
/**
* 中序遍历线索化
*/
public void inThreadIng(BinaryThreadNode root) {
if (root == null) {
return;
}
inThreadIng(root.left);
if (root.left == null) {
root.left = preNode;
root.lflag = true;
}
if (preNode != null && preNode.right == null) {
preNode.rflag = true;
preNode.right = root;
}
preNode = root;
inThreadIng(root.right);
}
/**
* 中序遍历线索二叉树
*/
public void inOrderThreading(BinaryThreadNode node) {
//1、找中序遍历方式开始的节点
while (node != null && !node.lflag) {
node = node.left;
}
while (node != null) {
System.out.print(node.val + ", ");
//如果右指针是线索,线索即是下一个要遍历的结点
if (node.rflag) {
node = node.right;
} else {
//如果右指针不是线索，如果不是线索，则是该结点的右孩子节点。找到右子树开始的节点。即最左
node = node.right;
while (node != null && !node.lflag) {
node = node.left;
}
}
}
}
————————————————树、森林、二叉树转换—————————————————
树转换为二叉树：
1.加线。在所有兄弟节点之间加一条线
2.去线。对树中每个结点，只保留它与第一个孩子节点的连线，删除它与其他孩子节点之间的连线
3.层次调整。以树的根节点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树的左孩子，兄弟转换过来的孩子是结点的右孩子。
森林转换为二叉树：
1.把每棵树转换为二叉树
2.第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。
当所有的二叉树连接起来后就得到了由森林转换来的二叉树。
二叉树转换为树：
1.加线。若某结点的左孩子节点存在，则将这个左孩子的右孩子节点、右孩子的右孩子节点....也就是左孩子的n个右孩子节点都作为此节点的孩子。
2.去线。删除原二叉树中所有节点与其有孩子节点的连线
3.层次调整。
二叉树转换为森林：
1.从根节点开始，若右孩子存在，则把与右孩子节点的连线删除，在查看分离后的二叉树，若右孩子存在，则连线删除....直到所有右孩子连线都删除为止，得到分离的二叉树
2.再将每棵分离后的二叉树转换为树
————————————————————哈夫曼树—————————————————
从树中一个节点到另一个节点之间的分支构成两个节点之间的路径，路径上的分支数目称作路径长度。
树的路径长度就是从跟到每一节点的路径长度之和。
带权路径最小的二叉树成为赫夫曼树。
1.根据给定的n个权值{w1，w2....wn}构成n棵二叉树的集合F={T1,T2....Tn}，其中每棵二叉树Ti中只有一个带权为wi的根节点，其左右子树均为空。
2.在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根结点权值之和。
3.在F中删除这两棵树，同时将新得到的二叉树加入F中
4.重复2、3步骤，知道F仅含有一棵树为止，这棵树便是哈夫曼树。
private static class HuffmanNode {
private String val;
//权值
private int weight;
private HuffmanNode left;
private HuffmanNode right;
public HuffmanNode(String val, int weight) {
this.weight = weight;
this.val = val;
}
public int getWeight() {
return weight;
}
}
public static HuffmanNode buildHuffmanTree(List<HuffmanNode> huffmanNodeList) {
if (CollectionUtils.isEmpty(huffmanNodeList)) {
return null;
}
int i = 1;
while (huffmanNodeList.size() > 1) {
//将节点排序，按照权值大小排序
huffmanNodeList.sort(Comparator.comparing(HuffmanNode::getWeight));
HuffmanNode left = huffmanNodeList.get(0);
HuffmanNode right = huffmanNodeList.get(1);
HuffmanNode parent = new HuffmanNode("W" + i, left.weight + right.weight);
parent.left = left;
parent.right = right;
huffmanNodeList.add(parent);
huffmanNodeList.remove(left);
huffmanNodeList.remove(right);
}
return huffmanNodeList.get(0);
}
