二叉排序树的实现

清疚 2023-06-25 06:23 29阅读 0赞

#### 一、二叉排序树 ####

**1. 定义及性质：**

二叉排序树又称二叉查找树，它或者是一颗空树，或者具有一下性质的二叉树：  
（1）如果左子树不为空，那么左子树上面的所有节点的值都小于它的根节点的值。  
（2）如果右子树不为空，那么右子树上面的所有节点的值都大于它的根节点的值。  
（3）左右子树也分别为二叉排序树

**2. 代码实现：**

（1）先定义一个节点类，分别定义节点的权，左节点，右节点，和初始化构造方法

package tree;
    
    public class Node {
            //节点类
       //节点的权
       int data;
       
       //左节点
       Node left;
       
       //右节点
       Node right;
       
       //构造方法
       public Node(int data) {
        
       	this.data = data;
       	this.left = null;
       	this.right = null;
       	
       }
    
    }

（2）编写实现类BinaryTree，手下定义其根节点及其构造方法。

public class BinaryTree {
              //二叉排序树
    	//定义根节点
    	private Node root;
    	
    	//构造方法
    	public BinaryTree() {
        
    		root = null;
    	}

（3）插入节点  
首先创建一个新节点，判断头节点是否为空，如果为空则将新节点赋给头节点。  
反之定义一个当前节点和父节点，循环遍历查找元素插入的位置，根据二叉排序树的性质可知，插入结点的值小于其根节点的值，就可以将新节点赋给为空的左节点。  
反之，当插入节点的值大于根结点的值时，就可以将新节点赋给为空的右节点。

//插入节点
    	public void insert(int data) {
        
    		//创建一个新节点
    		Node newNode = new Node(data);
    		//判断头节点为空,将新节点赋给头节点
    		if(root == null) {
        
    			root = newNode;
    		}else {
        
    			Node current = root;   //当前节点
    			Node parent;     //根节点
    			while(true) {
                //寻找插入的位置
    				parent = current;     //将当前节点赋给父节点
    				if(data<current.data) {
              //如果插入节点的值小于当前节点的值
    					current = current.left;     //将当前节点的左节点赋给当前节点
    					if(current == null) {
        
    						parent.left = newNode;
    						return;
    					}
    				}else {
                                 //如果插入节点的值大于当前节点的值
    					current = current.right;    //将当前结点的右节点赋给当前节点
    					if(current == null) {
        
    						parent.right = newNode;
    						return;
    					}
    				}
    			}
    		}
    	}

（4）将数值插入到二叉树中  
循环依次将数据插入到二叉树中

//将数值插入到二叉树中
    	public void bulidTree(int[] data) {
        
    		for(int i=0;i<data.length;i++) {
        
    			insert(data[i]);
    		}
    	}

（5）先序遍历

//先序遍历方法递归实现
    	public void preOrder(Node localRoot) {
        
    		if(localRoot != null ) {
        
    			//遍历当前节点
    			System.out.print(localRoot.data+" ");
    			//递归遍历左节点
    			preOrder(localRoot.left);
    			//递归遍历右节点
    			preOrder(localRoot.right);
    		}
    	}
    	public void preOrder(){
        
    		this.preOrder(this.root);
    	}

（6）中序遍历

//中序遍历
    	public void inOrder(Node localRoot) {
        
    		if(localRoot != null) {
        
    			//递归遍历左节点
    			inOrder(localRoot.left);
    			//遍历当前节点
    			System.out.print(localRoot.data+" ");
    			//递归遍历右节点
    			inOrder(localRoot.right);
    		}
    	}
    	public void inOrder() {
        
    		this.inOrder(this.root);
    	}

（7）后序遍历

//后序遍历
    	public void postOrder(Node localRoot) {
        
    		if(localRoot != null) {
        
    			//递归遍历左节点
    			postOrder(localRoot.left);
    			//递归遍历右节点
    			postOrder(localRoot.right);
    			//遍历当前节点
    			System.out.print(localRoot.data+" ");
    		}
    	}
    	public void postOrder() {
        
    		postOrder(this.root);
    	}

（8）测试

//测试
    	public static void main(String[] args) {
        
    		
    		//创建一个二叉树
    		BinaryTree bin = new BinaryTree();
    		
    		//定义一个数组
    		int data[] = {
        4,1,7,5,2,8,6,3,9};
    		
    		//将数据插入到二叉树中
    		bin.bulidTree(data);
    		
    		//先序遍历
    		System.out.println("先序遍历:");
    		bin.preOrder();
    		System.out.println();
    		
    		//中序遍历
    		System.out.println("中序遍历：");
    		bin.inOrder();
    		System.out.println();
    		
    		//后续遍历
    		System.out.println("后序遍历：");
    		bin.postOrder();
    		System.out.println();
    		
    		
    	}

（9）运行截图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0NjQ2Mw_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0NjQ2Mw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191226184635378.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0NjQ2Mw==,size_16,color_FFFFFF,t_70