JAVA BST的实现

  1 public class BinarySearchTree {
  2     TreeNode rootNode=null;
  3     private int size=0;
  4     public BinarySearchTree()
  5     {}
  6     public BinarySearchTree(int [] values)
  7     {
  8         for(int i=0;i<values.length;i++)
  9         {
 10             insert(values[i]);
 11         }
 12     }
 13     public int size()
 14     {
 15         System.out.println("size="+size);
 16         return size;
 17     }
 18     public void insert(int value)
 19     {
 20         if(rootNode==null)
 21         {
 22             rootNode=new TreeNode(value);
 23             size++;
 24             return;
 25         }
 26         TreeNode treeNode=new TreeNode(value);
 27         insert(rootNode, treeNode);
 28         size++;
 29     }
 30     /**
 31      * 每次插入的都是叶子节点
 32      * @param root
 33      * @param newNode
 34      */
 35     
 36     private void insert(TreeNode root,TreeNode newNode)
 37     {
 38         //没有左子树或右子树的情况
 39         if(root.left==null && root.value>newNode.value)
 40         {
 41             root.left=newNode;
 42             newNode.parent=root;
 43             return;
 44         }
 45         if(root.right==null && root.value<newNode.value)
 46         {
 47             root.right=newNode;
 48             newNode.parent=root;
 49         }
 50         if(root.value>newNode.value) insert(root.left,newNode);
 51         else if(root.value<newNode.value) insert(root.right,newNode);
 52     }
 53     
 54     /**
 55      * 删除节点的办法
 56      * 假如目标节点的左子树为空，直接将右子树的根取代目标节点
 57      * 假如目标节点的右子树为空，直接将左子树的根取代目标节点
 58      * 假如目标节点的左右子树都不为空，将左边子树的最右边的叶子节点  或  右子树的最左边的叶子节点取代目标节点
 59      * 这里取右子树最小值，共有两种情况
 60      * 1、这个最小值是叶子节点，
 61      * 2、这个最小值不是叶子节点，有一颗右子树
 62      * 对于第一种直接将叶子节点的值赋给要删除的节点，然后将双亲的左子树置空
 63      * 对于第二种将叶子节点的值赋给要删除的节点，接着将双亲的右子树指向被删节点的右子树。
 64      * 上面两种情况合起来就是假如有右子树，就将右子树链接到该节点的双亲上
 65      * @param value
 66      */
 67     public void delete(int value)
 68     {
 69         TreeNode node=searchNode(rootNode, value);
 70         if(node==null)
 71         {
 72             System.out.println("node "+value+" doesn't exist!");
 73             return;
 74         }
 75         size--;
 76         //如果左右子树都为空 直接获取双亲
 77         if(node.left==null && node.right==null)
 78         {
 79             System.out.println("左右为空");
 80             if(isLeftLeaf(node)) node.parent.left=null;//左子树
 81             else if(isRightLeaf(node)) node.parent.right=null;//右子树
 82             else rootNode=null;  //既没有子树，又没有双亲，只能是单个的根节点了，直接删除
 83             return;
 84         }
 85         
 86         //存在左子树
 87         if(node.left!=null && node.right==null)
 88         {
 89             System.out.println("存在左子树");
 90             if(isLeftLeaf(node)) node.parent.left=node.left;
 91             else if(isRightLeaf(node)) node.parent.right=node.left;
 92             else rootNode.left=node.left;
 93             return;
 94         }
 95         
 96         //存在右子树
 97         if(node.left==null && node.right!=null)
 98         {
 99             System.out.println("存在右子树");
100             if(isLeftLeaf(node)) node.parent.left=node.right;
101             else if(isRightLeaf(node)) node.parent.right=node.right;
102             else rootNode.right=node.right;
103             return;
104         }
105         
106         //左右子树都存在
107         if(node.left!=null && node.right!=null)
108         {
109             System.out.println("左右不为空");
110             TreeNode tempNode=node.right;
111             while(tempNode.left!=null)
112                 tempNode=tempNode.left;
113             //将该节点的值赋给node
114             node.value=tempNode.value;
115             
116             if(tempNode.right!=null)
117             {
118                 if(isLeftLeaf(tempNode)) tempNode.parent.left=tempNode.right;
119                 else if(isRightLeaf(tempNode)) tempNode.parent.right=tempNode.right;
120                 else rootNode.right=tempNode.right;
121             }
122             else 
123             {
124                 if(isLeftLeaf(tempNode)) tempNode.parent.left=null;//左子树
125                 else if(isRightLeaf(tempNode)) tempNode.parent.right=null;//右子树
126                 else rootNode=null;  //既没有子树，又没有双亲，只能是单个的根节点了，直接删除
127             }
128         }
129     }
130     //先判断是否有双亲，再判断该节点是否等于双亲的左子树
131     public boolean isLeftLeaf(TreeNode node)
132     {
133         
134         if(node.parent==null)
135             return false;
136         TreeNode leftNode=node.parent.left;
137         return leftNode==node;
138     }
139     
140     public boolean isRightLeaf(TreeNode node)
141     {
142         if(node.parent==null)
143             return false;
144         TreeNode rightNode=node.parent.right;
145         return rightNode==node;
146     }
147     
148     public void preOrder()
149     {
150         if(rootNode==null)
151         {
152             System.out.println("tree is null");
153             return ;
154         }
155         preOrder(rootNode);
156     }
157     
158     private void preOrder(TreeNode treeNode)
159     {
160         if(treeNode!=null)
161         {
162             System.out.println(treeNode.value);
163             preOrder(treeNode.left);
164             preOrder(treeNode.right);
165         }
166     }
167     
168     public TreeNode searchNode(int value)
169     {
170         return searchNode(rootNode,value);
171     }
172     
173     private TreeNode searchNode(TreeNode treeNode,int value)
174     {
175         if(treeNode==null)
176             return null;
177         if(value<treeNode.value)
178             return searchNode(treeNode.left, value);
179         else if(value>treeNode.value)
180             return searchNode(treeNode.right, value);
181         else
182             return treeNode;
183     }
184     
185     public void inOrder()
186     {
187         if(rootNode==null)
188         {
189             System.out.println("tree is null");
190             return ;
191         }
192         inOrder(rootNode);
193     }
194     
195     private void inOrder(TreeNode treeNode)
196     {
197         if(treeNode!=null)
198         {
199             inOrder(treeNode.left);
200             System.out.println(treeNode.value);
201             inOrder(treeNode.right);
202         }
203     }
204     
205     public class TreeNode
206     {
207         private int value;
208         TreeNode right;
209         TreeNode left;
210         TreeNode parent;
211         
212         public TreeNode()
213         {
214             this.value=0;
215         }
216         
217         public TreeNode(int value)
218         {
219             this.value=value;
220         }
221         
222         public int value()
223         {
224             return value;
225         }
226     }
227 }

      public static void main(String[] args) throws Exception{
          int[] data={16,6,2,5,1,18,7};
          BinarySearchTree bst=new BinarySearchTree(data);
          System.out.println(bst.searchNode(2).parent.value());
          System.out.println(bst.searchNode(6).right.value());
          bst.insert(17);
          System.out.println(bst.searchNode(17).parent.value());
          bst.insert(25);
          System.out.println(bst.searchNode(18).right.value());
          bst.delete(6);
          System.out.println(bst.searchNode(16).left.value());
          bst.delete(1);
          System.out.println(bst.searchNode(2).left);
          bst.delete(16);
          System.out.println(bst.searchNode(18).parent.value());
          bst.delete(18);
          System.out.println(bst.searchNode(17).right.value());
      }

6
7
18
25
左右不为空
7
左右为空
null
左右不为空
17
存在右子树
25