二叉树
1. 基本概念
路径：顺着连接节点的边从一个节点走到另一个节点，所经过的节点的顺序排列就称为“路径”
根：树顶端的节点，一棵树只有一个根。
父节点：每个节点(除了根)都恰好有一条边向上连接到另一个节点，上面的这个节点就称为下面节点的“父节点”。
子节点：每个节点都可能有一条或多条边向下连接其他节点，下面的这些节点就称为它的“子节点”。
叶节点：没有子节点的节点
子树：每个节点都可以作为“子树”的根。
访问：当程序控制流程到达某个节点时，就称为“访问”这个节点。
遍历：遵循某种特定的顺序访问树中所有节点。
层：一个节点的层数是指从根开始到这个节点有多少“代”。
关键字：对象中的数据域
二叉树：树中每个节点最多只有两个子节点，且一个节点的左子节点的关键字值小于这个节点，右子节点的关键字值大于或等于这个父节点
2. 基本操作(增加、查询和删除)
2.1 定义一个节点Node
首先定义一个树中的节点类，该类包括数据域data以及，左子节点和右子节点
public class Node {
//数据域
public Object data;
//左子节点
public Node left;
//右子节点
public Node right;
public Node(Object data) {
this.data = data;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", left=" + left +
", right=" + right +
'}';
}
}
2.2 插入一个节点
节点定义好之后，首先来看插入操作，根据上边提到的二叉树的特点
一个节点的左子节点的关键字值小于这个节点，右子节点的关键字值大于或等于这个父节点
所以插入的时候要根据插入的数值与树中节点的数值大小，如果插入值小于树中节点的值就放左边，反之就放右边。
插入方法：
public boolean insert(T i){
//判断有没有父节点,没有就创建一个
if (root == null){
root = new Node(i);
return true;
}
Node current = root;
while (true){
//插入值比当前节点的值小
if (i.compareTo((T) current.data) < 0){
if (current.left != null){
current = current.left;
}else {
current.left = new Node(i);
break;
}
}else { //插入值大于等于当前节点的值
if (current.right != null){
current = current.right;
}else{
current.right = new Node(i);
break;
}
}
}
return true;
}
2.3 根据指定key值查询节点
查询方法同插入方法很像，只不过当没有查找到时，就返回空
查询方法：
public Node find(T key){
if (root == null){
return null;
}
Node current = root;
while (key.compareTo((T) current.data) != 0){
if (key.compareTo((T) current.data) < 0){
current = current.left;
}else {
current = current.right;
}
if (current == null){
return null;
}
}
return current;
}
还可以另外写一个只判断当前树是否包含指定关键字节点的方法
public boolean contains(T key){
return find(key) != null;
}
2.4 删除节点
删除的基本步骤如下：
- 找到要删除的节点
- 找到该节点的父节点
- 删除该节点，分三种情况：
(1). 节点没有子节点，在父节点中用null替换此节点
(2). 节点只有一个子节点，在父节点中，用唯一的子节点替换该节点
(3). 节点有两个子节点
先看找该节点的父节点代码：
public Node getParent(T key) {
Node current = find(key);
return (root == null || root == current) ? null : getParent(root, current);
}
private Node getParent(Node subTree, Node node) {
if (subTree == null) {
return null; //空子树，没有父节点
}
if (Objects.equals(subTree.left.data, node.data) || Objects.equals(subTree.right.data, node.data)) {
return subTree;
}
Node parent = null;
if (getParent(subTree.left, node) != null) {
parent = getParent(subTree.left, node);
return parent;
}
return getParent(subTree.right, node);
}
第一种情况，如果待删除节点只有一个孩子，那么直接把这一个孩子挂接在待删节点的父亲节点上即可。
第二种情况，如果待删除节点又两个孩子，那么待删除节点的后继节点一定在右子树上，并且该后继节点一定是右子树上最小的那个。把该后继节点中的值拷贝到待删除节点后，就变成了第一种情况，这时再删除后继节点即可。
如图所示
image
这里参考这个帖子如何找后继节点
link
全部删除代码
private void remove(Node n) {
Node parent = getParent((T) n.data);
Node next, child;
if (n.left == null && n.right == null) { //删除叶子节点
//考虑是否为root节点
if (n == root) {
root = null;
return;
}
if (n == parent.left) {
parent.left = null;
} else if (n == parent.right) {
parent.right = null;
}
} else if (n.left != null && n.right != null) {
next = successor(n);
n.data = next.data;
remove(next);
} else { //删除只有一个孩子的节点，把孩子交给爷爷
if (n.left != null) {
child = n.left;
} else {
child = n.right;
}
Node childParent = getParent((T) child.data);
if (n == root) {
childParent = null;
root = child;
return;
}
if (n == parent.left) {
childParent = parent;
parent.left = child;
} else {
childParent = parent;
parent.right = child;
}
}
}
3. 遍历
二叉树的遍历一般分为中序、前序还有后序遍历。
中序遍历：按照这个顺序访问整颗树，左子树 ---> 根结点 ---> 右子树
前序遍历：按照这个顺序访问整颗树，根结点 ---> 左子树 ---> 右子树
后序遍历：按照这个顺序访问整颗树，左子树 ---> 右子树 ---> 根结点
3.1 中序遍历
3.1.1递归法
遍历树最简单的方法是递归法，这个方法只需要做三件事：
- 调用自身来遍历节点的左子树
- 访问这个节点
- 调用自身来遍历节点的右子树
private void inOrderByRec(Node current){
if (current != null){
inOrderByRec(current.left);
System.out.println(current);
inOrderByRec(current.right);
}
}
3.1.2 非递归方法：
递归方法很简单，这里提供一种不用递归的解法。
先想我们人类对于这个问题的解法，我们会一直遍历这颗树，直到找到一个没有左子节点的节点，然后再找该节点的右子节点，然后一直循环，直到遍历整棵树。那么我们可以定义一个栈，用来存放我们在找左子节点的途中已经遍历过的节点，让这些节点依次入栈，等找到一个没有左子节点的节点时，将存放的节点出栈，继续找该节点的右子节点。
private void inOrder(Node root){
Stack<Node> stack = new Stack<>();
Node current = root;
while ( current != null || !stack.empty()){
if ( current != null){
stack.push(current);
current = current.left;
}else {
current = stack.pop();
System.out.println(current);
current =current.right;
}
}
}
3.2 前序遍历
3.2.1递归法
遍历树最简单的方法是递归法，这个方法只需要做三件事：
- 访问这个节点
- 调用自身来遍历节点的左子树
- 调用自身来遍历节点的右子树
private void preOrderByRec(Node current){
if (current != null){
System.out.println(current);
preOrderByRec(current.left);
preOrderByRec(current.right);
}
}
3.2.2 非递归方法：
private void preOrder(Node root){
Stack<Node> stack = new Stack<>();
Node current = root;
while ( current != null || !stack.empty()){
if ( current != null){
System.out.println(current);
stack.push(current);
current = current.left;
}else {
current = stack.pop();
current = current.right;
}
}
}
3.3 后序遍历
3.3.1 递归法
遍历树最简单的方法是递归法，这个方法只需要做三件事：
- 调用自身来遍历节点的左子树
- 调用自身来遍历节点的右子树
- 访问这个节点
private void postOrderByRec(Node current){
if (current != null){
preOrderByRec(current.left);
preOrderByRec(current.right);
System.out.println(current);
}
}
网友评论