树(Tree):是n(n>=0)个结点的有限集,n=0,称为空树
在任意的非空树中:
定义树的时候
n(n>=0)个结点的有限集,n=0,称为空二叉树
特点
性质
存储结构
二叉树的遍历从根节点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次,且仅被访问一次
二叉树的访问次序可以分为4种:
class TreeNode<T>{ T data; //数据本身 TreeNode left; //左孩子 TreeNode right; //右孩子 public TreeNode(T data) { this.data = data; } //前序遍历 // 传入的参数就是根节点 public static void preorder(TreeNode root){ if(root == null){ return; } System.out.println(root.data); // 递归 preorder(root.left); preorder(root.right); } //中序遍历 public static void inorder(TreeNode root) { if(root == null){ return; } inorder(root.left); System.out.println(root.data); inorder(root.right); } // 后序 public static void postorder(TreeNode root){ if(root == null){ return; } postorder(root.left); postorder(root.right); System.out.println(root.data); } }
所有的结点都只有左子树的二叉树叫做左斜树,所有的结点都只有右子树的二叉树叫做右斜树
在一颗二叉树中,如果所有分支结点都在存在左子树和右子树,并且所有的叶子都在同一层上,这样的二叉树叫做满二叉树
特点
对一颗具有n个结点的二叉树按层编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉中编号为i的结点位置完全相同,则这棵二叉树称为完全二叉树
class Node { int value; Node left; Node right; public Node(int value) { this.value = value; } public static void preorder(Node head){ if(head != null){ Stack<Node> stack = new Stack<>(); stack.add(head); while(!stack.isEmpty()){ head = stack.pop(); System.out.print(head.value + "、"); if(head.right != null){ stack.push(head.right); } if(head.left != null){ stack.push(head.left); } } } System.out.println(); } }
含有形同结点的二叉树的不同形态,找出一个查找平均长度最小的一颗二叉查找树
自平衡的二叉树。又增加了一个颜色的属性。
结点的颜色只能是红色或黑色。
B-树是一种平衡多路查找树,它在文件系统中很有用。一棵m阶B-树
集合:容器,存放数据的一个容器
使用集合的目的:更方便的存储和操作数据,CRUD
List和Set继承自Collection,Map不是
import java.util.ArrayList; import java.util.Arrays; import java.util.List; /* ArrayList:内部结构是一个数组 */ public class Ch02 { public static void main(String[] args) { //创建一个ArrayList集合 //开发中一般情况下,使用多态创建集合 //向上转型 // ArrayList<Integer> l1 = new ArrayList<>(); List<Integer> l2 = new ArrayList<>(); //集合的新增 l2.add(1); l2.add(2); l2.add(3); l2.add(4); l2.add(5); l2.add(1,-1); // 从后新增 l2.addAll(l2); // 清空集合元素,集合中没有数据size==0,集合为null // l2.clear(); //直接打印集合对象 ArrayList里重写了toString方法,所有直接输出了集合对象,而不是地址 System.out.println(l2); //把下标为0的值改为200 l2.set(0,200); //集合和数组之间的转换 建议封装一个工具类 //数组-->集合 int[] arr = new int[]{1,2,3,4,5}; List<Integer> integers = Arrays.asList(1,2,3,4,5); System.out.println(integers); // List<int[]> arr1 = List.of(arr); // contains方法判断元素是否存在是根据元素的equals方法进行比较,若元素中没有重写equals方法,那么contains将比较对象 System.out.println(l2.contains(1)); //获取指定下标值 System.out.println(l2.get(0)); //判断是否是为空 System.out.println(l2.isEmpty()); //返回输入值的下标,没有就返回-1 System.out.println(l2.indexOf(1000)); } }
如果初始化集合尽量指定初始化容量,如果确定不了,默认指定为16
使用泛型,数据的类型时候,一定要使用引用数据类型
List集合中存放的数据: