Java中二叉排序树

  1 package com.ietree.basic.datastructure.tree;
  2 
  3 import java.util.ArrayDeque;
  4 import java.util.ArrayList;
  5 import java.util.List;
  6 import java.util.Queue;
  7 
  8 /**
  9  * Created by ietree
 10  * 2017/5/1
 11  */
 12 public class SortedBinTree<T extends Comparable> {
 13 
 14     static class Node {
 15 
 16         Object data;
 17         Node parent;
 18         Node left;
 19         Node right;
 20 
 21         public Node(Object data, Node parent, Node left, Node right) {
 22             this.data = data;
 23             this.parent = parent;
 24             this.left = left;
 25             this.right = right;
 26         }
 27 
 28         public String toString() {
 29             return "[data=" + data + "]";
 30         }
 31 
 32         public boolean equals(Object obj) {
 33             if (this == obj) {
 34                 return true;
 35             }
 36             if (obj.getClass() == Node.class) {
 37                 Node target = (Node) obj;
 38                 return data.equals(target.data) && left == target.left && right == target.right && parent == target.parent;
 39             }
 40             return false;
 41         }
 42 
 43     }
 44 
 45     private Node root;
 46 
 47     // 两个构造器用于创建排序二叉树
 48     public SortedBinTree() {
 49         root = null;
 50     }
 51 
 52     public SortedBinTree(T o) {
 53         root = new Node(o, null, null, null);
 54     }
 55 
 56     // 添加节点
 57     public void add(T ele) {
 58         // 如果根节点为null
 59         if (root == null) {
 60             root = new Node(ele, null, null, null);
 61         } else {
 62             Node current = root;
 63             Node parent = null;
 64             int cmp = 0;
 65             // 搜索合适的叶子节点，以该叶子节点为父节点添加新节点
 66             do {
 67                 parent = current;
 68                 cmp = ele.compareTo(current.data);
 69                 // 如果新节点的值大于当前节点的值
 70                 if (cmp > 0) {
 71                     // 以右子节点作为当前节点
 72                     current = current.right;
 73                 } else {
 74                     // 如果新节点的值小于当前节点的值
 75                     // 以左节点作为当前节点
 76                     current = current.left;
 77                 }
 78             }
 79             while (current != null);
 80             // 创建新节点
 81             Node newNode = new Node(ele, parent, null, null);
 82             // 如果新节点的值大于父节点的值
 83             if (cmp > 0) {
 84                 // 新节点作为父节点的右子节点
 85                 parent.right = newNode;
 86             } else {
 87                 // 如果新节点的值小于父节点的值
 88                 // 新节点作为父节点的左子节点
 89                 parent.left = newNode;
 90             }
 91         }
 92     }
 93 
 94     // 删除节点
 95     public void remove(T ele) {
 96         // 获取要删除的节点
 97         Node target = getNode(ele);
 98         if (target == null) {
 99             return;
100         }
101         // 左、右子树为空
102         if (target.left == null && target.right == null) {
103             // 被删除节点是根节点
104             if (target == root) {
105                 root = null;
106             } else {
107                 // 被删除节点是父节点的左子节点
108                 if (target == target.parent.left) {
109                     // 将target的父节点的left设为null
110                     target.parent.left = null;
111                 } else {
112                     // 将target的父节点的right设为null
113                     target.parent.right = null;
114                 }
115                 target.parent = null;
116             }
117         } else if (target.left == null && target.right != null) {
118             // 左子树为空，右子树不为空
119             // 被删除节点是根节点
120             if (target == root) {
121                 root = target.right;
122             } else {
123                 // 被删除节点是父节点的左子节点
124                 if (target == target.parent.left) {
125                     // 让target的父节点的left指向target的右子树
126                     target.parent.left = target.right;
127                 } else {
128                     // 让target的父节点的right指向target的右子树
129                     target.parent.right = target.right;
130                 }
131                 // 让target的右子树的parent指向target的parent
132                 target.right.parent = target.parent;
133             }
134         } else if (target.left != null && target.right == null) {
135             // 左子树不为空，右子树为空
136             // 被删除节点是根节点
137             if (target == root) {
138                 root = target.left;
139             } else {
140                 // 被删除节点是父节点的左子节点
141                 if (target == target.parent.left) {
142                     // 让target的父节点的left指向target的左子树
143                     target.parent.left = target.left;
144                 } else {
145                     // 让target的父节点的right指向target的左子树
146                     target.parent.right = target.left;
147                 }
148                 // 让target的左子树的parent指向target的parent
149                 target.left.parent = target.parent;
150             }
151         } else {
152             // 左、右子树都不为空
153             // leftMaxNode用于保存target节点的左子树中值最大的节点
154             Node leftMaxNode = target.left;
155             // 搜索target节点的左子树中值最大的节点
156             while (leftMaxNode.right != null) {
157                 leftMaxNode = leftMaxNode.right;
158             }
159             // 从原来的子树中删除leftMaxNode节点
160             leftMaxNode.parent.right = null;
161             // 让leftMaxNode的parent指向target的parent
162             leftMaxNode.parent = target.parent;
163             // 被删除节点是父节点的左子节点
164             if (target == target.parent.left) {
165                 // 让target的父节点的left指向leftMaxNode
166                 target.parent.left = leftMaxNode;
167             } else {
168                 // 让target的父节点的right指向leftMaxNode
169                 target.parent.right = leftMaxNode;
170             }
171             leftMaxNode.left = target.left;
172             leftMaxNode.right = target.right;
173             target.parent = target.left = target.right = null;
174         }
175     }
176 
177     // 根据给定的值搜索节点
178     public Node getNode(T ele) {
179         // 从根节点开始搜索
180         Node p = root;
181         while (p != null) {
182             int cmp = ele.compareTo(p.data);
183             // 如果搜索的值小于当前p节点的值
184             if (cmp < 0) {
185                 // 向左子树搜索
186                 p = p.left;
187             } else if (cmp > 0) {
188                 // 如果搜索的值大于当前p节点的值
189                 // 向右子树搜索
190                 p = p.right;
191             } else {
192                 return p;
193             }
194         }
195         return null;
196     }
197 
198     // 广度优先遍历
199     public List<Node> breadthFirst() {
200 
201         Queue<Node> queue = new ArrayDeque<Node>();
202         List<Node> list = new ArrayList<Node>();
203         if (root != null) {
204             // 将根元素入“队列”
205             queue.offer(root);
206         }
207         while (!queue.isEmpty()) {
208             // 将该队列的“队尾”的元素添加到List中
209             list.add(queue.peek());
210             Node p = queue.poll();
211             // 如果左子节点不为null，将它加入“队列”
212             if (p.left != null) {
213                 queue.offer(p.left);
214             }
215             // 如果右子节点不为null，将它加入“队列”
216             if (p.right != null) {
217                 queue.offer(p.right);
218             }
219         }
220         return list;
221     }
222 
223 }

测试类：

 1 package com.ietree.basic.datastructure.tree;
 2 
 3 /**
 4  * Created by ietree
 5  * 2017/5/1
 6  */
 7 public class SortedBinTreeTest {
 8 
 9     public static void main(String[] args) {
10 
11         SortedBinTree<Integer> tree = new SortedBinTree<Integer>();
12 
13         // 添加节点
14         tree.add(5);
15         tree.add(20);
16         tree.add(10);
17         tree.add(3);
18         tree.add(8);
19         tree.add(15);
20         tree.add(30);
21 
22         System.out.println(tree.breadthFirst());
23         // 删除节点
24         tree.remove(20);
25         System.out.println(tree.breadthFirst());
26 
27     }
28 
29 }

程序输出：

[[data=5], [data=3], [data=20], [data=10], [data=30], [data=8], [data=15]]
[[data=5], [data=3], [data=15], [data=10], [data=30], [data=8]]

采用广度优先法则来遍历排序二叉树得到的不是有序序列，采用中序遍历来遍历排序二叉树才可以得到有序序列。