Java：二叉搜索树-BinarySearchTree-前序遍历-中序遍历-后序遍历-层序遍历-删除节点_二叉查找树(binary search tree)的前序遍历结果数组

二叉查找树（Binary Search Tree）

一、定义

它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

如图：

二、添加

先找到需要添加的位置，然后add

public void add(E e) {
		if (rootNode == null) {
			rootNode = new Node<E>(e); return;
		}
		Node<E> node = rootNode;
		Node<E> parent = null;
		int compare = 0;
		//1、先找到需要添加的位置
		while (node != null) {
			parent = node;
			compare = compare(e,node.element);
			if ( compare> 0) {
				node = node.rightNode;
			}else if(compare <0) {
				node = node.leftNode;
			}else { //如果相等，直接替换data，并返回
				node.element = e; return;
			}
		}
		//2、在找到的位置上，判断添加左节点还是右节点
		if (compare >0) {
			parent.rightNode = new Node<E>(e);
		} else if (compare < 0){
			parent.leftNode = new Node<E>(e);
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

三、遍历

遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。树的遍历以下几种：

1、前序遍历：根节点–>左子树–>右子树

private static void forwardTraversal(Node node) {
		if (node == null) { return; }
		System.out.println(node.element);
		forwardTraversal(node.leftNode);
		forwardTraversal(node.rightNode);
}
1
2
3
4
5
6

2、中序遍历：左子树–>根节点–>右子树

private static void middleTraversal(Node node) {
		if (node == null) { return; }
		middleTraversal(node.leftNode);
		System.out.println(node.element);
		middleTraversal(node.rightNode);
}
1
2
3
4
5
6

3、后序遍历：左子树–>右子树–>根节点

private static void afterTraversal(Node node) {
		if (node == null) { return; }
		afterTraversal(node.leftNode);
		afterTraversal(node.rightNode);
		System.out.println(node.element);
}
1
2
3
4
5
6

4、层序遍历：将二叉树的每一层分别遍历，直到最后的叶子节点被全部遍历完。

层序遍历使用队列实现，因为要用到队列先进先出的特性

public static void levelTraversl(Node node) {
		Queue<Node> queue = new LinkedList();
		queue.offer(node);
		while (!queue.isEmpty()) {
			Node n = queue.poll();
			System.out.println(n.element);
			if (n.leftNode != null) {
				queue.offer(n.leftNode);
			}
			if (n.rightNode != null) {
				queue.offer(n.rightNode);
			}
		}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

四、前驱节点、后继节点

1、前驱节点

二叉树进行中序遍历，当前节点的前一个节点为该节点的前驱节点；

如下图前驱节点有三种情况：

• 有左子树：例如节点4，该节点的前驱节点就在他的左子树里面。
• 没有左子树，有父节点：例如1，7；节点1的祖先节点中找不见，他没有先驱节点。节点7有，祖先节点6

public static Node PrecursorNode(Node node) {
		if (node == null) {
			return null;
		}
		Node curNode = node.leftNode;
		//1,当该节点存在左子树时，前驱节点在左子数的最右边
		if (curNode != null) {
			while (curNode.rightNode != null) {
				curNode = curNode.rightNode;
			}
			return curNode;
		}
		//2,当该节点 不存在左子树 并且存在parent时，前驱节点可能在祖先节点中，也可能是他本身
		curNode = node;
		while (curNode.parentNode !=null && curNode == curNode.parentNode.leftNode) {
			curNode = curNode.parentNode;
		}

		//3,这里有两种情况，第一，该节点是最左边的节点，他没有前驱节点，返回空，
		// 第二，给节点的祖先节点中有前驱节点
		return curNode.parentNode;
	}
	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2、后继节点

二叉树中序遍历，当前节点的后一个节点为该节点的后继节点；

public static Node succeedNode(Node node) {
		if (node == null) {
			return null;
		}
		Node tempNode = node.rightNode;
		if (tempNode != null) {
			while (tempNode.leftNode != null) {
				tempNode = tempNode.leftNode;
			}
			return tempNode;
		}
		//要重新赋值
		tempNode = node;
		//没有右子树
		while (tempNode.parentNode != null && tempNode == tempNode.parentNode.rightNode) {
			tempNode = tempNode.parentNode;
		}
		return tempNode.parentNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

五、删除节点

分三大类，删除度为2的节点；度为1 的节点，度为0的节点，代码可以优化，但是为了逻辑清晰，没做优化处理

public static void remove(Node node) {
		if (node == null) {
			return;
		}
		//1、该节点度为2，就是有左右子树的节点
		if (node.leftNode != null && node.rightNode != null) {
			//2、先找到前驱或者后继节点
			Node sn = succeedNode(node);
			node.element = sn.element;
			if (sn == sn.parentNode.leftNode) {
				sn.parentNode.leftNode = null;
			} else {
				sn.parentNode.rightNode = null;
			}
		} 
		//度为0的节点
		else if (node.leftNode == null && node.rightNode == null) {
			if (node.parentNode != null) {
				if (node == node.parentNode.leftNode) {
					node.parentNode.leftNode = null;
				} else {
					node.parentNode.rightNode = null;
				}
			} else {
				root = null;
			}
		//	度为1的节点
		} else {
			Node replacelement = node.leftNode != null ? node.leftNode : node.rightNode;
			if (node.parentNode != null) {
				replacelement.parentNode = node.parentNode;
				if (node == node.parentNode.leftNode) {
					node.parentNode.leftNode = replacelement;
				} else {
					node.parentNode.rightNode = replacelement;
				}
			} else {
				root = replacelement;
			}
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41