二分搜索树[数据结构与算法][Java]

为什么要研究树结构？

为什么要研究树结构？

树结构

  • 树结构本身是一种天然的组织结构
  • 将数据使用树结构存储后，出奇的高效

二分搜索树[Binary Search Tree]

  • 和链表一样，动态数据结构
1
2
3
4
5
Class Node{
	E e;
	Node left;
	Node right;
}
  • 二叉树(多叉树)

二叉树

  • 二叉树具有天然递归结构

  • 每一棵子树也是二分搜索树

  • 存储的元素必须有可比较性

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
//手动实现二分搜索树
package cn.Bst;
public class BST<E extends Comparable<E>>{

		private class Node{
			public E e;
			public Node left, right;
		
		public Node(E e) {
			this.e = e;
			left = null;
			right = null;
		}
		}

		private Node root;
		private int size;
		
		public BST() {
			root = null;
			size = 0;
		}
		
		public int size() {
			return size;
		}
		
		public boolean isEmpty() {
			return size == //手动实现二分搜索树
package cn.Bst;
public class BST<E extends Comparable<E>>{

		private class Node{
			public E e;
			public Node left, right;
		
		public Node(E e) {
			this.e = e;
			left = null;
			right = null;
		}
		}

		private Node root;
		private int size;
		
		public BST() {
			root = null;
			size = 0;
		}
		
		public int size() {
			return size;
		}
		
		public boolean isEmpty() {
			return size == 0;
		}		
}

二分搜索树添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//向以node为根的二分搜索树中插入元素E，递归算法
private void add(Node node,E e) {
	if (e.equals(node.e)) {
		return;
	}
	else if (e.compareTo(node.e) < 0 && node.left == null) {
		node.left = new Node(e);
		size ++;
		return;
	}
	else if (e.compareTo(node.e) > 0 && node.right == null) {
		node.right = new Node(e);
		size ++;
		return;
	}
	
	if (e.compareTo(node.e) < 0) {
		add(node.left,e);
	}//向以node为根的二分搜索树中插入元素E，递归算法
private void add(Node node,E e) {
	if (e.equals(node.e)) {
		return;
	}
	else if (e.compareTo(node.e) < 0 && node.left == null) {
		node.left = new Node(e);
		size ++;
		return;
	}
	else if (e.compareTo(node.e) > 0 && node.right == null) {
		node.right = new Node(e);
		size ++;
		return;
	}
	
	if (e.compareTo(node.e) < 0) {
		add(node.left,e);
	}else {
		add(node.right,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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package cn.Bst;
/**
 * 实现二分搜索树
 * @author HQF
 *
 * @param <E>
 */
public class BST<E extends Comparable<E>>{

		private class Node{
			public E e;
			public Node left, right;
		
		public Node(E e) {
			this.e = e;
			left = null;
			right = null;
		}
		
		}

		private Node root;
		private int size;
		
		public BST() {
			root = null;
			size = 0;
		}
		
		public int size() {
			return size;
		}
		
		public boolean isEmpty() {
			return size == 0;
		}
		
		//向二分搜索树中添加新的元素e
		public void add(E e) {
//			if (root == null) {
//				root = new Node(e);
//				size ++;
//			}
//			else {
//				add(root,e);
//			}
			root = add(root, e);
		}
		
		//向以node为根的二分搜索树中插入元素E，递归算法
		private Node add(Node node,E e) {
//			if (e.equals(node.e)) {
//				return;
//			}
//			else if (e.compareTo(node.e) < 0 && node.left == null) {
//				node.left = new Node(e);
//				size ++;
//				return;
//			}
//			else if (e.compareTo(node.e) > 0 && node.right == null) {
//				node.right = new Node(e);
//				size ++;
//				return;
//			}
			
			if (node == null) {
				return new Node(e);
			}
			
			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 {
				package cn.Bst;
/**
 * 实现二分搜索树
 * @author HQF
 *
 * @param <E>
 */
public class BST<E extends Comparable<E>>{

		private class Node{
			public E e;
			public Node left, right;
		
		public Node(E e) {
			this.e = e;
			left = null;
			right = null;
		}
		
		}

		private Node root;
		private int size;
		
		public BST() {
			root = null;
			size = 0;
		}
		
		public int size() {
			return size;
		}
		
		public boolean isEmpty() {
			return size == 0;
		}
		
		//向二分搜索树中添加新的元素e
		public void add(E e) {
//			if (root == null) {
//				root = new Node(e);
//				size ++;
//			}
//			else {
//				add(root,e);
//			}
			root = add(root, e);
		}
		
		//向以node为根的二分搜索树中插入元素E，递归算法
		private Node add(Node node,E e) {
//			if (e.equals(node.e)) {
//				return;
//			}
//			else if (e.compareTo(node.e) < 0 && node.left == null) {
//				node.left = new Node(e);
//				size ++;
//				return;
//			}
//			else if (e.compareTo(node.e) > 0 && node.right == null) {
//				node.right = new Node(e);
//				size ++;
//				return;
//			}
			
			if (node == null) {
				return new Node(e);
			}
			
			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);
			}
		}
		
}