动手写一个二叉搜索树

绝地灬酷狼 2023-06-18 04:56 41阅读 0赞

前面已经手写了一个简单的[双向链表][Link 1]

在此基础上再写一个简单的二叉搜索树【这里仅简单实现】。二叉搜索树在结构上跟双向链表比较相似，将左节点看做左子树，将右节点看做父节点，只是多个右字数的对应。

package com.tree;
    
    import java.util.List;
    
    
    /** * 实现二叉搜索树（又叫二叉排序树） * 先思考正常情况，再考虑特殊情况，否则会进入到死胡同 * @author Tang * @param <T> */
    public class TreeTable<T extends Comparable<T>>{ 
    	
    	private TreeNode<T> rootNode;
    	private int size;
    
     
    	/** * 添加元素 * @param data */
        public void put(T data) { 
            TreeNode<T> newNode = new TreeNode<T>(data);
        	
            //如果根节点为空，直接赋值
        	if (rootNode == null){ 
        		rootNode = newNode;
        		size++;
        		return;
            }
        	
            int ret = 0;
            TreeNode<T> currentNode = rootNode;
            TreeNode<T> parentNode = null;
            
            while (true){ 
            	parentNode = currentNode;
                //每次插入都从根节点进行遍历，同时不断的更换对比节点。
                ret = data.compareTo(currentNode.data);
                
                if (ret < 0){ 
                	//插入的数据比当前节点小，获取当前节点的左节点，跟左节点进行比较。如果左节点为null，数据就直接插入到这里
                	currentNode = currentNode.leftNode;
                	if(currentNode == null){ 
                		parentNode.leftNode = newNode;
                		return;
                	}
                } else { 
                	//数据相等进行覆盖，不操作，所以这里只处理大于
                	currentNode = currentNode.rightNode;
                	if(currentNode == null){ 
                		parentNode.rightNode = newNode;
                		return;
                	}
                } 
            }
        }
        
        /** * 查找数据 * @param data * @return */
        public TreeNode get(T data){ 
        	TreeNode<T> currentNode = rootNode;
            int ret;
            //从根节点开始遍历。并且不断的切换需要比较的节点为currentNode
            while(currentNode != null){ 
                ret = data.compareTo(currentNode.data);
                if (ret < 0){ 
                	currentNode = currentNode.leftNode;
                } else if (ret > 0){ 
                	currentNode = currentNode.rightNode;
                } else { 
                	return currentNode;
                }
            }
            return null;
        }
        
        /** * 获取根节点 * @return */
        public TreeNode getRootNode(){ 
        	return rootNode;
        }
        
        
        /** * 遍历数据。这里是按照顺序进行遍历的。 */
        public void display() { 
            display(rootNode);
        }
        private void display(TreeNode node) { 
            if (node != null) { 
                display(node.leftNode);
                System.out.print(" " + node.data);
                display(node.rightNode);
            }
        }
        
        /** * 前序遍历<br> * 前序遍历的顺序是：根节点->左节点->右节点 * @param e 开始遍历元素 */
        public void prevIterator(TreeNode<T> node,List list){ 
            if (node != null) { 
                //System.out.print(node.data + " ");
                list.add(node);
                prevIterator(node.leftNode,list);
                prevIterator(node.rightNode,list);
            }
        }
        
        /** * 中序遍历 * @param e */
        public void midIterator(TreeNode<T> node,List list){ 
            if (node != null){ 
                midIterator(node.leftNode,list);
                //System.out.print(node.data + " ");
                list.add(node);
                midIterator(node.rightNode,list);
            }
        }
        
        /** * 后续遍历 * @param e 开始遍历元素 */
        public void subIterator(TreeNode<T> node,List list){ 
            if (node != null) { 
                subIterator(node.leftNode,list);
                subIterator(node.rightNode,list);
                //System.out.print(node.data + " ");
                list.add(node);
            }
        }
        
        /** * 删除指定的数据 * @param data */
        public boolean remove(T data){ 
        	TreeNode<T> delNode = get(data);
        	if(delNode == null){ 
        		return false;
        	}
        	TreeNode parentNode = delNode.parentNode;
        	//要删除的节点没有子节点，直接删除即可。
        	if(delNode.leftNode == null && delNode.rightNode == null){ 
        		if(delNode == rootNode){ 
        			rootNode = null;
        		} else { 
        			if(delNode == parentNode.leftNode){ //判断当前节点是左节点还是右节点
        				parentNode.leftNode = null;
        			} else { 
        				parentNode.rightNode = null;
        			}
        		}
        	//要删除的节点只有左节点
        	} else if(delNode.rightNode == null){ 
        		TreeNode leftNode = delNode.leftNode;
        		
        		if(delNode == parentNode.leftNode){ //如果当前删除的节点是左节点。直接对接即可
        			parentNode.leftNode = leftNode;
        		} else { 							//如果当前删除的节点是右节点。
        			parentNode.rightNode = leftNode;
        		}
        		leftNode.parentNode = parentNode;
        		
        	//要删除的节点只有右节点
        	} else if(delNode.leftNode == null){ 
        		TreeNode rightNode = delNode.rightNode;
        		if(delNode == parentNode.rightNode){ 
        			parentNode.rightNode = rightNode;
        		} else { 
        			parentNode.leftNode = rightNode;
        		}
        		
        	} else { 
        		
        	}
        	return true;
        }
        
    	
        
        /** * 构建树节点类 * @author T */
    	class TreeNode<T extends Comparable<T>>{ 
    		
    		private T data;
    		private TreeNode<T> leftNode;
    		private TreeNode<T> rightNode;
    		private TreeNode<T> parentNode;
    	
    		/** * @param data 节点的值 * @param parentNode 父节点 */
    		public TreeNode(T data,TreeNode<T> parentNode){ 
    			this.data = data;
    			this.parentNode = parentNode;
    		}
    		
    		public TreeNode(T data){ 
    			this.data = data;
    		}
    
    		public T getData() { 
    			return data;
    		}
    
    		public void setData(T data) { 
    			this.data = data;
    		}
    
    		public TreeNode getLeftNode() { 
    			return leftNode;
    		}
    
    		public void setLeftNode(TreeNode leftNode) { 
    			this.leftNode = leftNode;
    		}
    
    		public TreeNode getRightNode() { 
    			return rightNode;
    		}
    
    		public void setRightNode(TreeNode rightNode) { 
    			this.rightNode = rightNode;
    		}
    
    		public TreeNode getParentNode() { 
    			return parentNode;
    		}
    
    		public void setParentNode(TreeNode parentNode) { 
    			this.parentNode = parentNode;
    		}
    		
    	}
    
    }

