思维导图
什么是二叉树：
在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。
二叉树特点：
•和链表一样，动态数据结构
•二叉树具有唯一根节点
•二叉树每个节点最多有2个孩子
•二叉树每个节点最多有一个父亲
•二叉树具有天然递归结构
•每个节点的左子树或右子树也是二叉树
•二叉树不一定是“满”的
二叉树种类：
图示：
二叉搜索树特点：
•二叉搜索树是二叉树
•每一颗子树也是二叉搜索树
•存储的元素必须有可比较性
•二叉搜索树的每个节点的值：大于其左子树的所有节点的值，小于其右子树的所有节点的值，如下图：
实现步骤：
代码实现：
public class BinarySearchTree<E extends Comparable<E>> {
//定义节点
private class Node {
private E e;
private Node left, right;//左右节点
public Node(E e) {
this.e = e;
}
}
private Node root;//根节点
private int size;//节点的个数
public BinarySearchTree() {
}
//获取节点的个数
public int size() {
return size;
}
//判断是否为空
public boolean isEmpty() {
return size == 0;
}
//增加一个值为e的节点
public void add(E e) {
root = add(root, e);
}
private Node add(Node node, E e) {
if (node == null) {
size++;
return new Node(e);
} else if (e.compareTo(node.e) < 0) {
node.left = add(node.left, e);
} else if (e.compareTo(node.e) > 0) {
node.right = add(node.right, e);
}
return node;
}
//是否包含值为e的节点
public boolean contains(E e) {
return contains(root, e);
}
private boolean contains(Node node, E e) {
if (node == null) {
return false;
}
if (e.compareTo(node.e) == 0) {
return true;
} else if (e.compareTo(node.e) < 0) {
return contains(node.left, e);
} else {
return contains(node.right, e);
}
}
}
删除节点：
要想删除一个节点，我们先聊一聊怎么获取最小最大节点。我们由二叉搜索树的定义知道：二叉搜索树的每个节点的值大于其左子树的所有节点的值，小于其右子树的所有节点的值，那么最小的值一定在最左下角的那个节点里，最大的值一定在最右下角的那个节点里，所以有以下代码：
//获取最小节点
public E getMinimum() {
if (size == 0) {
throw new IllegalArgumentException("BST is empty!!!");
}
return getMinimum(root).e;
}
private Node getMinimum(Node node) {
if (node.left == null) {
return node;
} else {
return getMinimum(node.left);
}
}
//获取最大节点
public E getMaximum() {
if (size == 0) {
throw new IllegalArgumentException("BST is empty!!!");
}
return getMaximum(root).e;
}
private Node getMaximum(Node node) {
if (node.right == null) {
return node;
} else {
return getMaximum(node.right);
}
}
那我们怎么删除一个值最小的节点或一颗最大的节点呢？
分2种情况：
•如果该最小(大)节点没有孩子，直接删除，下图最小节点13，最大节点42
•如果该最小(大)节点有右(左)孩子，将右(左)孩子上移到它的位置
转换成代码逻辑：如果当前节点的的左子树为null，代表该节点为最小节点，返回该节点的右子树(右子树为null返回的也是null,相当于直接删除该节点),不为null代表该节点不是最小节点，递归当前节点的左节点，最后返回当前节点(递归到底层再回溯)
上述为删除最小节点，删除最大节点与其原理相反。
//返回删除的最小节点值
public E removeMinimum() {
E ret = getMinimum();
removeMinimum(root);
return ret;
}
//删除二叉树中最小节点
private Node removeMinimum(Node node) {
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
node.left = removeMinimum(node.left);
return node;
}
//返回删除的最大节点值
public E removeMaximum() {
E ret = getMaximum();
removeMaximum(root);
return ret;
}
//删除二叉树中最大节点
private Node removeMaximum(Node node) {
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
node.right = removeMaximum(node.right);
return node;
}
好了，现在我们可以开始删除想删的节点了！
分3种情况：
•删除只有左孩子的节点
•删除只有右孩子的节点
•删除具有左孩子和右孩子的节点，如下图：
前两种均以在前面讨论过，这里只讨论第3种情况：
如果该节点既有左孩子又有右孩子，找到右孩子中值最小的节点，用它顶替该节点(当然也可以找到左孩子中值最大的节点，用它顶替该节点，2种方法2选1)由于前面我们写了怎么找树中最小节点或最小节点的方法，这里就可以拿来用啦
删除代码：
//删除包含指定值的节点
public void remove(E e) {
root = remove(root, e);
}
private Node remove(Node node, E e) {
if (node == null) {
return null;
}
if (e.compareTo(node.e) < 0) {
node.left = remove(node.left, e);
return node;
} else if (e.compareTo(node.e) > 0) {
node.right = remove(node.right, e);
return node;
} else {//e.compareTo(node.e) == 0
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
//代替的节点为node节点的右子树中最小节点
Node successsor = getMinimum(node.right);
//将node节点的右子树中的最小节点删除
//同时将删完最小节点的右子树赋予代替节点的右子树
successsor.right = removeMinimum(node.right);
//代替节点的左子树为node节点的左子树
successsor.left = node.left;
//断开node节点同二叉树的联系
node.left = node.right = null;
return successsor;
}
}
遍历：
前序遍历:
前序遍历（DLR）是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。
在源代码中加入以下代码：
//前序遍历
public void preOrder(){
preOrder(root);
}
private void preOrder(Node node){
if (node == null){
return;
}
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
中序遍历:
中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。
在源代码中加入以下代码：
//中序遍历
public void inOrder(){
inOrder(root);
}
private void inOrder(Node node) {
if (node == null){
return;
}
inOrder(node.left);
System.out.println(node.e);
inOrder(node.right);
}
后序遍历:
后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。
在源代码中加入以下代码：
//后序遍历
public void postOrder(){
postOrder(root);
}
private void postOrder(Node node) {
if (node == null){
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}
层序遍历：
层序遍历(广度优先遍历)除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
在源代码中加入以下代码：
//层序遍历
public void levelOrder(){
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
Node cur = queue.remove();
System.out.println(cur.e);
if(cur.left != null){
queue.add(cur.left);
}
if(cur.right != null){
queue.add(cur.right);
}
}
}
运行结果：
与预期相符。
网友评论