排序二叉树

  1 package tree;
  2 import java.util.ArrayDeque;
  3 import java.util.ArrayList;
  4 import java.util.List;
  5 import java.util.Queue;
  6 public class SortedBinaryTree<T extends Comparable> {
  7     
  8     public static class Node<E>{
  9         E data;
 10         Node<E> parent;
 11         Node<E> left;
 12         Node<E> right;
 13         
 14         public Node() {}
 15         public Node(E data){
 16             this.data=data;
 17         }
 18         public Node(E data,Node<E> left,Node<E> right){
 19             this.data=data;
 20             this.left=left;
 21             this.right=right;
 22         }
 23         public Node(E data,Node<E> parent,Node<E> left,Node<E> right){
 24             this.data=data;
 25             this.parent=parent;
 26             this.left=left;
 27             this.right=right;
 28         }
 29         public boolean equals(Object obj){
 30             if(this==obj){
 31                 return true;
 32             }else if(this.getClass()==obj.getClass()){
 33                 Node<E> nodeObj=(Node<E>) obj;
 34                 return nodeObj.data.equals(data) && nodeObj.left==left && nodeObj.right==right;                    
 35             }
 36             return false;
 37         }
 38         public String toString(){
 39             return "[data="+data+"]";
 40         }
 41     }
 42     private Node<T> root;
 43     public SortedBinaryTree() {
 44         root=null;
 45     }
 46     public SortedBinaryTree(T data){
 47         root=new Node<T>(data);
 48     }
 49     
 50     //往排序二叉树中添加节点
 51     public void add(T element){
 52         Node<T> node=new Node<T>(element);
 53         if(root==null){
 54             root=node;
 55         }else {
 56             Node<T> current=root;
 57             Node<T> parent=null;
 58             int cmp=0;
 59             //循环找到可以被添加到的位置。
 60             while(current!=null){
 61                 parent=current;
 62                 cmp=element.compareTo(current.data);
 63                 //如果新节点大于当前节点
 64                 if(cmp>0){
 65                     //以右子节点作为当前节点
 66                     current=current.right;
 67                 }else {
 68                     current=current.left;
 69                 }
 70             }
 71             //如果新节点大于父节点的值
 72             if(cmp>0){
 73                 //新节点作为父节点的右子节点。
 74                 parent.right=node;
 75             }else {
 76                 parent.left=node;
 77             }
 78             node.parent=parent;
 79         }
 80     }
 81     //删除节点
 82     public void remove(T data){
 83         //获取要删除的节点
 84         Node<T> node=getNode(data);
 85         if(node==null){
 86             return;
 87         }
 88         boolean isLeftOfParent=isLeft(node);
 89         //如果删除的是叶子节点
 90         if(node.left==null && node.right==null){
 91             //如果该叶子节点就是根节点,即该树中只有一个根节点
 92             if(node==root){
 93                 root=null;
 94             }else if(isLeftOfParent){//被删除的节点是父节点的左子节点。
 95                 node.parent.left=null;//将被删除的节点的父节点的左子节点指针设为null
 96             }else {
 97                 node.parent.right=null;
 98             }
 99             //将被删除节点的父节点指针设为null
100             node.parent=null;
101         }else if(node.left!=null && node.right==null){//左子树不为空，右子节点为空
102             //被删除节点是根节点
103             if(root==node){
104                 root=node.left;
105             }else    if(isLeftOfParent){
106                 node.parent.left=node.left;            
107             }else {
108                 node.parent.right=node.left;                
109             }
110             node.parent=null;
111         }else if(node.left==null && node.right!=null){
112             if(node==root){
113                 root=node.right;
114             }else if(isLeftOfParent){
115                 node.parent.left=node.right;
116             }else {
117                 node.parent.right=node.right;
118             }
119             node.parent=null;
120         }else {
121             Node<T> leftMaxNode=node.left;
122             while(leftMaxNode.right!=null){
123                 leftMaxNode=leftMaxNode.right;
124             }
125             if(node!=root){            
126                 leftMaxNode.parent=node.parent;
127                 if(isLeftOfParent){//如果被删的节点是其父节点的左子节点，则重构其父节点的左子节点为leftMaxNode节点
128                     node.parent.left=leftMaxNode;
129                 }else {//如果被删的节点是其父节点的右子节点，则重构其父节点的右子节点为leftMaxNode节点
130                     node.parent.right=leftMaxNode;
131                 }
132             }else {//如果删除的节点就是根节点，则重构根节点为leftMaxNode，因为一颗树必须有根节点，以如中根节点分析
133                 root=leftMaxNode;
134             }
135             if(leftMaxNode!=node.left){//>必须判断<以图中节点10分析。
136                 //如果leftMaxNode节点就是其根结点的左子节点，就不能有下面的语句，否则会出现死循环
137                 leftMaxNode.left=node.left;
138                 //如果leftMaxNode节点就是其根结点的左子节点，就不能有下面的语句，否则删除其他的数据-->leftMaxNode.parent.right。
139                 leftMaxNode.parent.right=null;
140             }        
141             
142             leftMaxNode.right=node.right;        
143             node.parent=node.left=node.right=null;
144         }
145     }
146     private boolean isLeft(Node<T> node) {
147         if(node==root){
148             return false;
149         }else {
150             return node==node.parent.left;
151         }    
152     }
153     public Node<T> getNode(T data) {
154         Node<T> node=root;
155         while(node!=null){
156             int comp=data.compareTo(node.data);
157             if(comp>0){
158                 node=node.right;
159             }else if(comp<0){
160                 node=node.left;
161             }else {
162                 return node;
163             }
164         }
165         return null;
166     }
167     //广度优先遍历
168     public List<Node<T>> breadthFirst(){
169         Queue<Node<T>> queue=new ArrayDeque<Node<T>>();
170         List<Node<T>> list=new ArrayList<Node<T>>();
171         Node<T> tmp;
172         if(root!=null){
173             queue.offer(root);
174         }
175         while(!queue.isEmpty()){
176             list.add(queue.peek());
177             tmp=queue.poll();
178             if(tmp.left!=null){
179                 queue.offer(tmp.left);
180             }
181             if(tmp.right!=null){
182                 queue.offer(tmp.right);
183             }
184         }
185         return list;
186     }
187     //中序遍历
188     public List<Node> midIterator(){
189         return midIterator(root);
190     }
191     private List<Node> midIterator(Node root) {
192         List<Node> list=new ArrayList<Node>();
193         if(root==null){
194             return null;
195         }else{
196             if(root.left!=null){
197                 list.addAll(midIterator(root.left));
198             }
199             list.add(root);
200             if(root.right!=null){
201                 list.addAll(midIterator(root.right));
202             }
203             return list;
204         }
205     }
206 }

 1     public static void main(String[] args) {
 2         SortedBinaryTree<Integer> sortedBinaryTree=new SortedBinaryTree<Integer>();
 3         sortedBinaryTree.add(5);
 4         sortedBinaryTree.add(20);
 5         sortedBinaryTree.add(10);
 6         sortedBinaryTree.add(3);
 7         sortedBinaryTree.add(8);
 8         sortedBinaryTree.add(15);
 9         sortedBinaryTree.add(30);
10         System.out.println(sortedBinaryTree.breadthFirst());
11         System.out.println(sortedBinaryTree.midIterator());
12         sortedBinaryTree.remove(20);
13         System.out.println(sortedBinaryTree.breadthFirst());
14         System.out.println(sortedBinaryTree.midIterator());
15     }