二叉搜索树+双向链表

  1 package data.structure.exercise;
  2 
  3 import java.util.LinkedList;
  4 
  5 public class BinaryTree {
  6     
  7     private TreeNode root;
  8     
  9     public BinaryTree(int root){
 10         this.setRoot(new TreeNode(root));
 11     }
 12     
 13     public TreeNode insert(int value){
 14         if(this.getRoot() == null){
 15             return null;
 16         }
 17         return insert(this.getRoot(), value);
 18     }
 19     
 20     private TreeNode insert(TreeNode node, int value){
 21         if(node == null){
 22             node = new TreeNode(value, null, null);
 23             return node;
 24         }
 25         
 26         if(value < node.value){
 27             TreeNode lnode = insert(node.getLnode(), value);
 28             node.setLnode(lnode);
 29         }else{
 30             TreeNode rnode = insert(node.getRnode(), value);
 31             node.setRnode(rnode);
 32         }
 33         
 34         return node;
 35     }
 36 
 37     public boolean find(TreeNode node, int value){
 38         if(node == null){
 39             return false;
 40         }
 41         
 42         if(value == node.value){
 43             return true;
 44         }else if(value < node.value){
 45             return find(node.getLnode(), value);
 46         }else{
 47             return find(node.getRnode(), value);
 48         }
 49         
 50     }
 51     
 52     public TreeNode findMax(TreeNode node) {  
 53         if(node!=null)  {  
 54             while(node.getRnode()!=null)  
 55                 node=node.getRnode();  
 56         }  
 57         return node;         
 58     } 
 59     
 60     public TreeNode remove(int value){
 61         return remove(this.getRoot(), value);
 62     }
 63     private TreeNode remove(TreeNode node, int value){
 64         if(node == null){
 65             return null;
 66         }
 67         
 68         if(value == node.value){
 69             
 70             if(node.getLnode() !=null && node.getRnode() !=null){
 71                 //左子树最大节点的parent
 72                 TreeNode parentOfMax = node.getLnode().getRnode();
 73                 while(parentOfMax.getRnode().getRnode() !=null){
 74                     parentOfMax = parentOfMax.getRnode();
 75                 }
 76                 //左子树最大的节点
 77                 TreeNode maxNode = parentOfMax.getRnode();
 78                 node.setValue(maxNode.getValue());
 79                 node.setRnode(remove(node.getRnode(), maxNode.getValue()));
 80             }
 81             else{
 82                 if(node.getLnode() !=null){
 83 
 84                     node = node.getLnode();
 85                 }else{
 86                     //node.getRnode() != null
 87                     node = node.getRnode();
 88                 }
 89             }
 90             
 91         }else if(value < node.value){
 92             node.setLnode(remove(node.getLnode(), value));
 93         }else{
 94             node.setRnode(remove(node.getRnode(), value));
 95         }
 96         return node;
 97     }
 98 
 99     public LinkedList<TreeNode> tree2LinkedList(){
100         return tree2LinkedList(this.getRoot());
101     }
102     
103     private LinkedList<TreeNode> tree2LinkedList(TreeNode root){
104         
105         LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
106         
107         dfs(root, queue);
108         
109         return queue;
110         
111     }
112     
113     private void dfs(TreeNode root, LinkedList<TreeNode> queue){
114         
115         if(root!=null){
116             dfs(root.getLnode(), queue);
117             queue.addLast(root);
118             dfs(root.getRnode(), queue);
119         }
120     }
121     
122     
123     public TreeNode getRoot() {
124         return root;
125     }
126 
127     public void setRoot(TreeNode root) {
128         this.root = root;
129     }
130 
131 
132     public class TreeNode{
133         
134         private int value;
135         
136         private TreeNode lnode;
137         
138         private TreeNode rnode;
139         
140         public TreeNode(int value){
141             this.value = value;
142         }
143         
144         public TreeNode(int value, TreeNode lnode, TreeNode rnode){
145             
146             this.setValue(value);
147             this.setLnode(lnode);
148             this.setRnode(rnode);
149         }
150 
151         public int getValue() {
152             return value;
153         }
154 
155         public void setValue(int value) {
156             this.value = value;
157         }
158 
159         public TreeNode getLnode() {
160             return lnode;
161         }
162 
163         public void setLnode(TreeNode lnode) {
164             this.lnode = lnode;
165         }
166 
167         public TreeNode getRnode() {
168             return rnode;
169         }
170 
171         public void setRnode(TreeNode rnode) {
172             this.rnode = rnode;
173         }
174 
175         @Override
176         public String toString() {
177             return "TreeNode [value=" + value + ", lnode=" + lnode + ", rnode=" + rnode + "]";
178         }
179         
180     }
181     
182     public static void main(String[] args){
183         BinaryTree tree = new BinaryTree(10);
184         tree.insert(6);
185         tree.insert(14);
186         tree.insert(4);
187         tree.insert(8);
188         tree.insert(12);
189         tree.insert(16);
190         
191         System.out.println("root.left: "+ tree.getRoot().getLnode().toString());
192         System.out.println("root.right: "+ tree.getRoot().getRnode().toString());
193         tree.remove(16);
194         System.out.println("root.right: "+tree.getRoot().getRnode().toString());
195         
196         LinkedList<TreeNode> treeNodes = tree.tree2LinkedList();
197         for(TreeNode node:treeNodes){
198             System.out.println(node);
199         }
200     }
201 }