树和二叉树

拼搏现实的明天。 2023-06-23 06:54 71阅读 0赞

##### 一、树的概述 #####

1.  树结构概述

根节点：该节点没有父节点
    
    双亲结点：有父节点和子节点
    
    子节点：一个节点的下面一个节点为子节点
    
    路劲：从根节点访问其他节点要经过的节点
    
    节点的度：一个节点后面的子节点数
    
    节点的权：该节点储存的数据
    
    叶子节点：没有子节点的节点子
    
    子树：除根节点外所有的节点以下的所有节点
    
    层：同一个节点的所有子节点所在的地方
    
    树的高度：从根节点开始到最远叶子节点的距离
    
    森林：由好多树组成

##### 二、二叉树 #####

1.  二叉树

二叉树：任何一个节点的子节点得数量不超过两个，子节点分为左节点的和右节点，并且不能调换位置。
    
    满二叉树：所有叶子节点都在最后一层，并且子节点得数量为2^n-1。（特殊的完全二叉树）
    
    完全二叉树：所有叶子节点都在最后一层或是倒数第二层，最后一层得叶子节点在左边连续，倒数第二层的叶子节点在右边连续。

1.  创建二叉树  
    先编写一个二叉树的节点类TreeNode，定义节点的权和左右儿子，和set方法。  
    编写一个根节点类，定义一个根节点，编写设置根节点方法和获取根节点方法。  
    编写二叉树测试类，首先创建一个二叉树和根节点，根节点赋值给二叉树，然后创建它的左右节点并赋值给根节点。

TreeNode：

package Tree;
    
    public class TreeNode {
             //二叉树节点
    	
    	//节点的权
    	int value;
    	
    	//左儿子
    	TreeNode leftNode;
    	
    	//右儿子
    	TreeNode rightNode;
    	
    	public TreeNode(int value) {
        
    		this.value = value;
    	}
    	
    	//设置左节点
    	public void setlNode(TreeNode leftNode) {
        
    		this.leftNode = leftNode;
    	}
    	
    	//设置右节点
    	public void setrNode(TreeNode rightNode) {
        
    		this.rightNode = rightNode;
    	}
    
    }

BinaryTree：

package Tree;
    
    public class BinaryTree {
             //根节点
    	
    	//根节点
    	TreeNode root;
    	
    	//设置根节点
    	public void setRoot(TreeNode root) {
        
    		this.root = root;
    	}
    	
    	//获取根节点
    	public TreeNode getRoot() {
        
    		return root;
    	}
    
    }

BinaryTreeTest：

package Tree;
    
    public class BinaryTreeTest {
        
    	
    	public static void main(String[] args) {
        
    		
    		//创建一个二叉树
    	BinaryTree binTree = new BinaryTree();
    	
    	//创建根节点
    	TreeNode root = new TreeNode(1);
    	
    	//把根节点赋给树
    	binTree.setRoot(root);
    	
    	//创建一个左节点
    	TreeNode rootL = new TreeNode(2);
    	//把创建的节点赋为根节点的左节点
    	root.setlNode(rootL);
    	
    	//创建一个右节点
    	TreeNode rootR = new TreeNode(3);
    	//把创建的节点赋为根节点的右节点
    	root.setrNode(rootR);
    	
    	}
    	
    }

1.  二叉树遍历

（1）先序遍历：先取根节点，再取左节点，最后取右节点。

//遍历二叉树
    	//先序遍历
    	binTree.frontShow();
    	System.out.println("******************************");
    
    
    public void frontShow() {
             //先序遍历
    		// TODO Auto-generated method stub
    		root.frontShow();
    		
    	}
    
    public void frontShow() {
            //先序遍历
    		// TODO Auto-generated method stub
    		
    		//遍历当前节点的内容
    		System.out.println(value);
    		
    		//递归遍历左节点
    		if(leftNode!=null) {
        
    			leftNode.frontShow();
    		}
    		
    		//递归遍历右节点
    		if(rightNode!=null) {
        
    			rightNode.frontShow();
    		}
    		
    	}

（2）中序遍历：先取左节点，再取根节点，最后取右节点。

//中序遍历
    	binTree.midShow();
    	System.out.println("******************************");
    
    public void midShow() {
              //中序遍历
    		// TODO Auto-generated method stub
    		root.midShow();
    		
    	}
    
    
    public void midShow() {
             //中序遍历
    		// TODO Auto-generated method stub
    		
    		//递归遍历左节点
    		if(leftNode!=null) {
        
    			leftNode.midShow();
    		}
    		
    		//遍历当前节点
    		System.out.println(value);
    		
    		//递归遍历右节点
    		if(rightNode!=null) {
        
    			rightNode.midShow();
    		}
    		
    	}

（3）后序遍历：先取右节点，再取左节点，最后取根节点。

//后序遍历
    	binTree.afterShow();
    
    public void afterShow() {
             //后序遍历
    		// TODO Auto-generated method stub
    		root.afterShow();
    		
    	}

1.  二叉树的查找

//前序查找
    	TreeNode result = binTree.frontSearch(5);
    	System.out.println(result);
    
    public TreeNode frontSearch(int i) {
            //前序查找
    		// TODO Auto-generated method stub
    		return root.frontSerach(i);
    	}
    
    public TreeNode frontSerach(int i) {
           //前序查找
    		// TODO Auto-generated method stub
    		//定义一个变量
    		TreeNode target = null;
    		//判断当前节点的值
    		if(value == i) {
        
    			return this;
    		}else {
        
    			//查找左儿子,判断左儿子书否为空
    			if(leftNode!=null) {
            //直接把查找到的值赋给变量
    				target = leftNode.frontSerach(i);
    			}
    			//判断该变量是否为空，不为空将其返回
    			if(target != null) {
        
    				return target;
    			}
    			//为空的话继续查找右儿子
    			if(rightNode != null) {
        
    				target = rightNode.frontSerach(i);
    			}
    		}
    		return target;
    	}

1.  删除子树

//删除节点
    	binTree.delete(2);
    	binTree.afterShow();
    
    public void delete(int i) {
             //删除节点
    		// TODO Auto-generated method stub
    		//先判断是不是根节点
    		if(root.value == i) {
        
    			root = null;
    		}else {
        
    			root.delete(i);
    		}
    		
    	}
    
    public void delete(int i) {
             //删除节点
    		// TODO Auto-generated method stub
    		TreeNode parent = this;
    		
    		//判断左儿子
    		if(parent.leftNode !=null&&parent.leftNode.value == i) {
        
    			parent.leftNode = null;
    			return;
    		}
    		//判断右儿子
    		if(parent.rightNode !=null&&parent.rightNode.value ==i) {
        
    			parent.rightNode = null;
    			return;
    		}
    		
    		//递归并检查删除左儿子
    		//将左儿子赋给父节点
    		parent = leftNode;
    		if(parent!=null) {
        
    			parent.delete(i);
    		}
    		
    		//递归检查并删除右儿子
    		parent = rightNode;
    		if(parent!=null) {
        
    			parent.delete(i);
    		}
    		
    		
    	}