1.树的定义
1.1与节点相关的概念
节点的高度:该节点到叶子节点的最长路径(边的数量)
节点的深度:根节点到该节点的边的个数；
节点的层数:节点的深度+1；
树的高度:根节点的高度；
度 ：结点拥有的子树数称为结点的度 。度为零的结点称为叶子结点，度不为0的结点称为分支结点。除根节点外，分支结点也叫作内部结点。树的度是树内部各节点的度的最大值。
image.png
1.2 各种树
树>二叉树
满二叉树 ：一棵二叉树中，1 如果所有的分支结点都存在左子树和右子树 ，并且2 所有叶子结点都在同一层，这样的二叉树称为满二叉树
完全二叉树: 1.所有的叶子节点都在最后两层；2.最后一层的叶子节点靠左排列；3.除了最后一层，其它层的叶子节点都是满的
1.3 二叉树的存储结构
链式存储法
image.png
这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构来实现的。
顺序存储法
image.png
- 为了方便计算子节点，根节点会存储在下标为 1 的位置；
- 如果节点 X 存储在数组中下标为 i 的位置，下标为 2 * i 的位置存储的就是左子节点，下标为 2 * i + 1 的位置存储的就是右子节点；
- 反过来，下标为 i/2 的位置存储就是它的父节点。
堆其实就是一种完全二叉树，最常用的存储方式就是数组。
1.4 二叉树的性质
二叉树的性质：[一定要重视这里，考了超多次]
- 性质1：在二叉树的第i层上至多有2^(i-1)个结点(i>=1)
- 性质2：层数为K的二叉树至多有2^k-1个结点(i>=1)
- 性质3：对于任何一棵二叉树T，如果终端结点(叶子节点)数为n0,度为2的结点数为n2，则n0=n2+1
节点数：n=n0+n1+n2 n=n1+2n2+1 1表示根
1.5 完全二叉树的性质
- 包含n个结点的完全二叉树的层数为[log2 n]+1 向下取整
特值check法:例如n=1，层数为1;n=3,层数为2； -
完全二叉树中叶子节点数n0和总结点数N的关系 n0=[N/2],向上取整 比如[9/2]=5!!
1.5 向上取整为 2，向下取整为1；
2.二叉树的遍历
这里所说的前中后:指的是当前节点
前序遍历:当前节点-->左-->右
中序遍历:左-->当前节点-->右
后序遍历:左-->右-->当前节点
层序遍历:一层层遍历
2.1 前、中、后遍历的递归实现
每个节点都要被访问三次，时间复杂度为O(n)，空间复杂度为O(h)，h为二叉树的深度，其中h是二叉树的深度，额外空间是函数递归的调用栈产生的，而不是显示的额外变量。
// 前序遍历，当前节点-->左-->右
public static void preOrder(Node root) {
// 递归终止条件
if (root == null) {
return;
}
System.out.print(root.data + " ");
preOrder(root.left);
preOrder(root.right);
}
// 中序遍历，左-->当前节点-->右
public static void midOrder(Node root) {
// 递归终止条件
if (root == null) {
return;
}
midOrder(root.left);
System.out.print(root.data + " ");
midOrder(root.right);
}
// 后序遍历，左-->右-->当前节点-->
public static void postOrder(Node root) {
// 递归终止条件
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data + " ");
}
层序遍历
利用队列，每次弹出去后就将其左右节点压进去，直至为空
// 层序遍历，使用队列来实现
public static void levelOrder(Node root) {
LinkedList<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node remove = queue.remove();
System.out.print(remove.data + " ");
if (remove.left != null) {
queue.add(remove.left);
}
if (remove.right != null) {
queue.add(remove.right);
}
}
}
2.2 前、中、后遍历的非递归实现
2.2.1 前序遍历
根据前序遍历的访问的顺序，先访问根节点，然后再访问左子树和右子树。对于树中的任意一个节点，都可以看做一个根节点，因此 可以直接访问根节点，访问完根节点，如果它的左子树不为空，用相同的方法访问它的左子树，直到左子树为空，再访问它的右子树。
对于树中的任意一个节点p：
1） 访问p，并将节点入栈；
2）判断节点p的左孩子是否为空，若不为空，则将p的左孩子置为当前的节点p
- 若为空，则取栈顶节点并进行出栈操作(根据出栈节点去找该节点的右孩子)，并将栈顶节点的右孩子置为当前节点p，循环至1；
// 非递归实现前序遍历
public static void preOrder1(Node root) {
if (root == null) {
return;
}
Stack<Node> stack = new Stack<>();
while (root != null || stack.size() > 0) {
while (root != null) {
System.out.print(root.data+" ");
stack.push(root);
root = root.left;
}
if (stack.size() > 0) {
root=stack.pop();
root = root.right;
}
}
}
2.2.2 中序遍历
根据中序遍历的访问顺序，优先访问根节点的左孩子，而左孩子又可以看成是一个根节点，将当前节点压栈继续访问其左孩子，直到遇到左孩子为空的节点才对该节点进行访问，然后按照相同的方法遍历右孩子。
对于树中的任意节点p：
（1）若p的左孩子不为空，将p压栈，并将p的左孩子置为当前节点p，然后对当前节点重复操作。
（2）若p的左孩子为空，将栈顶元素出栈并进行访问，把当前节点置为p的右孩子。
（3）直到栈为空且p为空
// 中序遍历，非递归实现
public static void midOrder1(Node root) {
if (root == null) {
return;
}
Stack<Node> stack = new Stack<>();
while (root != null || stack.size() > 0) {
while (root != null) {
stack.push(root);
root = root.left;
}
if (stack.size() > 0) {
root = stack.pop();
System.out.print(root.data + " ");
root = root.right;
}
}
}
2.2.3后序遍历
//todo 待实现
3.二叉查找树
3.1定义
二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。
二叉查找树[二叉搜索树]Binary Search Tree：对于任意一个节点 n，其左子树下的每个后代节点的值都小于节点 n 的值；其右子树下的每个后代节点的值都大于节点 n 的值。二叉搜索树不一定是完全二叉树。
image.png
3.2 查找、增加、删除
3.2.1 查找
// 查找某个节点，存在的话返回该节点，不存在返回null
// 1.递归实现
public static TreeNode search(TreeNode node, int target) {
if (node == null) {
return null;
}
return _search(node, target);
}
private static TreeNode _search(TreeNode node, int target) {
if (node == null) {
return null;
}
if (node.val == target) {
return node;
} else if (node.val > target) {
return _search(node.left, target);
} else {
return _search(node.right, target);
}
}
// 2.非递归实现
public static TreeNode searchNoRecursion(TreeNode node, int target) {
if (node == null) {
return null;
}
while (node != null) {
if (node.val == target) {
return node;
} else if (node.val > target) {
node = node.left;
} else {
node = node.right;
}
}
return null;
}
3.2.2 插入
// 插入操作
// 1.递归实现
public static TreeNode insertByRecursion(TreeNode root, int target) {
// 递归终止条件
if (root == null) {
return new TreeNode(target);
}
// 插入的值存在，直接返回
if (root.val == target) {
return root;
} else if (root.val > target) {
return insertByRecursion(root.left, target);
} else {
return insertByRecursion(root.right, target);
}
}
// 2.非递归实现
public static TreeNode insertByNoRecursion(TreeNode root, int target) {
// 特殊情况处理
if (root == null) {
root = new TreeNode(target);
return root;
}
while (root != null) {
if (root.val == target) {
return root;
} else if (root.val > target) {
root = root.right;
} else {
root = root.left;
}
}
// 最后的root一定为空，此时给它赋值为插入的数据
root = new TreeNode(target);
return root;
}
3.2.3 删除最大值和最小值
// 删除最小值
// 思路，case1:如果最小值的右节点为空，那么直接删除即可
// case2:如果最小值的右节点不为空，那么需要将右节点置为该值
public static TreeNode removeMin(TreeNode root) {
if (root == null) {
return null;
}
return _removeMin(root);
}
private static TreeNode _removeMin(TreeNode root) {
if (root.left == null) {
// 如果root.right为null，则将root置为空，否则置为该数
TreeNode rightNode = root.right;
// 将右节点置为空，等待GC回收
root.right = null;
return rightNode;
}
// 这处其实很巧妙，我一开始的思路是node=removeMin(root.left)但是这样的问题是找到了该节点，却不知道父节点是哪一个
root.left = _removeMin(root.left);
return root;
}
// 删除最大值
public static TreeNode removeMax(TreeNode root) {
if (root == null) {
return null;
}
return _removeMax(root);
}
private static TreeNode _removeMax(TreeNode root) {
if (root.right == null) {
// 如果左值存在，则赋值给左值
TreeNode leftNode = root.left;
// 左值置为空，等到GC
root.left = null;
return leftNode;
}
root.right = _removeMax(root.right);
return root;
}
3.2.4 删除任意一个节点
情况一:如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。比如图中的删除节点 55。
情况二:如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。
情况三:如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。
image.png
public static void removeRandomNode(TreeNode root, int target) {
// 父节点一开始为null
TreeNode fNode = null;
// 子节点一开始即为根节点
TreeNode sNode = root;
// 1.首先是遍历，找到待删除的节点，以及父节点
while (root != null) {
if (root.val == target) {
break;
} else if (root.val > target) {
root = root.left;
} else {
root = root.right;
}
// 更新父子关系
fNode = sNode;
sNode = root;
}
// 2.没有找到，返回
if (sNode == null) {
return;
}
// 3.sNode的左右节点均存在
if (sNode.left != null && sNode.right != null) {
// 3.1 找到sNode右节点中的最小节点及父节点
// 父节点一开始为sNode
TreeNode fNodeFromsNode = sNode;
// 子节点一开始即为sNode.right
TreeNode sNodeFromsNode = sNode.right;
while (sNodeFromsNode.left != null) {
fNodeFromsNode = sNodeFromsNode;
sNodeFromsNode = sNodeFromsNode.left;
}
// 找到了以后，sNode的值替换为sNodeFromsNode的值
sNode.val = sNodeFromsNode.val;
// 巧妙。后面就变成了删除sNode
fNode = fNodeFromsNode;
sNode = sNodeFromsNode;
}
// 4.处理删除单节点问题
// 待删除的节点只能有一个子节点
TreeNode switchNode = null;
if (sNode.left != null) {
switchNode = sNode.left;
} else {
switchNode = sNode.right;
}
// 删除的为根节点
if (fNode == null) {
root = switchNode;
//注:这里不能用fNode.left!=null,因为fnode不一定只有一个子节点
} else if (fNode.left == sNode) {
fNode.left = switchNode;
} else {
fNode.right = switchNode;
}
}
