二叉树的遍历
//二叉树结点定义
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
val=x;
}
@Override
public String toString(){
return "val: "+val;
}
}
//访问结点方法方法
public void visit(TreeNode node){
System.out.print(node.val+" ");
}
-
前序遍历
-
递归实现
/** * 递归先序遍历 * */ public void preOrderRecursion(TreeNode node){ if(node==null) //如果结点为空则返回 return; visit(node);//访问根节点 preOrderRecursion(node.left);//访问左孩子 preOrderRecursion(node.right);//访问右孩子 } -
非递归
/** * 非递归先序遍历二叉树 * */ public List<Integer> preorderTraversal(TreeNode root) { List<Integer> resultList = new ArrayList<>(); Stack<TreeNode> treeStack = new Stack<>(); if (root == null) //如果为空树则返回 return resultList; treeStack.push(root); while( !treeStack.isEmpty() ){ TreeNode tempNode = treeStack.pop(); if(tempNode != null){ resultList.add(tempNode.val);//访问根节点 if (tempNode.right != null) { treeStack.push(tempNode.right); //入栈右孩子 } if (tempNode.left != null) { treeStack.push(tempNode.left);//入栈左孩子 } } } return resultList; }
-
-
中序遍历
递归
-
非递归
/** 非递归中序遍历 */ public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode cur = root; while(cur!=null || !stack.empty()){ while(cur!=null){ stack.add(cur); cur = cur.left; } cur = stack.pop(); list.add(cur.val); cur = cur.right; } return list; }
-
后序遍历
递归
-
非递归(加一个辅助栈)
public static void posOrderTraverse(Node head) { System.out.println("pos-order"); if(head != null) { Stack<Node> stack1 = new Stack<>(); Stack<Node> stack2 = new Stack<>(); // 辅助栈，存储 根 -> 右 -> 左 的结果 stack1.push(head); while(!stack1.isEmpty()) { head = stack1.pop(); stack2.push(head); // 有左孩子就先压入左孩子 if(head.left != null) stack1.push(head.left); // 有右孩子就后压入右孩子 if(head.right != null) stack1.push(head.right); } // 逆序打印 根 -> 右 -> 左 的结果，就是后序遍历的结果 while(!stack2.isEmpty()) System.out.print(stack2.pop().val + " "); } }
-
层序遍历(广度优先，用队列)
层序遍历框架：
void traverse(TreeNode root) { if (root == null) return; // 初始化队列，将 root 加入队列 Queue<TreeNode> q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { TreeNode cur = q.poll(); /* 层级遍历代码位置 */ System.out.println(root.val); /*****************/ if (cur.left != null) { q.offer(cur.left); } if (cur.right != null) { q.offer(cur.right); } } }分层来打印：需要加入一个Path
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) return res; Deque<TreeNode> queue = new ArrayDeque<>(); queue.addLast(root); while (queue.size() != 0) { int size = queue.size(); List<Integer> path = new ArrayList<>(); for (int i=0;i<size;i++) { //这个循环很关键 //按顺序出队列，访问出队列的元素的左右结点 TreeNode temp = queue.removeFirst(); if (temp.left != null) { queue.addLast(temp.left); } if (temp.right != null) { queue.addLast(temp.right); } path.add(temp.val); } res.add(path); } return res; } -
通过先序遍历和中序遍历重建二叉树
[图片上传失败...(image-923cb8-1609223312780)]
TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) { if (preStart > preEnd) { return null; } // root 节点对应的值就是前序遍历数组的第一个元素 int rootVal = preorder[preStart]; // rootVal 在中序遍历数组中的索引 int index = 0; for (int i = inStart; i <= inEnd; i++) { if (inorder[i] == rootVal) { index = i; break; } } int leftSize = index - inStart; // 先构造出当前根节点 TreeNode root = new TreeNode(rootVal); // 递归构造左右子树，参考下面两幅图 root.left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1); root.right = build(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd); return root; }image-20201226195602243image-20201226195624346 -
通过中序遍历和后序遍历重建二叉树
image-20201226195723841TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) { if (inStart > inEnd) { return null; } // root 节点对应的值就是后序遍历数组的最后一个元素 int rootVal = postorder[postEnd]; // rootVal 在中序遍历数组中的索引 int index = 0; for (int i = inStart; i <= inEnd; i++) { if (inorder[i] == rootVal) { index = i; break; } } // 左子树的节点个数 int leftSize = index - inStart; TreeNode root = new TreeNode(rootVal); // 递归构造左右子树 root.left = build(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1); root.right = build(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1); return root; }image-20201226195748361
总结：主要是要找到正确的起始位置，可以自己举一个例子画图来确定。leftSize是关键，他是中序遍历左子树的节点总数。
二叉树的序列化与反序列化
二叉树的序列化可以运用于对象转化为JSON字符串，反序列化可运用于JSON转化为对象。JSON的运用非常广泛，比如我们经常将变成语言中的结构体序列化成 JSON字符串，存入缓存或者通过网络发送给远端服务，消费者接受JSON字符串然后进行反序列化，就可以得到原始数据了。这就是「序列化」和「反序列化」的目的，以某种固定格式组织字符串，使得数据可以独立于编程语言。
-
前序遍历解法
序列化代码：如果结点是空结点，那么在字符串后面拼接一个“#,”;如果不是空结点，那么拼接“
rootVal，”。最后结果返回一个把二叉树“打平”了的字符串String SEP = ","; String NULL = "#"; /* 主函数，将二叉树序列化为字符串 */ String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); serialize(root, sb); return sb.toString(); } /* 辅助函数，将二叉树存入 StringBuilder */ void serialize(TreeNode root, StringBuilder sb) { if (root == null) { sb.append(NULL).append(SEP); return; } /****** 前序遍历位置 ******/ sb.append(root.val).append(SEP); /***********************/ serialize(root.left, sb); serialize(root.right, sb); } 反序列化代码：将序列化的字符串按照“,”进行分割，并转化为链表结构。然后通过前序遍历框架反序列化。
/* 主函数，将字符串反序列化为二叉树结构 */ TreeNode deserialize(String data) { // 将字符串转化成列表 LinkedList<String> nodes = new LinkedList<>(); for (String s : data.split(SEP)) { nodes.addLast(s); } return deserialize(nodes); } /* 辅助函数，通过 nodes 列表构造二叉树 */ TreeNode deserialize(LinkedList<String> nodes) { if (nodes.isEmpty()) return null; /****** 前序遍历位置 ******/ // 列表最左侧就是根节点 String first = nodes.removeFirst(); if (first.equals(NULL)) return null; TreeNode root = new TreeNode(Integer.parseInt(first)); /***********************/ //递归的去调用 root.left = deserialize(nodes); root.right = deserialize(nodes); return root; } -
后序遍历解法
序列化代码：
/* 辅助函数，将二叉树存入 StringBuilder */ void serialize(TreeNode root, StringBuilder sb) { if (root == null) { sb.append(NULL).append(SEP); return; } serialize(root.left, sb); serialize(root.right, sb); /****** 后序遍历位置 ******/ sb.append(root.val).append(SEP); /***********************/ }反序列化代码：首先要找到根节点，再按照根-->右-->左的顺序还原。
/* 主函数，将字符串反序列化为二叉树结构 */ TreeNode deserialize(String data) { LinkedList<String> nodes = new LinkedList<>(); for (String s : data.split(SEP)) { nodes.addLast(s); } return deserialize(nodes); } /* 辅助函数，通过 nodes 列表构造二叉树 */ TreeNode deserialize(LinkedList<String> nodes) { if (nodes.isEmpty()) return null; // 从后往前取出元素 String last = nodes.removeLast(); if (last.equals(NULL)) return null; TreeNode root = new TreeNode(Integer.parseInt(last)); // 先构造右子树，后构造左子树 root.right = deserialize(nodes); root.left = deserialize(nodes); return root; } -
层序遍历解法
序列化代码：
String SEP = ","; String NULL = "#"; /* 将二叉树序列化为字符串 */ String serialize(TreeNode root) { if (root == null) return ""; StringBuilder sb = new StringBuilder(); // 初始化队列，将 root 加入队列 Queue<TreeNode> q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { TreeNode cur = q.poll(); /* 层级遍历代码位置 */ if (cur == null) { sb.append(NULL).append(SEP); continue; } sb.append(cur.val).append(SEP); /*****************/ q.offer(cur.left); q.offer(cur.right); } return sb.toString(); }序列化后的结果如图所示
image-20201226195841319反序列化代码：
/* 将字符串反序列化为二叉树结构 */ TreeNode deserialize(String data) { if (data.isEmpty()) return null; String[] nodes = data.split(SEP); // 第一个元素就是 root 的值 TreeNode root = new TreeNode(Integer.parseInt(nodes[0])); // 队列 q 记录父节点，将 root 加入队列 Queue<TreeNode> q = new LinkedList<>(); q.offer(root); for (int i = 1; i < nodes.length; ) { // 队列中存的都是父节点 TreeNode parent = q.poll(); // 父节点对应的左侧子节点的值 String left = nodes[i++]; if (!left.equals(NULL)) { parent.left = new TreeNode(Integer.parseInt(left)); q.offer(parent.left); } else { parent.left = null; } // 父节点对应的右侧子节点的值 String right = nodes[i++]; if (!right.equals(NULL)) { parent.right = new TreeNode(Integer.parseInt(right)); q.offer(parent.right); } else { parent.right = null; } } return root; } -
总结：
注意后序遍历解法，与前序遍历、层序遍历不同，后序遍历序列化是按照标准后序遍历框架进行的，而反序列化则是先找到最后一个元素即为根节点，从后往前(根-->右-->左)进行反序列化。
二叉(排序/搜索)树 (BST树)
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树。
- 它的中序遍历是升序的（左-->中-->右），也可以降序（右-->中-->左）
二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。
-
查找
可以利用二叉搜索树的性质进行查找（二分查找），O(logn)时间复杂度，最坏情况O(n)(当树退化为链表时)。
-
插入
在查找的基础上进行插入操作
-
删除
分为三种情况：删除叶子节点、删除只有一个子结点的结点、删除有两个子结点的结点
TreeNode deleteNode(TreeNode root, int key) { if (root == null) return null; if (root.val == key) { // 这两个 if 把情况 1 和 2 都正确处理了 if (root.left == null) return root.right; if (root.right == null) return root.left; // 处理情况 3 //minNode 右子树的最小结点 TreeNode minNode = getMin(root.right); root.val = minNode.val; root.right = deleteNode(root.right, minNode.val); } else if (root.val > key) { root.left = deleteNode(root.left, key); } else if (root.val < key) { root.right = deleteNode(root.right, key); } return root; } TreeNode getMin(TreeNode node) { // BST 最左边的就是最小的 while (node.left != null) node = node.left; return node; }
平衡二叉树(AVL树)
平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
基本代码准备：
/**
* AVLTree是BST，所以节点值必须是可比较的
*/
public class AvlTree<E extends Comparable<E>>{
private class Node{
public E e;
public Node left;
public Node right;
public int height;
public Node(E e){
this.e = e;
this.left = null;
this.right = null;
this.height = 1;
}
}
private Node root;
private int size;
public AvlTree(){
root=null;
size=0;
}
//获取某一结点的高度
private int getHeight(Node node){
if(node==null){
return 0;
}
return node.height;
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
/**
* 获取节点的平衡因子
* @param node
* @return
*/
private int getBalanceFactor(Node node){
if(node==null){
return 0;
}
return getHeight(node.left)-getHeight(node.right);
}
//判断树是否为平衡二叉树
public boolean isBalanced(){
return isBalanced(root);
}
private boolean isBalanced(Node node){
if(node==null){
return true;
}
int balanceFactory = Math.abs(getBalanceFactor(node));
if(balanceFactory>1){
return false;
}
return isBalanced(node.left)&&isBalanced(node.right);
}
}
-
LL（右旋）
LL的意思是向左子树（L）的左孩子（L）中插入新节点后导致不平衡，这种情况下需要右旋操作，而不是说LL的意思是右旋，后面的也是一样。
在这里插入图片描述
/**
* 右旋转
*/
private Node rightRotate(Node y){
//x作为新顶点
Node x = y.left;
//因为即将要改变x的右指针，需要保存原来的右孩子
Node t3 = x.right;
x.right = y;
y.left = t3;
//更新height
y.height = Math.max(getHeight(y.left),getHeight(y.right))+1;
x.height = Math.max(getHeight(x.left),getHeight(x.right))+1;
return x;
}
-
RR（左旋）
左旋操作/** * 左旋转 */ private Node leftRotate(Node y){ Node x = y.right; Node t2 = x.left; x.left = y; y.right = t2; //更新height y.height = Math.max(getHeight(y.left),getHeight(y.right))+1; x.height = Math.max(getHeight(x.left),getHeight(x.right))+1; return x; }
-
LR（双旋）
image-20201209203744422private Node LRRotate(Node y){ y.left = leftRotate(y.left); return rightRotate(y); } -
RL（双旋）image-20201209204242906private Node RLRotate(Node y){ y.right = rightRotate(y.right); return leftRotate(y); } 删除结点类似于BST树，但需要维护平衡性
B树（又叫B-树）和B+树
-
B树
又叫多路平衡搜索树，一颗m叉的
BTree特性如下（ceil()向上取整）：- 树中每个节点最多包含m个孩子。
- 除根节点与叶子节点外，每个节点至少有[ceil(m/2)]个孩子。
- 若根节点不是叶子节点，则至少有两个孩子。
- 所有的叶子节点都在同一层。
- 每个非叶子节点由n个key与n+1个指针组成，其中[ceil(m/2)-1] <= n <= m-1
以5叉BTree为例，key的数量：公式推导[ceil(m/2)-1] <= n <= m-1。所以 2 <= n <=4 。当n>4时，中间节点分裂到父节点，两边节点分裂。
插入 C N G A H E K Q M F W L T Z D P R X Y S 数据为例。
image-20201209221931890
image-20201209222034582
image-20201209222058261
image-20201209222116477
-
B+树
image-20201209222155086MySQL中的B+树
image-20201209222244742
