java代码构建二叉树(二叉查找树)

怼烎@ 2022-10-07 05:58 199阅读 0赞

### 1. 前言 ###

#### 1.1 **二叉树定义** ####

> 二叉树是N个结点的有限集合，该集合或者为空集，或者由一个根节点跟两棵互不相交的、分别称为根节点的左子树或者右子树的二叉树组成。

#### 1.2 二叉树的特点 ####

*  每个结点最多有两个子树
 *  左子树跟右子树是有序的
 *  树中某个结点只有一棵子树,也要区分是左子树还是右子树

#### 1.3 二叉树的形态 ####

*  空二叉树
 *  只有一个根结点
 *  根结点只有左子树
 *  根结点只有右子树
 *  根结点既有左子树,又有右子树

### 2. java构建二叉树代码示例 ###

#### 2.1 二叉树的存储结构 ####

以二叉链表存储为例  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpamluZ2ppbmdjaG4_size_16_color_FFFFFF_t_70_pic_center]

#### 2.2 示例 ####

以下是构建一个普通二叉树的代码，根结点的左叶子结点会小于根结点，右叶子结点反之。

public class BinaryTree {
    
    	//根结点,默认为null
    	private Node root = null;
    
    	public Node getRoot() {
    		return root;
    	}
    
    	//通过内部类,构建结点
    	private class Node{
    		//左节点
    		private Node left;
    		//数据域
    		private int data;
    		//右节点
    		private Node right;
    
    		public Node(int data) {
    			this.data = data;
    		}
    
    		public Node getLeft() {
    			return left;
    		}
    
    		public void setLeft(Node left) {
    			this.left = left;
    		}
    
    		public int getData() {
    			return data;
    		}
    
    		public void setData(int data) {
    			this.data = data;
    		}
    
    		public Node getRight() {
    			return right;
    		}
    
    		public void setRight(Node right) {
    			this.right = right;
    		}
    	}
    
    
    	/**
    	 * 创建人:贺小五
    	 * 创建时间:2017-09-16 00:54:52
    	 * 描述:
    	 * 		构建二叉树
    	 * 	    Node 为结点,
    	 * 	    data 为数据
    	 */
    	private void buildBiTree(Node node,int data){
    		//如果根结点是空,那么设置根结点,并且设置数据域
    		if(root == null){
    			root = new Node(data);
    		}else{
    			/**
    			 * 根结点不为空,那么判断数据是否小于当前结点的数据
    			 */
    			if(data<node.getData()){
    				//如果小于,判断当前结点是否有左叶子结点
    				if(node.getLeft()==null){
    					//左叶子结点为空,设置左叶子结点,并且设置数据
    					node.setLeft(new Node(data));
    				}else{
    					//左叶子结点不为空,递归调用构建二叉树的函数
    					buildBiTree(node.getLeft(),data);
    				}
    			}else{
    				//如果大于或等于,判断当前结点是否存在右叶子结点
    				if(node.getRight()==null){
    					//右叶子结点为空,设置右叶子结点,并且设置数据域
    					node.setRight(new Node(data));
    				}else{
    					//右叶子几点不为空,递归调用构建二叉树的函数
    					buildBiTree(node.getRight(),data);
    				}
    			}
    		}
    	}
    
    	/**
    	 * 创建人:贺小五
    	 * 创建时间:2017-09-16 01:01:30
    	 * 描述:
    	 * 		创建二叉树函数
    	 * 		int[] 是个int类型的数组
    	 * 		通过循环调用,往二叉树插入数据
    	 */
    	public static BinaryTree createBiTree(int[] datas){
    		BinaryTree binaryTree = new BinaryTree();
    		for (int data : datas) {
    			binaryTree.buildBiTree(binaryTree.getRoot(),data);
    		}
    
    		return binaryTree;
    	}
    }

然后我们上一段测试代码，往该树插入数据：

public static void main(String[] args) {
    
    		int[] datas = {72,37,29,55,51,80};
    
    
    		BinaryTree biTree = BinaryTree.createBiTree(datas);
    
    	}

执行测试代码后,结构应该是如下图(测试的同学可以debug 看树的结构)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpamluZ2ppbmdjaG4_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpamluZ2ppbmdjaG4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221005/975dfb820457421983682e1f265d7647.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpamluZ2ppbmdjaG4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221005/6d7e0df6ebb34f5cbe9e09df1b087ee6.png