模拟二叉查找树底层实现

蔚落 2024-02-18 21:11 74阅读 0赞

GitHub源码地址：（https://github.com/BradenLei/BST）

二叉查找树：当前结点的左子树所有结点值小于当前结点值，而右子树所有结点值都大于当前结点

实现方法：search()、insert()、delete()、前中后序遍历等。其中delete过程稍稍复杂。

接口：

package binary;
    
    public interface Tree<E> extends Iterable<E>{
        /**查找某个元素是否存在*/
    	public boolean search(E e);
    	/**插入元素*/
    	public boolean insert(E e);
    	/**删除元素*/
    	public boolean delete(E e);
    	
    	/**前序遍历*/
    	public void postorder();
    	/**中序遍历*/
    	public void inorder();
    	/**后序遍历*/
    	public void preorder();
    	/**获取元素个数*/
    	public int getSize();
    	/**树结构是否为空*/
    	public boolean isEmpty();
    }

抽象实现：

package binary;
    
    public abstract class AbstractTree<E> implements Tree<E> {
    
    	@Override
    	public void postorder() {
    		// TODO Auto-generated method stub
    		
    	}
    
    	@Override
    	public void inorder() {
    		// TODO Auto-generated method stub
    		
    	}
    
    	@Override
    	public void preorder() {
    		// TODO Auto-generated method stub
    		
    	}
    
    	@Override
    	public boolean isEmpty() {
    		return getSize() == 0;
    	}
    
    	
    }

实现代码：

package binary;
    
    import java.nio.file.Path;
    import java.util.ArrayList;
    import java.util.Iterator;
    import java.util.List;
    //二叉查找树实现
    public class BST<E extends Comparable<E>> extends AbstractTree<E> {
        protected TreeNode<E> root;
        protected int size = 0;
        
        public BST() {
        	
        }
        
        public BST(E[] objects) {
        	for (int i = 0; i < objects.length; i++) {
    			insert(objects[i]);
    		}
        }
        
        /**查找该树中是否存在目标元素*/
    	@Override
    	public boolean search(E e) {
    		TreeNode<E> current = root;
    		
    		while(current != null) {
    			if (e.compareTo(current.element) < 0) {
    				current = current.left;
    			}else if(e.compareTo(current.element) > 0) {
    				current = current.right;
    			}else {
    				return true;
    			}
    		}
    		return false;
    	}
    
    	/**返回true，则返回成功*/
    	@Override
    	public boolean insert(E e) {
    		if(root == null) {
    			root = createNewNode(e);
    		}else {
    			//locate the parent node
    			TreeNode<E> parent = null;
    			TreeNode<E> current = root;
    			while(current != null) {
    				if(e.compareTo(current.element) < 0) {
    					parent = current;
    					current = current.left;
    				}else if(e.compareTo(current.element) > 0) {
    					parent = current;
    					current = current.right;
    				}else {
    					return false;  //Duplicate node not inserted
    				}
    			}
    			
    			//create new node
    			if(e.compareTo(parent.element) < 0) {
    				parent.left = createNewNode(e);
    			}else {
    				parent.right = createNewNode(e);
    			}
    		}
    		
    		size++;
    		return true;
    	}
    	
    	protected TreeNode<E> createNewNode(E e){
    		return new TreeNode<>(e);
    	}
    
    	/**后序遍历*/
    	@Override
    	public void postorder() {
    		postorder(root);
    	}
    	protected void postorder(TreeNode<E> root) {
    		if(root == null) return;
    		postorder(root.left);
    		postorder(root.right);
    		System.out.print(root.element + " ");
    	}
    
    	/**中序遍历*/
    	@Override
    	public void inorder() {
    		inorder(root);
    	}
    	protected void inorder(TreeNode<E> root) {
    		if(root == null) return;
    		inorder(root.left);
    		System.out.print(root.element + " ");
    		inorder(root.right);
    	}
    
    	/**先序遍历*/
    	@Override
    	public void preorder() {
    		preorder(root);
    	}
    	protected void preorder(TreeNode<E> root) {
    		if(root == null) return;
    		System.out.print(root.element + " ");
    		preorder(root.left);
    		preorder(root.right);		
    	}
    
    	@Override
    	public int getSize() {
    		return size;
    	}
    	
    	/**返回根结点*/
    	public TreeNode<E> getRoot() {
    		return root;
    	}
    
    	/**Returns a path from the root leading to the specified element*/
    	public java.util.ArrayList<TreeNode<E>> path(E e){
    		ArrayList<TreeNode<E>> list = new ArrayList<>();
    		TreeNode<E> current = root;
    		
    		while(current != null) {
    			list.add(current);
    			if(e.compareTo(current.element) < 0) {
    				current = current.left;
    			}else if(e.compareTo(current.element) > 0) {
    				current = current.right;
    			}else 
    				break;
    		}
    		
    		return list;
    	}
    	
    	/**删除二叉树中的元素，成功返回true，失败返回false*/
    	@Override
    	public boolean delete(E e) {
    		//Locate the node to be deleted and alse locate its parent node
    		TreeNode<E> parent = null;
    		TreeNode<E> current = root;
    		while(current != null) {
    			if(e.compareTo(current.element) < 0) {
    				parent = current;
    				current = current.left;
    			}else if(e.compareTo(current.element) > 0) {
    				parent = current;
    				current = current.right;
    			}else 
    				break; 
    		}
    		
    		if(current == null)
    			return false;  //Element is not in the tree
    		
    		//Case 1 : current has no left child
    		if(current.left == null) {
    			//父结点连接当前删除结点的右结点
    			if(parent == null) {
    				root = current.right;
    			}else {
    				if(e.compareTo(parent.element) < 0)
    					parent.left = current.right;
    				else 
    					parent.right = current.right;
    			}
    		}
    		else {//Case 2: 定位当前删除结点的左子树的最大值(rightmost)以及其父结点，用rightmost替换删除结点值，同时删除rightmost
    			TreeNode<E> parentOfRightMost = current;
    			TreeNode<E> rightmost = current.left;
    			
    			while(rightmost.right != null) {
    				parentOfRightMost = rightmost;
    				rightmost = rightmost.right;
    			}
    			//Replace the element in current by the element in rightmost
    			current.element = rightmost.element;
    			
    			if(parentOfRightMost.right == rightmost)
    				parentOfRightMost.right = rightmost.left;
    			else //Special case : parentRightMost == current ， 必须考虑这种情况
    				parentOfRightMost.left = rightmost.left;
    		}
    		
    		size--;
    		return true;
    	}	
    	
    	/**清空二叉树*/
    	public void clear() {
    		root = null;
    		size = 0;
    	}
    	
    	/**遍历元素*/
    	@Override
    	public Iterator<E> iterator() {
    		return new InorderIterator();
    	}
    
    	//Inner class InorderIterator
    	private class InorderIterator implements java.util.Iterator<E>{
    		//arraylist做存储时，迭代器中的remove方法极不高效，因为每次都要重构二叉树（移动元素位置）
            private ArrayList<E> list = new ArrayList<>();
            private int current = 0;
            
            public InorderIterator() {
    			inorder();
    		}
            private void inorder() {
            	inorder(root);
            }
            private void inorder(TreeNode<E> root) {
            	if(root == null) return;
            	inorder(root.left);
            	list.add(root.element);
            	inorder(root.right);
            }
            
    		@Override
    		public boolean hasNext() {
    			if(current < list.size())
    				return true;
    			else 
    			    return false;
    		}
    
    		@Override
    		public E next() {
    			return list.get(current++);
    		}
    
    		@Override
    		public void remove() {
    			delete(list.get(current));
    			list.clear();
    			inorder();//Rebuild the list
    		}
    		
    	}
    	
    	/**结点声明*/
    	public static class TreeNode<E extends Comparable<E>>{
    		protected E element;
    		protected TreeNode<E> left;
    		protected TreeNode<E> right;
    		
    		public TreeNode(E e) {
    			element = e;
    		}
    	}
    }

