二叉树：定义、遍历、查询、删除

青旅半醒 2021-08-11 20:53 285阅读 0赞

【一】二叉树

> 二叉树的相关概念  
> 满二叉树：如果二叉树的yezi节点都在最后一层，并且节点总数=2^n-1,n为层数  
> 完全二叉树：如果二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续。

【二】为什么提出二叉树

> 数组  
>     优点：通过下标形式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。  
>     缺点：如果检索某一个具体的值，或者插入值（按一定顺序整体移动），效率较低。  
> 链表  
>     优点：插入、删除元素速度较快。  
>     缺点：在进行检索是，效率较低。  
> 树  
>     能提高数据的存储读取的效率。对数据进行增删改查速度都比较快。

【三】二叉树功能

> 1.二叉树的先序、中序、后序遍历
> 
>   先序遍历：根节点->左子树->右子树  
>             先遍历当前节点，再判断当前节点的左子树是否为空，若不为空递归先序遍历；  
>             再遍历右子树，判断当前节点的右子树是否为空，若不为空递归先序遍历；  
>   中序遍历：左子树->根节点->右子树  
>             先遍历当前节点的左子树是否为空，若不为空递归中序遍历；  
>             若为空，输出当前节点  
>             再遍历右子树，判断当前节点的右子树是否为空，若不为空递归中序遍历；  
>   后序遍历：左子树->右子树->根节点  
>             先遍历当前节点的左子树是否为空，若不为空递归后序遍历；  
>             若为空，再遍历右子树，判断当前节点的右子树是否为空，若不为空递归后序遍历；  
>             若为空，输出当前节点
> 
>  2.查找指定的节点  
>      1>先序查找  
>          判断当前根节点是否为要查找的元素，如果是返回当前节点；  
>          如果不是，判断节点的左子节点是否为空，如果不为空，进行先序递归查找；如果找到，则返回节点；  
>          如果没有找到，对右子节点进行判断是否为空，如果不为空，进行先序查找的递归；如果找到，则返回节点；  
>          如果没有找到，返回null;  
>     2>中序查找：  
>         判断当前节点的左子节点是否为空，如果不为空，用中序递归查找；如果找到了，则返回节点；  
>         如果未找到，就和当前节点进行比较，如果是，则返回当前节点；  
>         如果不是，判断右子节点是否为空，如果不为空，进行中序递归查询，如果找到，则返回节点；  
>         如果没有找到，返回null;  
>     3>后序查找：  
>         判断当前节点的左子节点是否为空，如果不为空，用中序递归查找；如果找到了，则返回节点；  
>         如果未找到，判断右子节点是否为空，如果不为空，进行中序递归查询；如果找到了，则返回节点；  
>         如果未找到，就和当前节点进行比较，如果是，则返回当前节点；  
>         如果不是，返回null; 
> 
> 3. 删除  
>     删除一：  
>         1>如果要删除的节点为叶子节点（没有子节点的节点），则直接删除；  
>         2>如果要删除的节点不是叶子节点，则删除整个子树。  
>     删除二：  
>            1>如果要删除的节点为叶子节点，则直接删除  
>            2>如果要删除的节点为非叶子节点，则判断：  
>                如果该节点只有一个子节点，直接用子节点代替要删除的节点；  
>                如果该节点有两个子节点，则用左子节点代替要删除的节点，右子节点的位置不变；

【四】代码实现

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70][]

package tree.test;
    
    
    /*
    代码实现二叉树的先序、中序、后序遍历
    	先序遍历：根节点->左子树->右子树
    			先遍历当前节点，再判断当前节点的左子树是否为空，若不为空递归先序遍历；
    	 		再遍历右子树，判断当前节点的右子树是否为空，若不为空递归先序遍历；
    	中序遍历：左子树->根节点->右子树
    			先遍历当前节点的左子树是否为空，若不为空递归中序遍历；
    	 		若为空，输出当前节点
    			再遍历右子树，判断当前节点的右子树是否为空，若不为空递归中序遍历；
    	后序遍历：左子树->右子树->根节点
    			先遍历当前节点的左子树是否为空，若不为空递归后序遍历；
    	 		若为空，再遍历右子树，判断当前节点的右子树是否为空，若不为空递归后序遍历；
    	 		若为空，输出当前节点
    			
         查找指定的节点
     	1>先序查找
     		判断当前根节点是否为要查找的元素，如果是返回当前节点；
     		如果不是，判断节点的左子节点是否为空，如果不为空，进行先序递归查找；如果找到，则返回节点；
     		如果没有找到，对右子节点进行判断是否为空，如果不为空，进行先序查找的递归；如果找到，则返回节点；
     		如果没有找到，返回null;
    	2>中序查找：
    		判断当前节点的左子节点是否为空，如果不为空，用中序递归查找；如果找到了，则返回节点；
    		如果未找到，就和当前节点进行比较，如果是，则返回当前节点；
    		如果不是，判断右子节点是否为空，如果不为空，进行中序递归查询，如果找到，则返回节点；
    		如果没有找到，返回null;
    	3>后序查找：
    		判断当前节点的左子节点是否为空，如果不为空，用中序递归查找；如果找到了，则返回节点；
    		如果未找到，判断右子节点是否为空，如果不为空，进行中序递归查询；如果找到了，则返回节点；
    		如果未找到，就和当前节点进行比较，如果是，则返回当前节点；
    		如果不是，返回null;
        删除
    	删除一：
    		1>如果要删除的节点为叶子节点（没有子节点的节点），则直接删除；
    		2>如果要删除的节点不是叶子节点，则删除整个子树。
       	删除二：
       		1>如果要删除的节点为叶子节点，则直接删除
       		2>如果要删除的节点为非叶子节点，则判断：
       			如果该节点只有一个子节点，直接用子节点代替要删除的节点；
       			如果该节点有两个子节点，则用左子节点代替要删除的节点，右子节点的位置不变；
       						
    */
    
    public class TreeTest {
    	public static void main(String[] args) {
    		BinaryTree binarytree=new BinaryTree();
    		TreeNode root=new TreeNode(1,"红儿");
    		TreeNode node2=new TreeNode(2,"橙儿");
    		TreeNode node3=new TreeNode(3,"黄儿");
    		TreeNode node4=new TreeNode(4,"绿儿");
    		TreeNode node5=new TreeNode(5,"青儿");
    		TreeNode node6=new TreeNode(6,"蓝儿");
    		TreeNode node7=new TreeNode(7,"紫儿");
    		
    		binarytree.setRoot(root);
    		root.setLeft(node2);
    		root.setRight(node3);
    		node2.setLeft(node4);
    		node2.setRight(node5);
    		node3.setLeft(node6);
    		node3.setRight(node7);
    		
    		
    		System.out.println("======先序遍历");
    		binarytree.preOrder();
    		/*System.out.println("======中序遍历");
    		binarytree.infixOrder();
    		System.out.println("======后序遍历");
    		binarytree.pastOrder();
    		
    		System.out.println("------------先序查找");
    		TreeNode no1=binarytree.preOrderSearch(7);
    		System.out.println(no1.toString());
    		System.out.println("------------中序查找");
    		TreeNode no2=binarytree.infixOrderSearch(6);
    		System.out.println(no2.toString());
    		System.out.println("------------后序查找");
    		TreeNode no3=binarytree.pastOrderSearch(5);
    		System.out.println(no3.toString());
    		
    		System.out.println("+++++++++++++++删除一");
    		binarytree.deleteNode(7);
    		binarytree.preOrder();//1,2,4,5,3,6
    		
    		binarytree.deleteNode(6);
    		binarytree.preOrder();//1,2,4,5*/
    		System.out.println("+++++++++++++++删除二");
    		binarytree.deleteNode2(2);
    		binarytree.preOrder();
    	}
    }
    
    //定义一个二叉树
    class BinaryTree{
    	private TreeNode root;
    
    	public void setRoot(TreeNode root) {
    		this.root = root;
    	}
    	
    	//先序遍历
    	public void preOrder(){
    		if(this.root!=null) {
    			this.root.preOrder();
    		}else {
    			System.out.println("二叉树为空，无法遍历");
    		}
    	}
    	//中序遍历
    	public void infixOrder() {
    		if(this.root!=null) {
    			this.root.infixOrder();
    		}else {
    			System.out.println("二叉树为空，无法遍历");
    		}
    	}
    	//后序遍历
    	public void pastOrder() {
    		if(this.root!=null) {
    			this.root.pastOrder();
    		}else {
    			System.out.println("二叉树为空，无法遍历");
    		}
    	}
    	
    	//先序查询
    	public TreeNode preOrderSearch(int id) {
    		if(this.root!=null) {
    			return this.root.preOrderSearch(id);
    		}else {
    			return null;
    		}
    	}
    	
    	//中序查询
    	public TreeNode infixOrderSearch(int id) {
    		if(this.root!=null) {
    			return this.root.infixOrderSearch(id);
    		}else {
    			return null;
    		}
    	}
    	
    	//后序查询
    	public TreeNode pastOrderSearch(int id) {
    		if(this.root!=null) {
    			return this.root.pastOrderSearch(id);
    		}else {
    			return null;
    		}
    	}
    	//删除一
    	public void deleteNode(int id) {
    		if(root!=null) {
    			if(root.getId()==id) {
    				root=null;
    			}else {
    				root.deleteNode(id);
    			}
    		}else {
    			System.out.println("空树，不能删除...");
    		}
    	}
    	
    	//删除二
    	public void deleteNode2(int id) {
    		if(root!=null) {
    			if(root.getId()==id) {
    				if(root.getLeft()!=null) {
    					root=root.getLeft();
    				}else if(root.getLeft()==null&&root.getRight()!=null) {
    					root=root.getRight();
    				}else {
    					root=null;
    				}
    			}else {
    				root.deleteNode2(id);
    			}
    		}else {
    			System.out.println("空树，不能删除...");
    		}
    	}
    	
    }
    
    //定义节点
    class TreeNode{
    	private int id;
    	private String name;
    	private TreeNode left;
    	private TreeNode right;
    	public TreeNode(int id, String name) {
    		//super();
    		this.id = id;
    		this.name = name;
    	}
    	public int getId() {
    		return id;
    	}
    	public void setId(int id) {
    		this.id = id;
    	}
    	public String getName() {
    		return name;
    	}
    	public void setName(String name) {
    		this.name = name;
    	}
    	public TreeNode getLeft() {
    		return left;
    	}
    	public void setLeft(TreeNode left) {
    		this.left = left;
    	}
    	public TreeNode getRight() {
    		return right;
    	}
    	public void setRight(TreeNode right) {
    		this.right = right;
    	}
    	@Override
    	public String toString() {
    		return "TreeNode [id=" + id + ", name=" + name + "]";
    	}
    	
    	//先序遍历 
    	/*思想：先遍历当前节点，再判断当前节点的左子树是否为空，若不为空递归先序遍历；
    	 * 	      再遍历右子树，判断当前节点的右子树是否为空，若不为空递归先序遍历；
    	 * */
    	public void preOrder() {
    		System.out.println(this);
    		if(this.left!=null) {
    			this.left.preOrder();
    		}
    		if(this.right!=null) {
    			this.right.preOrder();
    		}
    	}
    	//中序遍历
    	/*思想：先遍历当前节点的左子树是否为空，若不为空递归中序遍历；
    	 * 	      若为空，输出当前节点
    	 * 	      再遍历右子树，判断当前节点的右子树是否为空，若不为空递归中序遍历；
    	 * */
    	public void infixOrder() {
    		if(this.left!=null) {
    			this.left.infixOrder();
    		}
    		System.out.println(this);
    		if(this.right!=null) {
    			this.right.infixOrder();
    		}
    	}
    	//后序遍历
    	/*思想：先遍历当前节点的左子树是否为空，若不为空递归后序遍历；
    	 * 	      若为空，再遍历右子树，判断当前节点的右子树是否为空，若不为空递归后序遍历；
    	 * 	      若为空，输出当前节点
    	 * 	      
    	 * */
    	public void pastOrder() {
    		if(this.left!=null) {
    			this.left.pastOrder();
    		}
    		if(this.right!=null) {
    			this.right.pastOrder();
    		}
    		System.out.println(this);
    	}
    	
    	//先序查询
    	public TreeNode preOrderSearch(int id) {
    		//判断当前根节点是否为要查找的元素，如果是返回当前节点；
    		if(this.id==id) {
    			return this;
    		}
     		//如果不是，判断节点的左子节点是否为空，如果不为空，进行先序递归查找；如果找到，则返回节点；
    		TreeNode node=null;
    		if(this.left!=null) {
    			node=this.left.preOrderSearch(id);
    		}
    		if(node!=null) {
    			return node;
    		}
     		//如果没有找到，对右子节点进行判断是否为空，如果不为空，进行先序查找的递归；如果找到，则返回节点；
    		if(this.right!=null) {
    			node=this.right.preOrderSearch(id);
    		}
     		//如果没有找到，返回null;
    		return node;
    	}
    	
    	//中序查询
    	public TreeNode infixOrderSearch(int id) {
    		//判断当前节点的左子节点是否为空，如果不为空，用中序递归查找；如果找到了，则返回节点；
    		TreeNode node=null;
    		if(this.left!=null) {
    			node=this.left.infixOrderSearch(id);
    		}
    		if(node!=null) {
    			return node;
    		}
    		//如果未找到，就和当前节点进行比较，如果是，则返回当前节点；
    		if(this.id==id) {
    			return this;
    		}
    		//如果不是，判断右子节点是否为空，如果不为空，进行中序递归查询，如果找到，则返回节点；
    		//如果没有找到，返回null;
    		if(this.right!=null) {
    			node=this.right.infixOrderSearch(id);
    		}
    		return node;
    	}
    	
    	//后序查询
    	public TreeNode pastOrderSearch(int id) {
    		//判断当前节点的左子节点是否为空，如果不为空，用中序递归查找；如果找到了，则返回节点；
    		TreeNode node=null;
    		if(this.left!=null) {
    			node=this.left.pastOrderSearch(id);
    		}
    		if(node!=null) {
    			return node;
    		}
    		//如果未找到，判断右子节点是否为空，如果不为空，进行中序递归查询；如果找到了，则返回节点；
    		if(this.right!=null) {
    			node=this.right.pastOrderSearch(id);
    		}
    		if(node!=null) {
    			return node;
    		}
    		//如果未找到，就和当前节点进行比较，如果是，则返回当前节点；
    		//如果不是，返回null;
    		if(this.id==id) {
    			return this;
    		}
    		return node;
    	}
    	
    	//删除一
    	/*思想：
    	 * 
    	 * 	判断当前节点的左子节点是否为要删除的节点，如果是，this.left=null;
    	 * 	如果不是，判断当前节点的右子节点是否为要删除的节点，如果是，this.right=null;
    	 * 	如果当前节点的左右子节点均不是要删除的节点，则需要左子树递归判断删除；
    	 * 	如果左子树递归没有删除节点，则需要右子树递归判断删除；
    	 * 	如果未找到删除的节点，直接返回；
    	 * */
    	public void deleteNode(int id) {
    		if(this.left!=null&&this.left.id==id) {
    			this.left=null;
    			return;
    		}
    		if(this.right!=null&&this.right.id==id) {
    			this.right=null;
    			return;
    		}
    		if(this.left!=null) {
    			this.left.deleteNode(id);
    		}
    		if(this.right!=null) {
    			this.right.deleteNode(id);
    		}
    	}
    	
    	//删除二
    	/*	判断当前节点的左子节点是否为要删除的节点，如果是，判断是否存在子节点，
    	 * 		如果不存在，直接this.left=null,
    	 * 		如果存在，判断是否存在左子节点，如果存在：this.left.right=this.right;this.left=this.left.left;
    	 * 		如果不存在，this.left=this.left.right;
    	 * 	如果不是，判断当前节点的右子节点是否为要删除的节点，如果是，判断是否存在子节点，
    	 * 		如果不存在，直接this.right=null,
    	 * 		如果存在，判断是否存在左子节点，如果存在：this.left.right=this.right;this.right=this.right.left;
    	 * 		如果不存在，this.right=this.right.right;
    	 * 	如果当前节点的左右子节点均不是要删除的节点，则需要左子树递归判断删除；
    	 * 	如果左子树递归没有删除节点，则需要右子树递归判断删除；
    	 * 	如果未找到删除的节点，直接返回；
    	 * 
    	 * */
    	public void deleteNode2(int id) {
    		if(this.left!=null&&this.left.id==id) {
    			if(this.left.left!=null&&this.left.right!=null) {
    				this.left.left.right=this.left.right;
    				this.left=this.left.left;
    				
    			}else if(this.left.left==null&&this.left.right!=null) {
    				this.left=this.left.right;
    			}else if(this.left.right==null&&this.left.left!=null){
    				this.left=this.left.left;
    			}else {
    				this.left=null;
    			}
    			return;
    		}
    		if(this.right!=null&&this.right.id==id) {
    			if(this.right.left!=null&& this.right.right!=null) {
    				this.right.left.right=this.right.right;
    				this.right=this.right.left;
    			}else if(this.right.left==null && this.right.right!=null) {
    				this.right=this.right.right;
    			}else if(this.right.right==null && this.right.left!=null){
    				this.right=this.right.left;
    			}else {
    				this.right=null;
    			}
    			return;
    		}
    		if(this.left!=null) {
    			this.left.deleteNode(id);
    		}
    		if(this.right!=null) {
    			this.right.deleteNode(id);
    		}
    	}
    }

【五】输出截图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70]: /images/20210811/85436e11cffd471784ae5f41918ae39e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70 1]: /images/20210811/1824050bac4e4fa4898142ce312f9339.png