java 实现二叉树

在计算机科学中，树是一种非常重要的数据结构，而且有非常广泛的应用，例如linux下的目录结构就可以看成是一棵树，另外树也是存储大量的数据一种解决方法，二叉排序树是树的一种特殊情形，它的每个节点之多只能有两个子节点，同时左子树的节点都小于它的父节点，右子树中的节点都大于它的父节点，二叉排序树在搜索中的应用非常广泛，同时二叉排序树的一个变种（红黑树）是java中TreeMap和TreeSet的实现基础。下边是二叉排序树的定义，其中用到了两个类，一个是Node类，代表树中的节点，另外一个是Name类，表示节点的数据，Name类实现Comparable接口，这样才可以比较节点的大小。

?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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142 public class BinarySearchTree{
private Node root;
private int size;

public BinarySearchTree(Node root){
this.root=root;
size++;
}

public int getSize(){
return this.size;
}

public boolean contains(Name name){
return contains(name,this.root);
//return false;
}

private boolean contains(Name n,Node root){
if(root==null){
return false;
}
int compare=n.compareTo(root.element);
if(compare>0){
if(root.right!=null){
return contains(n,root.right);
}else{
return false;
}
}else if(compare<0){
if(root.left!=null){
return contains(n,root.left);
}else{
return false;
}
}else{
return true;
}
}

public boolean insert(Name n){
boolean flag = insert(n,this.root);
if(flag) size++;
return flag;
}

private boolean insert(Name n,Node root){
if(root==null){
this.root=new Node(n);
return true;
}else if(root.element.compareTo(n)>0){
if(root.left!=null){
return insert(n,root.left);
}else{
root.left=new Node(n);
return true;
}
}else if(root.element.compareTo(n)<0){
if(root.right!=null){
return insert(n,root.right);
}else{
root.right=new Node(n);
return true;
}
}else{
root.frequency++;
return true;
}
}

public boolean remove(Name name){
root = remove(name,this.root);
if(root != null){
size--;
return true;
}
return false;
}

private Node remove(Name name,Node root){
int compare = root.element.compareTo(name);
if(compare == 0){
if(root.frequency>1){
root.frequency--;
}else{
/**根据删除节点的类型，分成以下几种情况
**①如果被删除的节点是叶子节点，直接删除
**②如果被删除的节点含有一个子节点，让指向该节点的指针指向他的儿子节点
**③如果被删除的节点含有两个子节点，找到左字数的最大节点，并替换该节点
**/
if(root.left == null && root.right == null){
root = null;
}else if(root.left !=null && root.right == null){
root = root.left;
}else if(root.left == null && root.right != null){
root = root.right;
}else{
//被删除的节点含有两个子节点
Node newRoot = root.left;
while (newRoot.left != null){
newRoot = newRoot.left;//找到左子树的最大节点
}
root.element = newRoot.element;
root.left = remove(root.element,root.left);
}
}
}else if(compare > 0){
if(root.left != null){
root.left = remove(name,root.left);
}else{
return null;
}
}else{
if(root.right != null){
root.right = remove(name,root.right);
}else{
return null;
}
}
return root;
}

public String toString(){
//中序遍历就可以输出树中节点的顺序
return toString(root);
}

private String toString(Node n){
String result = "";
if(n != null){
if(n.left != null){
result += toString(n.left);
}
result += n.element + " ";
if(n.right != null){
result += toString(n.right);
}
}
return result;
}

}



在二叉排序树的操作中，节点的删除时最难处理的，要分成很多种情况分别进行处理，下边是Node类和Name类的定义：

?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 class Node{
public Name element;
public Node left;
public Node right;
public int frequency = 1;

public Node(Name n){
this.element=n;
}
}

class Name implements Comparable<Name>{
private String firstName;
private String lastName;

public Name(String firstName,String lastName){
this.firstName=firstName;
this.lastName=lastName;
}

public int compareTo(Name n) {
int result = this.firstName.compareTo(n.firstName);
return result==0?this.lastName.compareTo(n.lastName):result;
}

public String toString(){
return firstName + "-" +lastName;
}
}



最后是二叉排序树的测试：

?1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 public static void main(String[] args){
//System.out.println("sunzhenxing");
Node root = new Node(new Name("sun","zhenxing5"));
BinarySearchTree bst =new BinarySearchTree(root);
bst.insert(new Name("sun","zhenxing3"));
bst.insert(new Name("sun","zhenxing7"));
bst.insert(new Name("sun","zhenxing2"));
bst.insert(new Name("sun","zhenxing4"));
bst.insert(new Name("sun","zhenxing6"));
bst.insert(new Name("sun","zhenxing8"));
System.out.println(bst);
bst.remove(new Name("sun","zhenxing2"));
System.out.println(bst);
bst.remove(new Name("sun","zhenxing7"));
System.out.println(bst);
}