二叉树的定义，它的子节点最多有两个(左节点，右节点)。二叉搜索树是二叉树中一个特殊的存在，它规定所有左侧节点的值都小于本节点，所有右侧节点的值都大于本节点。二叉搜索树对于关键值的查找非常快，执行效率是(lg N -- N)。
一 .节点类Node
class Node {
// 存放的数据
private int key;
// 左子节点
private Node left;
// 右子节点
private Node right;
public Node(int key) {
this.key = key;
}
@Override
public String toString() {
final StringBuilder sb = new StringBuilder("{");
sb.append("key=").append(key);
sb.append('}');
return sb.toString();
}
}
二. 插入节点
public void insert(int key) {
// 创建一个新节点
Node node = new Node(key);
Node parent = null;
Node temp = root;
// 标志 新节点插入 父节点的左侧还是右侧
boolean isLeft = true;
// 如果temp为空，表示新节点就插入在这个位置
while (temp != null) {
parent = temp;
// 如果小于temp.key，表示从左侧寻找插入位置
if (key < temp.key) {
isLeft = true;
temp = temp.left;
}
else {
isLeft = false;
temp = temp.right;
}
}
// 如果parent为空，表示root为空，新插入的节点作为root节点
if (parent == null) root = node;
else {
if (isLeft) parent.left = node;
else parent.right = node;
}
}
主要步骤：
- 创建一个新节点node。
- 创建三个局部变量parent、temp、isLeft。
因为我们的节点类Node没有指向父节点的引用，所以这个要有个parent局部变量，temp变量是用来遍历整个树的，isLeft变量是用标志当前temp是左节点还是右节点。
- 通过while循环找到新节点就插入的位置。
- 如果parent为空，表示root为空，新插入的节点作为root节点
- 如果parent不为空，那么根据isLeft的值，来决定新节点插入在父节点的左边还是右边。
三. 删除节点
对于二叉树来说，删除一个节点还是比较麻烦的。第一步我们还是有找到这个节点：
public Node remove(int key) {
Node parent = null;
Node temp = root;
boolean isLeft = true;
while (temp != null) {
// 相等，表示找到要删除的节点了
if (temp.key == key) {
removeNode(parent, temp, isLeft);
return temp;
}
parent = temp;
if (key < temp.key) {
isLeft = true;
temp = temp.left;
}
else {
isLeft = false;
temp = temp.right;
}
}
return null;
}
遍历树，找到与要删除的节点，然后调用removeNode方法进行删除操作。
要删除二叉树的一个节点，分三种情况：
- 被删除节点没有子节点，也就是说它是一个子叶节点。那就很简单了，直接删除这个节点，就是将它的父节点对应它的引用置位null就行了。
- 被删除节点有一个子节点。
如果被删除节点是父节点的左子节点，那么它的子节点一定是比父节点小的，直接使用被删除节点子节点取代删除节点就可以了。如果被删除节点是父节点的右子节点，流程一样。
- 被删除节点有两个子节点。
这个时候就比较麻烦了，你删除了本节点后，完全不知道，用那个子节点取代自己的位置。
根据搜索二叉树的定义规则，取代被删除节点的节点，也必须满足比被删除节点左节点的值都大，比被删除节点右边的值都小。这个就是它的后继节点，问题就变为寻找它的后继结点。
它的后继节点其实就是它右子节点的最小值，也就是右测最左边的值。
private Node findSuccessorNode(Node rightNode) {
// 如果rightNode的左子节点为空，那么它就是最小节点，直接返回它。
if (rightNode.left == null) return rightNode;
Node parent = rightNode;
Node successor = parent.left;
while (successor.left != null) {
parent = successor;
successor = successor.left;
}
// successor表示最小节点，它要取代被删除的节点，
//所以它的右节点移动到父节点左侧，它的右节点指向rightNode。
parent.left = successor.right;
successor.right = rightNode;
return successor;
}
这个方法就是寻找右侧最左边的值，即后继节点。
private void removeNode(Node parent, Node delNode, boolean isLeft) {
// 表示准备添加父节点的新子节点，取代被删除的节点位置
Node newNode;
// 如果被删除的节点 左右子节点都为空，那么就直接删除，所以这里的newNode为空，表示不会向父节点添加任何子节点
if (delNode.left == null && delNode.right == null) {
newNode = null;
} else if (delNode.left == null) {
// 如果被删除的节点 左子节点为空，那么 右子节点就取代删除的节点位置
newNode = delNode.right;
} else if (delNode.right == null) {
// 如果被删除的节点 右子节点为空，那么 左子节点就取代删除的节点位置
newNode = delNode.left;
} else {
// 如果左右子节点都不为空，那么就从右侧寻找后继节点，即最小值节点，用它取代删除的节点位置
newNode = findSuccessorNode(delNode.right);
newNode.left = delNode.left;
}
// parent为空，表示删除的是root节点，当然你也可以用delNode == root来判断。
if (parent == null) {
root = newNode;
} else {
if (isLeft) parent.left = newNode;
else parent.right = newNode;
}
}
newNode节点用来取代被删除节点，具体的判断逻辑与前面叙述的一样。
四. 用递归来遍历二叉树
4.1 前序遍历
public void preOrder(StringBuilder sb, Node node) {
if (node == null) return;
sb.append(node.key+" ");
preOrder(sb, node.left);
preOrder(sb, node.right);
}
4.2 中序遍历
public void inOrder(StringBuilder sb, Node node) {
if (node == null) return;
inOrder(sb, node.left);
sb.append(node.key+" ");
inOrder(sb, node.right);
}
4.3 后序遍历
public void postOrder(StringBuilder sb, Node node) {
if (node == null) return;
postOrder(sb, node.left);
postOrder(sb, node.right);
sb.append(node.key+" ");
}
五.用栈来遍历二叉树
5.1 前序遍历
private void preOrderByStack(StringBuilder sb, Node node) {
Stack<Node> stack = new Stack();
while (node != null || !stack.isEmpty()) {
if (node != null) {
sb.append(node.key+" ");
stack.push(node);
node = node.left;
} else {
Node temp = stack.pop();
node = temp.right;
}
}
}
5.2 中序遍历
private void inOrderByStack(StringBuilder sb, Node node) {
Stack<Node> stack = new Stack();
while (node != null || !stack.isEmpty()) {
if (node != null) {
stack.push(node);
node = node.left;
} else {
Node temp = stack.pop();
sb.append(temp.key+" ");
node = temp.right;
}
}
}
5.3 后序遍历
private void postOrderByStack(StringBuilder sb, Node node) {
if (node == null) return;
Stack<Node> stack = new Stack();
Stack<Node> tempStack = new Stack();
stack.push(node);
while (!stack.isEmpty()) {
node = stack.pop();
tempStack.push(node);
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
while (!tempStack.isEmpty()) {
node = tempStack.pop();
sb.append(node.key+" ");
}
}
附：源码
import tree.Stack;
import java.util.Random;
class SpendTime {
private long start = -1;
public SpendTime() {
start = System.currentTimeMillis();
}
public double getSpendSeconds() {
long times = System.currentTimeMillis() - start;
return times / 1000d;
}
public void priteTime(){
long times = System.currentTimeMillis() - start;
System.out.println();
System.out.println("花费了"+(times / 1000d)+"秒"+(times % 1000)+"毫秒");
}
}
public class TwoTree {
static class Node {
// 存放的数据
private int key;
// 左子节点
private Node left;
// 右子节点
private Node right;
public Node(int key) {
this.key = key;
}
@Override
public String toString() {
final StringBuilder sb = new StringBuilder("{");
sb.append("key=").append(key);
sb.append('}');
return sb.toString();
}
}
// 树的根节点
private Node root;
public void insert(int key) {
// 创建一个新节点
Node node = new Node(key);
Node parent = null;
Node temp = root;
// 标志 新节点插入 父节点的左侧还是右侧
boolean isLeft = true;
// 如果temp为空，表示新节点就插入在这个位置
while (temp != null) {
parent = temp;
// 如果小于temp.key，表示从左侧寻找插入位置
if (key < temp.key) {
isLeft = true;
temp = temp.left;
}
else {
isLeft = false;
temp = temp.right;
}
}
// 如果parent为空，表示root为空，新插入的节点作为root节点
if (parent == null) root = node;
else {
if (isLeft) parent.left = node;
else parent.right = node;
}
}
public Node remove(int key) {
Node parent = null;
Node temp = root;
boolean isLeft = true;
while (temp != null) {
// 相等，表示找到要删除的节点了
if (temp.key == key) {
removeNode(parent, temp, isLeft);
return temp;
}
parent = temp;
if (key < temp.key) {
isLeft = true;
temp = temp.left;
}
else {
isLeft = false;
temp = temp.right;
}
}
return null;
}
private void removeNode(Node parent, Node delNode, boolean isLeft) {
// 表示准备添加父节点的新子节点，取代被删除的节点位置
Node newNode;
// 如果被删除的节点 左右子节点都为空，那么就直接删除，所以这里的newNode为空，表示不会向父节点添加任何子节点
if (delNode.left == null && delNode.right == null) {
newNode = null;
} else if (delNode.left == null) {
// 如果被删除的节点 左子节点为空，那么 右子节点就取代删除的节点位置
newNode = delNode.right;
} else if (delNode.right == null) {
// 如果被删除的节点 右子节点为空，那么 左子节点就取代删除的节点位置
newNode = delNode.left;
} else {
// 如果左右子节点都不为空，那么就从右侧寻找后继节点，即最小值节点，用它取代删除的节点位置
newNode = findSuccessorNode(delNode.right);
newNode.left = delNode.left;
}
// parent为空，表示删除的是root节点，当然你也可以用delNode == root来判断。
if (parent == null) {
root = newNode;
} else {
if (isLeft) parent.left = newNode;
else parent.right = newNode;
}
}
private Node findSuccessorNode(Node rightNode) {
// 如果rightNode的左子节点为空，那么它就是最小节点，直接返回它。
if (rightNode.left == null) return rightNode;
Node parent = rightNode;
Node successor = parent.left;
while (successor.left != null) {
parent = successor;
successor = successor.left;
}
// successor表示最小节点，它要取代被删除的节点，所以它的右节点移动到父节点左侧，它的右节点指向rightNode。
parent.left = successor.right;
successor.right = rightNode;
return successor;
}
public void display() {
StringBuilder sb = new StringBuilder();
preOrder(sb, root);
System.out.println("前序："+sb.toString());
sb.delete(0, sb.length());
preOrderByStack(sb, root);
System.out.println("前序："+sb.toString());
System.out.println("-------------------------");
sb.delete(0, sb.length());
inOrder(sb, root);
System.out.println("中序："+sb.toString());
sb.delete(0, sb.length());
inOrderByStack(sb, root);
System.out.println("中序："+sb.toString());
System.out.println("-------------------------");
sb.delete(0, sb.length());
postOrder(sb, root);
System.out.println("后序："+sb.toString());
sb.delete(0, sb.length());
postOrderByStack(sb, root);
System.out.println("后序："+sb.toString());
}
public void preOrder(StringBuilder sb, Node node) {
if (node == null) return;
sb.append(node.key+" ");
preOrder(sb, node.left);
preOrder(sb, node.right);
}
private void preOrderByStack(StringBuilder sb, Node node) {
Stack<Node> stack = new Stack();
while (node != null || !stack.isEmpty()) {
if (node != null) {
sb.append(node.key+" ");
stack.push(node);
node = node.left;
} else {
Node temp = stack.pop();
node = temp.right;
}
}
}
public void inOrder(StringBuilder sb, Node node) {
if (node == null) return;
inOrder(sb, node.left);
sb.append(node.key+" ");
inOrder(sb, node.right);
}
private void inOrderByStack(StringBuilder sb, Node node) {
Stack<Node> stack = new Stack();
while (node != null || !stack.isEmpty()) {
if (node != null) {
stack.push(node);
node = node.left;
} else {
Node temp = stack.pop();
sb.append(temp.key+" ");
node = temp.right;
}
}
}
public void postOrder(StringBuilder sb, Node node) {
if (node == null) return;
postOrder(sb, node.left);
postOrder(sb, node.right);
sb.append(node.key+" ");
}
private void postOrderByStack(StringBuilder sb, Node node) {
if (node == null) return;
Stack<Node> stack = new Stack();
Stack<Node> tempStack = new Stack();
stack.push(node);
while (!stack.isEmpty()) {
node = stack.pop();
tempStack.push(node);
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
while (!tempStack.isEmpty()) {
node = tempStack.pop();
sb.append(node.key+" ");
}
}
private static int[] insertData(TwoTree twoTree, int n) {
Random random = new Random();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
// twoTree.insert(random.nextInt(1000));
twoTree.insert(i);
}
return arr;
}
public static void main(String[] args){
TwoTree twoTree = new TwoTree();
SpendTime spendTime = new SpendTime();
twoTree.insert(6);
twoTree.insert(7);
twoTree.insert(2);
twoTree.insert(3);
// twoTree.remove(7);
twoTree.insert(8);
twoTree.insert(1);
twoTree.insert(9);
twoTree.insert(4);
// twoTree.remove(2);
twoTree.insert(5);
twoTree.display();
spendTime.priteTime();
}
}
网友评论