测试：

package com.tree;
    
    import java.util.ArrayList;
    import java.util.List;
    
    import com.tree.TreeTable.TreeNode;
    
    public class TreeTableTest { 
    	
    	public static void main(String[] args) { 
    		TreeTable<Integer> tt = new TreeTable<Integer>();
    		
    		tt.put(3);
    		tt.put(8);
    		tt.put(1);
    		tt.put(10);
    		tt.put(5);
    		tt.put(9);
    		tt.put(7);
    		tt.put(18);
    		tt.put(30);
    		tt.put(25);
    		tt.put(38);
    		
    		tt.display();
    		System.out.println();
    		System.out.println("===========================");
    		System.out.println("获取根节点："+tt.getRootNode().getData());
    		
    		
    		//遍历的结果存储在list集合中
    		
    		//前序遍历
    		List<TreeNode> list = new ArrayList<TreeNode>();
    		tt.prevIterator(tt.getRootNode(),list);
    		System.out.println();
    		for(TreeNode node:list){ 
    			System.out.print(node.getData()+" ");
    		}
    		System.out.println("前序遍历完毕");
    		
    		
    		//中序遍历
    		list.clear();
    		tt.midIterator(tt.getRootNode(),list);
    		System.out.println();
    		for(TreeNode node:list){ 
    			System.out.print(node.getData()+" ");
    		}
    		System.out.println("中序遍历完毕");
    		
    		
    		//后续遍历
    		list.clear();
    		tt.subIterator(tt.getRootNode(),list);
    		System.out.println();
    		for(TreeNode node:list){ 
    			System.out.print(node.getData()+" ");
    		}
    		System.out.println("后续遍历完毕");
    	}
    
    }

结果：

1 3 5 7 8 9 10 18 25 30 38
    ===========================
    获取根节点：3
    
    3 1 8 5 7 10 9 18 30 25 38 前序遍历完毕
    
    1 3 5 7 8 9 10 18 25 30 38 中序遍历完毕
    
    1 7 5 9 25 38 30 18 10 8 3 后续遍历完毕

[Link 1]: https://blog.csdn.net/jinjin603/article/details/103066186