树和树的表示形式
树结构是非线性结构,主要是一个节点可以延伸出多个子节点,而每个子节点也只有一个父节点,类时的文件目录就是典型的树结构.
节点的度:表示的是一个节点的子树的个数.
树的表示形式类时链表,在链表中叫做头节点,而在树中就叫作根节点.知道根节点就可以得到树的其他子树.最常用的表示方法就是孩子表示法,创建的Node节点中存储的是当前节点的子树引用.
当然也可以使用其他的表示方法.例如双亲表示法(只有当前节点父节点的引用).
二叉树
二叉树就是一个节点的度不能大于2.
完全二叉树:简单来说就是在每一层节点中,第一个节点和最后一个节点之间不能有空节点.
二叉树的遍历方式
二叉树的遍历是基于递归.
先序遍历:当遍历到当前节点就将节点的值打印,然后开始遍历当前节点的左子树,遍历完左边再遍历右边.
中序遍历:当遍历到当前节点,先遍历左子树,直到左子树为空,然后开始打印节点的值,接下来遍历右子树.
后序遍历:遍历完左右子树,当左右都为空时,此时返回上一节点开始打印结点的值.
层序遍历:层序遍历使用孩子表示法需要使用一个队列,先将根节点入队列,然后依次出队列,出队列的同时将出队列节点的左右子树入队列(不为空).
先序遍历的第一个节点就是根节点,后序的最后一个节点就是头节点,当知道了根节点,在中序遍历中根节点的左右两边就是左右子树.
知道上面的规律,就可以通过中序遍历和前序遍历推断出后序遍历,知道后序遍历和中序就可以推断出前序遍历.
当知道中序和前序要还原出二叉树,先序的第一个节点是头节点,在中序中寻找这个节点,中序中的这个节点的左右就是树的左右子树,就可以在先序中寻找到左右子树的范围,再将左右子树的头节点找出,以此类推.就可以还原出二叉树.
二叉树中基本操作的实现
1)获取树中结点的个数:
1.可以设置一个全局变量size,用来统计节点的个数.
2.将当前节点的左子树的节点数加上右子树的节点数,再加上当前节点的个数.
static int size2(TreeNode root) {
if(root == null){
return 0;
}
int lsize = size2(root.left);
int rsize = size2(root.right);
return lsize+rsize+1;
}
2)获取树中的叶子节点:
1.设置一个全局size统计,当一个节点的左右子树都为null就表示这个节点为叶子节点.
2.将问题简化,求一棵树的叶子节点就是,求左右子树的叶子节点.
/*
获取叶子节点的个数：遍历思路
*/
public static int leafSize = 0;
static void getLeafNodeCount1(TreeNode root) {
if(root == null) return;
if(root.left==null && root.right == null) leafSize++;
getLeafNodeCount1(root.left);
getLeafNodeCount1(root.right);
}
/*
获取叶子节点的个数：子问题
*/
static int getLeafNodeCount2(TreeNode root) {
if(root==null) return 0;
if(root.left==null && root.right == null) return 1;
int l = getLeafNodeCount2(root.left);
int r = getLeafNodeCount2(root.right);
return l+r;
}
3)获取k层节点的个数
同样可以将获取k个节点的问题裁成获取k-1层节点的子节点,当k=1时,此时就只有一个节点.
static int getKLevelNodeCount(TreeNode root, int k) {
if(root == null || k == 0) return 0;
if(k==1) return 1;
int l = getKLevelNodeCount(root.left,k-1);
int r = getKLevelNodeCount(root.right,k-1);
return l+r;
}
4)获取二叉树的高度和检测value是否在树中
1.获取高度:可以简化问题,求树的高度就是求一个根节点的左右子树的高度最大值再加上根节点.
int getHeight(TreeNode root) {
if(root==null) return 0;
int left = getHeight(root.left);
int right = getHeight(root.right);
return Math.max(left,right)+1;
}
2.查询value是否在树中
TreeNode find(TreeNode root, char val) {
if(root == null) return null;
if(root.val == val) return root;
TreeNode left = find(root.left,val);
if(left!=null) return left;
TreeNode right = find(root.right,val);
return right;
}
5)进行层序遍历
static void levelOrder(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val);
if (node.left!=null)
queue.offer(node.left);
if (node.right!=null)
queue.offer(node.right);
}
}
反射,枚举,lambda表达式
1.反射
反射可以理解为'自省',也就是让自己认识到自己,在Java中就是让对象认识到自己.
在Java中,创建一个对象,在外人的视角看来只需要通过代码就可以看到这个对象中的元素,但是这个对象本身是不能知道的,为了让运行过程中某个对象也能够像外人一样看到对象中的元素,就引入了反射的概念.
Java/JVM提供了一组API,通过这组API(标准库中的各种类)拿到指定对象的信息.
反射的缺点是会影响效率,同时在后面维护的时候会更加麻烦(代码复杂).
2.枚举
枚举本身可以表示'可以列举的概念',通常也可以使用整数部分来替代枚举,例如1来表示男性,0表示女性.
在一般的代码中我们可以使用
public static final int man = 1;
main{
if(man*2 == 2)
}
这样的写法,但是这样的写法其实就被误用了,在逻辑上一个man*2是无意义的,所以为了防止这样的情况出现,Java就引入了枚举(enum)这个关键字.
enum关键字可以在创建类的时候自己进行选择:
枚举其实和类是相似的,里面可以有变量和方法:
3.lambda表达式
引入lambda表达式先要认识回调函数,回调函数就像是提前恰好的手雷,在我们需要时唤醒丢出.
"函数式接口"表示如果一个接口中只有一个抽象方法,此时就可以称这个接口为函数式接口.也可以称为匿名函数,也可以称为lambda表达式.
以代码为例:
使用lambda表达式就可以变成这样:
