java实现二叉树的创建、前中后序遍历、以及查找删除等操作

Love The Way You Lie 2023-03-14 10:43 14阅读 0赞

## 源代码 ##

public class BinaryTreeDemo { 
    
    	public static void main(String[] args) { 
    		
    		// 创建二叉树
    		BinaryTree tree = new BinaryTree();
    		// 创建节点
    		Node root = new Node(1, "宋江");
    		Node node2 = new Node(2, "吴用");
    		Node node3 = new Node(3, "卢俊义");
    		Node node4 = new Node(4, "林冲");
    		
    		root.setLeft(node2);
    		root.setRight(node3);
    		node3.setRight(node4);
    		
    		tree.setRoot(root);
    		System.out.println("删除前，前序遍历：");
    		tree.preOrder();
    		tree.delNode(17);
    		System.out.println("删除后：");
    		tree.preOrder();
    		
    // System.out.println("中序遍历：");
    // tree.infixOrder();
    // System.out.println("后序遍历：");
    // tree.postOrder();
    // 
    // Node target = tree.postOrderSearch(40);
    // if(target != null) { 
    // System.out.println("\n找到了"+target);
    // }else { 
    // System.out.println("\n查无此人~~~");
    // }
    	}
    }
    
    // 定义二叉树
    class BinaryTree{ 
    	// 根节点
    	private Node root;
    	
    	public void setRoot(Node root) { 
    		this.root = root;
    	}
    	
    	// 删除叶子节点或子树
    	public void delNode(int no) { 
    		if(this.root != null) { 
    			// 如果根节点是要删除的，直接将根节点置为空
    			if(this.root.getNo() == no) { 
    				this.root = null;
    			}else { 
    				this.root.delNode(no);
    			}
    		}else { 
    			System.out.println("这是一棵空树!");
    		}
    	}
    	
    	// 前序遍历 
    	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 postOrder() { 
    		if(this.root != null) { 
    			this.root.postOrder();
    		}else { 
    			System.out.println("根节点为空，无法遍历!");
    		}
    	}
    	
    	// 前序查找 
    	public Node preOrderSearch(int no) { 
    		if(this.root != null) { 
    			return this.root.preOrderSearch(no);
    		}
    		return null;
    	}
    	// 中序查找 
    	public Node infixOrderSearch(int no) { 
    		if(this.root != null) { 
    			return this.root.infixOrderSearch(no);
    		}
    		return null;
    	}
    	// 后序查找 
    	public Node postOrderSearch(int no) { 
    		if(this.root != null) { 
    			return this.root.postOrderSearch(no);
    		}
    		return null;
    	}
    	
    }
    
    // 创建节点
    class Node{ 
    	private int no;
    	private String name;
    	private Node left;
    	private Node right;
    	
    	/** * * @param no * @param name */
    	public Node(int no,String name) { 
    		this.no = no;
    		this.name = name;
    	}
    	public int getNo() { 
    		return no;
    	}
    	public void setNo(int no) { 
    		this.no = no;
    	}
    	public String getName() { 
    		return name;
    	}
    	public void setName(String name) { 
    		this.name = name;
    	}
    	public Node getLeft() { 
    		return left;
    	}
    	public void setLeft(Node left) { 
    		this.left = left;
    	}
    	public Node getRight() { 
    		return right;
    	}
    	public void setRight(Node right) { 
    		this.right = right;
    	}
    	@Override
    	public String toString() { 
    		return "Node [no=" + no + ", 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 postOrder() { 
    		
    		// 如果左子节点不为空，递归前序遍历左子节点
    		if(this.left != null) { 
    			this.left.postOrder();
    		}
    		
    		// 同理如果右子节点不为空，递归前序遍历右子节点
    		if(this.right != null) { 
    			this.right.postOrder();
    		}
    		// 输出当前节点
    		System.out.println(this);
    	}
    	
    	// 前序查找 
    	public Node preOrderSearch(int no) { 
    		Node target = null;
    		if(this.no == no) { 
    			// 如果当前节点就是，直接返回
    			return this;
    		}
    		
    		// 如果左子节点为空，会抛出空指针异常
    		if(this.left != null) { 
    			target = this.left.preOrderSearch(no);
    		}
    		// 如果在左边找到了，返回目标
    		if(target != null) { 
    			return target;
    		}
    		
    		if(this.right != null) { 
    			target = this.right.preOrderSearch(no);
    		}
    		// 在右边，无论找没找到，都返回
    		return target;
    	}
    	// 中序查找 
    	public Node infixOrderSearch(int no) { 
    		Node target = null;
    		
    		if(this.left != null) { 
    			target = this.left.infixOrderSearch(no);
    		}
    		if(target != null) { 
    			return target;
    		}
    		
    		if(this.no == no) { 
    			return this;
    		}
    		
    		if(this.right != null) { 
    			target = this.right.infixOrderSearch(no);
    		}
    		return target;
    	}
    	// 后序查找 
    	public Node postOrderSearch(int no) { 
    		Node target = null;
    		
    		if(this.left != null) { 
    			target = this.left.postOrderSearch(no);
    		}
    		if(target != null) { 
    			return target;
    		}
    		
    		if(this.right != null) { 
    			target = this.right.postOrderSearch(no);
    		}
    		if(target != null) { 
    			return target;
    		}
    		
    		if(this.no == no) { 
    			return this;
    		}
    		return null;
    		
    	}
    	// 删除节点
    	public void delNode(int no) { 
    		// 判断左子节点是不是要删除的
    		if(this.left != null && this.left.no == no) { 
    			this.left = null;
    			return ;
    		}
    		// 判断右子节点是不是要删除的
    		if(this.right != null && this.right.no == no) { 
    			this.right = null;
    			return;
    		}
    		
    		// 如果左右子节点都不是，递归遍历左右子节点
    		if(this.left != null) { 
    			this.left.delNode(no);
    		}
    		if(this.right != null) { 
    			this.right.delNode(no);
    		}
    		
    	}
    }