二叉树
本篇是希望你对树结构能有一些了解,对树的定义和基本操作做些汇总,方便了解其他用到树结构的算法.
节点的度
一个结点拥有的子树个数称为结点的度。
节点的高度:和数楼层一样是从下向上数的,节点到叶子节点所有路径上的最大值.叶子节点的高度为1,往上节点的高度依次递增。
节点的深度:从根节点到节点唯一的路径的长,根节点深度为1;深度为h的二叉树最多有2^h-1个结点,最少有h个结点;
对于树中相同深度的每个结点来说,它们的高度不一定相同,这取决于每个结点下面的叶结点的深度.
注: 根节点的深度,为0或者1是有争议的,这里采用深度为1 的说法.
树的层数:节点为第一层，往下一次递增.
完全二叉树
除二叉树的最高层外，其它各层的结点数都达到最大个数，最高层有叶子结点，并且叶子结点都是从左到右依次存在，这就是完全二叉树。
满二叉树
除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
小顶堆
小顶堆是一棵完全二叉树,非叶子结点的值不大于左孩子和右孩子的值。
数组表示: [1,3,4,7,10,5]
其中,arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
根节点在数组中的位置是0，第i个位置的子节点分别在2i+1和 2i+2;位置k的父节点位置为(k-1)/2;
大顶堆
大顶堆是一棵完全二叉树,非叶子结点的值不小于左孩子和右孩子的值。
数组表示: [107,8,5,6,4]
其中,arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
根节点在数组中的位置是0，第i个位置的子节点分别在2i+1和 2i+2;位置k的父节点位置为(k-1)/2;
二叉搜索树
又叫二叉排序树或者二叉查找树, 一个二叉树的左子树上所有节点的值均小于根节点的值,而右子树上所有结点的值均大于根节点的值,左小右大,并不是乱序.
平衡二叉树
平衡二叉树是在二叉排序树的基础上发展而来的，是一棵空树或者一个二叉树的左右两个子树的高度差的绝对值不超过1,并且左右两个子树也都是一棵平衡二叉树.
红黑树
红黑树也是二叉查找树,但不是平衡二叉查找树,它的左右子树高差有可能大于1;
红黑树的主要优点是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能;虽然定义时会出现红色节点和黑色节点,但在查找时却可以忽略这些概念.
红黑树的主要特点:
1. 节点是红色或者黑色
2. 根节点是黑色
3. 每个叶子的节点都是黑色的空节点（NULL）
4. 每个红色节点的两个子节点都是黑色的。
5. 从任意节点到其每个叶子的所有路径都包含相同个数的黑色节点。
二叉树遍历
前序遍历: 先遍历左子树,再遍历根结点和最后遍历右子树;
中序遍历: 先遍历根结点,再遍历左子树和最后遍历右子树;
后序遍历: 先遍历左子树,再遍历右子树和最后遍历根结点;
按层遍历: 按树的高度进行遍历,遍历根，访问子节点，再访问子节点的子节点;
附上代码:
public class TreeTraversal {
public static List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
inorderTraversal(root, list);
return list;
}
static void inorderTraversal(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
inorderTraversal(root.left, list);
list.add(root.val);
inorderTraversal(root.right, list);
}
public static List preOrderTraversal(TreeNode root) {
List result = new ArrayList();
preOrderTraversal(root, result);
return result;
}
private static void preOrderTraversal(TreeNode current, List result) {
if (current == null) {
return;
}
result.add(current.val);
preOrderTraversal(current.left, result);
preOrderTraversal(current.right, result);
}
public static List postOrderTraversal(TreeNode root) {
List result = new ArrayList();
postOrderTraversal(root, result);
return result;
}
private static void postOrderTraversal(TreeNode current, List result) {
if (current == null) {
return;
}
postOrderTraversal(current.left, result);
postOrderTraversal(current.right, result);
result.add(current.val);
}
public static List<Integer> levelOrderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (null == root) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
res.add(node.val);
if (null != node.left) {
queue.add(node.left);
}
if (null != node.right) {
queue.add(node.right);
}
}
return res;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
TreeNode l1 = new TreeNode(2);
TreeNode r1 = new TreeNode(3);
root.left = l1;
root.right = r1;
TreeNode l11 = new TreeNode(4);
TreeNode lr1 = new TreeNode(5);
l1.left = l11;
l1.right = lr1;
System.out.println(preOrderTraversal(root));
System.out.println(inorderTraversal(root));
System.out.println(postOrderTraversal(root));
System.out.println(levelOrderTraversal(root));
}
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
}
腾讯云开发者