测试代码：

package binary;
    
    import java.util.ArrayList;
    
    public class TestBST {
    
    	public static void main(String[] args) {
    		BST<String> tree = new BST<>();
    		tree.insert("George");
    		tree.insert("Michael");
    		tree.insert("Tom");
    		tree.insert("Adam");
    		tree.insert("Jones");
    		tree.insert("Peter");
    		tree.insert("Daniel");
    
    		System.out.print("Inorder: " );
    		tree.inorder();
    		System.out.print("\nPostorder: ");
    		tree.postorder();
    		System.out.print("\nPreorder: ");
    		tree.preorder();
    		System.out.print("\nThe number of nodes is " + tree.getSize());
    		
    		System.out.print("\nIs Peter in the tree? " + tree.search("Peter"));
    		
    		System.out.print("\nA path from the root to Peter is: ");
    		ArrayList<BST.TreeNode<String>> path = tree.path("Peter");
    		
    		for(int i = 0; path != null && i < path.size(); i++)
    			System.out.print(path.get(i).element + " ");
    		
    		Integer[] numbers = {2,4,3,1,8,5,6,7};
    		BST<Integer> intTree = new BST<>(numbers);
    		System.out.print("\nInorder: ");
    		intTree.inorder();
    	}
    
    }
    
    /**
    Inorder: Adam Daniel George Jones Michael Peter Tom 
    Postorder: Daniel Adam Jones Peter Tom Michael George 
    Preorder: George Adam Daniel Michael Jones Tom Peter 
    The number of nodes is 7
    Is Peter in the tree? true
    A path from the root to Peter is: George Michael Tom Peter 
    Inorder: 1 2 3 4 5 6 7 8 
     * */

\-------------------------------------------------------------------------------

拆分解析：

1、插入：从根结点开始尝试插入元素，判断该结点与当前根结点的大小，小于递归左子树，大于递归右子树，直到找到合适插入位置为止：

