概念
二叉树就是度不超过2的树（每个结点最多有两个子结点）。
种类
满二叉树
一个二叉树如果每个层次的结点树都达到最大值，那么这个二叉树就是满二叉树
完全二叉树
叶子结点只出现在最下层和次下层，并且最下层的结点都集中在该层的最左边的若干位置的二叉树
原理
插入键值对
1.从根结点开始，拿结点的键与新键进行比较
2.若新键比当前结点的键小，则继续拿当前结点的左子结点去比较
3.若新键比当前结点的键大，则继续拿当前结点的右子结点去比较
4.若新键与当前结点的键一样大，则替换当前结点的值
5.若需要比较的结点不存在，则创建新结点作为上一个结点的左/右子结点（看上一步的比较逻辑而决定）
删除键值对
1.从根结点开始，拿结点的键与键进行比较
2.若键比当前结点的键小，则继续拿当前结点的左子结点去比较
3.若键比当前结点的键大，则继续拿当前结点的右子结点去比较
4.若新键与当前结点的键一样大，则删除当前结点
删除结点的逻辑
1.获取删除结点的左子树的最大结点 / 或右子树的最小结点（下面称其他替代结点）
2.使删除结点的父结点的左/右子结点（看上一步的比较逻辑而决定）的指针域指向替代结点
3.使替代结点的左子结点的指针域指向当前结点的左子结点
4.使替代结点的右子结点的指针域指向当前结点的右子结点
获取键对应的值
1.从根结点开始，拿结点的键与键进行比较
2.若键比当前结点的键小，则继续拿当前结点的左子结点去比较
3.若键比当前结点的键大，则继续拿当前结点的右子结点去比较
4.若新键与当前结点的键一样大，则将值进行返回
前序遍历
1.创建一个键队列（或集合等），用来保存获取到的键
2.创建一个结点队列，用来保存结点，默认添加根结点
3.遍历节点队列，若队列不为空，则从中获取一个结点
4.将该结点的键加入到键队列中
5.获取该结点的左子树，对其进行前序遍历
6.获取该结点的右子树，对其进行前序遍历
中序遍历
1.创建一个键队列（或集合等），用来保存获取到的键
2.创建一个结点队列，用来保存结点，默认添加根结点
3.遍历节点队列，若队列不为空，则从中获取一个结点
4.获取该结点的左子树，对其进行中序遍历
5.将该结点的键加入到键队列中
6.获取该结点的右子树，对其进行中序遍历
后序遍历
1.创建一个键队列（或集合等），用来保存获取到的键
2.创建一个结点队列，用来保存结点，默认添加根结点
3.遍历节点队列，若队列不为空，则从中获取一个结点
4.获取该结点的左子树，对其进行中序遍历
5.获取该结点的右子树，对其进行中序遍历
6.将该结点的键加入到键队列中
层序遍历
1.创建一个键队列（或集合等），用来保存获取到的键
2.创建一个结点队列，用来保存结点，默认添加根结点
3.遍历节点队列，若队列不为空，则从中获取一个结点
4.获取该结点的左子结点、右子结点，依次放入结点队列中
5.将左子结点、右子结点的键依次放入键队列中
最大深度
从根节点开始，查找左右子树的最大深度，较大者+1即是当前树的最大深度
示例
import java.util.LinkedList;
import java.util.Queue;
/**
* 堆代码 duidaima.com
* 二叉树
*/
public class BinaryTree<K extends Comparable<K>, V> {
// 根结点
private Node root;
// 存储的数据个数
private int N;
/**
* 内部结点类
*/
private class Node {
// 当前结点的键
private K key;
// 当前结点的值
private V value;
// 指向左子结点的指针
private Node left;
// 指向右子结点的指针
private Node right;
/**
* 构造方法
*/
public Node(K key, V value, Node left, Node right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
/**
* 构造方法
*/
public BinaryTree() {
// 初始化根结点
root = null;
// 初始化存储的数据个数
N = 0;
}
/**
* 向二叉树中插入一个键值对
*
* 原理
* (1) 新key比当前结点的key小的话，那么找当前结点的左子结点继续比较
* (2) 新key比当前结点的key大的话，那么找当前结点的右子结点继续比较
* (3) 新key与当前结点的key相等的话，那么替换当前结点的值
*
* @param key 键
* @param value 值
*/
public void put(K key, V value) {
// 校验键
validKey(key);
// 调用重载方法
root = put(root, key, value);
}
/**
* 向指定树上插入一个键值对，并返回插入后的新树
*
* @param node 指定树的根结点
* @param key 键
* @param value 值
*/
private Node put(Node node, K key, V value) {
if (node == null) {
// 如果当前结点不存在，那么创建新结点作为当前结点
node = new Node(key, value, null, null);
// 存储的数据个数+1
N++;
} else {
// 比较插入的key与当前结点的key的大小
int compareTo = key.compareTo(node.key);
// 新key比当前结点的key小，那么让当前结点的左子结点去与之比较
// 将操作后的结果结点作为当前结点的左子结点
if (compareTo < 0) {
node.left = put(node.left, key, value);
}
// 新key比当前结点的key大，那么让当前结点的右子结点去与之比较
// 将操作后的结果结点作为当前结点的右子结点
if (compareTo > 0) {
node.right = put(node.right, key, value);
}
// 新key与当前结点的key相等，那么将新值作为当前结点的值
if (compareTo == 0) {
node.value = value;
}
}
// 返回当前结点
return node;
}
/**
* 删除树中指定键对应的键值对
*
* 原理
* (1) 新key比当前结点的key小的话，那么找当前结点的左子结点继续比较
* (2) 新key比当前结点的key大的话，那么找当前结点的右子结点继续比较
* (3) 新key与当前结点的key相等的话，那么删除当前结点
* (A) 因为当前结点、左子结点、右子结点的值的排序为 左子结点 < 当前节点 < 右子结点
* (B) 所以删除当前结点时，将左子树的最大值结点 或 右子树的最小值结点 作为当前结点即可维持二叉树的结构完整性
*
* @param key 键
*/
public void delete(K key) {
// 校验键
validKey(key);
// 调用重载方法
root = delete(root, key);
}
/**
* 删除指定树中键对应的键值对
*
* @param node 指定树的根结点
* @param key 键
*/
private Node delete(Node node, K key) {
// 如果当前结点不存在，那么不进行操作
if (node == null) {
return null;
}
// 比较需删除的key与当前结点的key的大小
int compareTo = key.compareTo(node.key);
// 需删除的key比当前结点的key小
if (compareTo < 0) {
// 让当前结点的左子结点去删除
// 将操作后的结果结点作为当前结点的左子结点
node.left = delete(node.left, key);
// 返回当前结点
return node;
}
// 需删除的key比当前结点的key大
if (compareTo > 0) {
// 让当前结点的右子结点去删除
// 将操作后的结果结点作为当前结点的右子结点
node.right = delete(node.right, key);
// 返回当前结点
return node;
}
// 当前结点的key比需删除的key相等，则删除当前结点
// 记录当前结点的左结点
Node left = node.left;
// 记录当前结点的右结点
Node right = node.right;
// 因为当前结点的左子树都比当前结点小，右子树都比当前结点大
// 所以我们可以将左子树的最大结点 或者 右子树的最小结点拿出来替换当前结点
// 此处拿左子树的最大结点
// 如果没有左子树，那么直接将右子树中的根结点（当前结点的右结点）替换当前结点
if (left == null) {
return right;
}
// 如果没有右子树，那么直接将左子树中的根结点（当前结点的左结点）替换当前结点
if (right == null) {
return left;
}
// 左右子树都不为空，获取左子树的最大结点来替换当前结点
// 记录左子树的最大结点的父级结点
Node preNode = node;
// 记录左子树的最大结点
Node maxNode = left;
while(maxNode.right != null) {
preNode = maxNode;
maxNode = maxNode.right;
}
// 如果左子树的根结点就是最大结点，那么说明该结点没有右子结点
if (maxNode == left) {
// 让最大结点的右子结点指向当前结点的右子结点
maxNode.right = right;
} else {
// 让最大节点的左子结点指向当前结点的左子结点
maxNode.left = left;
// 让最大节点的右子结点指向当前结点的右子结点
maxNode.right = right;
// 将最大结点的父级结点的指向断开
preNode.right = null;
}
// 将当前结点的左右子结点的指向断开
node.left = null;
node.right = null;
// 存储的数据个数-1
N--;
// 返回结点
return maxNode;
}
/**
* 根据键从树中查找对应的值
*
* 原理
* (1) 新key比当前结点的key小的话，那么找当前结点的左子结点继续比较
* (2) 新key比当前结点的key大的话，那么找当前结点的右子结点继续比较
* (3) 新key与当前结点的key相等的话，那么返回当前结点的值
*
* @param key 键
* @return 键对应的值
*/
public V get(K key) {
// 校验键
validKey(key);
// 调用重载方法
return get(root, key);
}
/**
* 从指定树中，获取键对应的值
*
* @param node 指定树的根结点
* @param key 键
* @return 键对应的值
*/
private V get(Node node, K key) {
// 如果当前结点不存在，则返回null
if (node == null) {
return null;
}
// 比较查询的key与当前结点的key的大小
int compareTo = key.compareTo(node.key);
if (compareTo < 0) {
// 查找的key比当前结点的key要小，那么让当前结点的左结点去查找
return get(node.left, key);
} else if (compareTo > 0) {
// 查找的key比当前结点的key要大，那么让当前结点的右结点去查找
return get(node.right, key);
} else {
// 当前结点的key与新结点的key相等，那么将新值作为当前结点的值
return node.value;
}
}
/**
* 前序遍历
*
* 原理
* (1) 先打印当前结点，再打印左子树，最后打印右子树
* (2) 打印子树时，也按照(1)中次序来
*
* @return 树中所有key的队列
*/
public Queue<K> preErgodic() {
// 保存树中的所有key
Queue<K> keys = new LinkedList<>();
// 调用重载方法
preErgodic(root, keys);
// 返回查找到所有key
return keys;
}
/**
* 对指定树进行前序遍历
*/
private void preErgodic(Node node, Queue<K> keys) {
// 如果当前结点为null，不执行操作
if (node == null) {
return;
}
// 将当前结点的key加入队列
keys.add(node.key);
// 将当前结点的左子树加入队列
preErgodic(node.left, keys);
// 将当前结点的右子树加入队列
preErgodic(node.right, keys);
}
/**
* 中序遍历
*
* 原理
* (1) 先打印左子树，再打印当前结点，最后打印右子树
* (2) 打印子树时，也按照(1)中次序来
*
* @return 树中所有key的队列
*/
public Queue<K> midErgodic() {
// 保存树中的所有key
Queue<K> keys = new LinkedList<>();
// 调用重载方法
midErgodic(root, keys);
// 返回查找到所有key
return keys;
}
/**
* 对指定树进行中序遍历
*/
private void midErgodic(Node node, Queue<K> keys) {
// 如果当前结点为null，不执行操作
if (node == null) {
return;
}
// 将当前结点的左子树加入队列
midErgodic(node.left, keys);
// 将当前结点的key加入队列
keys.add(node.key);
// 将当前结点的右子树加入队列
midErgodic(node.right, keys);
}
/**
* 后序遍历
*
* 原理
* (1) 先打印左子树，再打印右子树，最后打印当前结点
* (2) 打印子树时，也按照(1)中次序来
*
* @return 树中所有key的队列
*/
public Queue<K> afterErgodic() {
// 保存树中的所有key
Queue<K> keys = new LinkedList<>();
// 调用重载方法
afterErgodic(root, keys);
// 返回查找到所有key
return keys;
}
/**
* 对某个树结点进行后序遍历
*/
private void afterErgodic(Node node, Queue<K> keys) {
// 如果当前结点为null，不执行操作
if (node == null) {
return;
}
// 将当前结点的左子树加入队列
afterErgodic(node.left, keys);
// 将当前结点的右子树加入队列
afterErgodic(node.right, keys);
// 将当前结点的key加入队列
keys.add(node.key);
}
/**
* 层序遍历
*
* 原理
* (1) 使用队列的先进先出机制，将当前结点进行记录
* (2) 查找当前结点的左右子结点、加入队列，并将当前结点从队列中去除
* (3) 将左右子结点作为当前结点，循环继续(1)(2)步骤，直到队列中没有数据了
*
* @return 树中所有key的队列
*/
public Queue<K> layerErgodic() {
// 创建存储当前已查询的结点的key的队列
Queue<K> keyQueue = new LinkedList<>();
// 创建等待查询的子结点的结点队列
Queue<Node> nodeQueue = new LinkedList<>();
// 将根结点加入到队列中
nodeQueue.add(root);
// 当待查询队列中有数据时
while(!nodeQueue.isEmpty()) {
// 获取队列中保存的第一个结点
Node node = nodeQueue.remove();
// 保存该结点的key
keyQueue.add(node.key);
// 将左子结点加入到结点队列中
if (node.left != null) {
nodeQueue.add(node.left);
}
// 将右子结点加入到结点队列中
if (node.right != null) {
nodeQueue.add(node.right);
}
}
// 返回保存key的队列
return keyQueue;
}
/**
* 获取树的最大深度
*
* 原理
* (1) 分别查找左右子树的最大深度，取其中的大值+1即是以当前结点为根结点的子树的最大深度
*
* @return 最大深度
*/
public int maxDepth() {
// 调用重造方法
return maxDepth(root);
}
/**
* 获取树中某个结点的最大深度
*
* @return 最大深度
*/
private int maxDepth(Node node) {
// 如果结点不存在，返回0
if (node == null) {
return 0;
}
// 获取左子树的最大深度
int leftDepth = maxDepth(node.left);
// 获取右子树的最大深度
int rightDepth = maxDepth(node.right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
/**
* 获取二叉树存储的数据个数
*
* @return 存储的数据个数
*/
public int size() {
return N;
}
/**
* 校验key是否为空
*
* @param key 键
*/
private void validKey(K key) {
if (key == null) {
throw new NullPointerException("二叉树的键不能为null");
}
}
闽公网安备 35020302035485号