public boolean insert(E e) {
    		if(root == null) {
    			root = createNewNode(e);
    		}else {
    			//locate the parent node
    			TreeNode<E> parent = null;
    			TreeNode<E> current = root;
    			while(current != null) {
    				if(e.compareTo(current.element) < 0) {
    					parent = current;
    					current = current.left;
    				}else if(e.compareTo(current.element) > 0) {
    					parent = current;
    					current = current.right;
    				}else {
    					return false;  //Duplicate node not inserted
    				}
    			}
    			
    			//create new node
    			if(e.compareTo(parent.element) < 0) {
    				parent.left = createNewNode(e);
    			}else {
    				parent.right = createNewNode(e);
    			}
    		}
    		
    		size++;
    		return true;
    	}

2、删除：分两种情况：

1）当前结点没有左子节点，这时只需要将该结点的父结点与该结点的右子节点相连

2）当前结点current有左子节点。那么要找出左子节点中的最大元素的结点(rightMost指向)，而parentOfRightMost指向rightMost结点的父结点。使用rightMost中的值替换current中的值，然后删除rightMost指向的结点即可

public boolean delete(E e) {
    		//Locate the node to be deleted and alse locate its parent node
    		TreeNode<E> parent = null;
    		TreeNode<E> current = root;
    		while(current != null) {
    			if(e.compareTo(current.element) < 0) {
    				parent = current;
    				current = current.left;
    			}else if(e.compareTo(current.element) > 0) {
    				parent = current;
    				current = current.right;
    			}else 
    				break; 
    		}
    		
    		if(current == null)
    			return false;  //Element is not in the tree
    		
    		//Case 1 : current has no left child
    		if(current.left == null) {
    			//父结点连接当前删除结点的右结点
    			if(parent == null) {
    				root = current.right;
    			}else {
    				if(e.compareTo(parent.element) < 0)
    					parent.left = current.right;
    				else 
    					parent.right = current.right;
    			}
    		}
    		else {//Case 2: 定位当前删除结点的左子树的最大值(rightmost)以及其父结点，用rightmost替换删除结点值，同时删除rightmost
    			TreeNode<E> parentOfRightMost = current;
    			TreeNode<E> rightmost = current.left;
    			
    			while(rightmost.right != null) {
    				parentOfRightMost = rightmost;
    				rightmost = rightmost.right;
    			}
    			//Replace the element in current by the element in rightmost
    			current.element = rightmost.element;
    			
    			if(parentOfRightMost.right == rightmost)
    				parentOfRightMost.right = rightmost.left;
    			else //Special case : parentRightMost == current ， 必须考虑这种情况
    				parentOfRightMost.left = rightmost.left;
    		}
    		
    		size--;
    		return true;
    	}

测试删除操作：

package binary;
    
    public class TestBSTDelete {
    
    	public static void main(String[] args) {
            BST<String> tree = new BST<>();
    		tree.insert("George");
    		tree.insert("Michael");
    		tree.insert("Tom");
    		tree.insert("Adam");
    		tree.insert("Jones");
    		tree.insert("Peter");
    		tree.insert("Daniel");
    		printTree(tree);
    		
    		System.out.println("\nAfter delete George:");
    		tree.delete("George");
    		printTree(tree);
    		
    		System.out.println("\nAfter delete Adam:");
    		tree.delete("Adam");
    		printTree(tree);
    		
    		System.out.println("\nAfter Michael");
    		tree.delete("Michael");
    		printTree(tree);
    	}
    	
    	public static void printTree(BST tree) {
    		System.out.print("Inorder:(Sorted) " );
    		tree.inorder();
    		System.out.print("\nPostorder: ");
    		tree.postorder();
    		System.out.print("\nPreorder: ");
    		tree.preorder();
    		System.out.print("\nThe number of nodes is " + tree.getSize());
    		System.out.println();		
    	}
    }
    
    /**
    Inorder:(Sorted) Adam Daniel George Jones Michael Peter Tom 
    Postorder: Daniel Adam Jones Peter Tom Michael George 
    Preorder: George Adam Daniel Michael Jones Tom Peter 
    The number of nodes is 7
    
    After delete George:
    Inorder:(Sorted) Adam Daniel Jones Michael Peter Tom 
    Postorder: Adam Jones Peter Tom Michael Daniel 
    Preorder: Daniel Adam Michael Jones Tom Peter 
    The number of nodes is 6
    
    After delete Adam:
    Inorder:(Sorted) Daniel Jones Michael Peter Tom 
    Postorder: Jones Peter Tom Michael Daniel 
    Preorder: Daniel Michael Jones Tom Peter 
    The number of nodes is 5
    
    After Michael
    Inorder:(Sorted) Daniel Jones Peter Tom 
    Postorder: Peter Tom Jones Daniel 
    Preorder: Daniel Jones Tom Peter 
    The number of nodes is 4
    
     * */
     */