Java学习总结 2020/4/20_学java课程的心得体会和收获

数据结构

1. 树

n个结点构成的有限集合，对于任意一个非空树，具有以下性质：

·树中有一个称为根的特殊结点

·其余结点可分为m个互不相交的有限集合，其中每个集合也是一棵树，称为原来树的子树

·树没有回路，除了根结点，只有一个父结点

2. 二叉树

二叉树是每个结点最多有两个子树的树结构。

特殊的二叉树：平衡二叉树，每一个结点的左右子树的高度差不超过1。

二叉树的遍历：

树的遍历都是先左，再右，区别就是打印顺序不同，对该二叉树遍历结果如下：

·先序遍历

public void preOrder(TreeNode root) {

    if (root == null) //树为空的情况

      return;

    System.out.print(root.getValue()); //先输出根

    preOrder(root.getLeft()); //再前序遍历左子树

    preOrder(root.getRight()); //再前序遍历右子树

  }

遍历结果为：A->B->D->F->H->C->G

·中序遍历

public void inOrder(TreeNode root) {

    if (root == null) {

      return;

    }

    inOrder(root.getLeft()); //先中序遍历左子树

    System.out.print(root.getValue());//再输出根

    inOrder(root.getRight()); //再中序遍历右子树

  }

遍历结果为：D->B->H->F->A->C->G

后序遍历：

public void postOrder(TreeNode root) {

    if (root == null) {

      return;

    }

    postOrder(root.getLeft()); //先后序遍历左子树

    postOrder(root.getRight()); //再后序遍历右子树

    System.out.print(root.getValue());//再输出根

  }

遍历结果：D->H->F->B->G->C->A

3. 二叉搜索树

或者是一棵空树，或者是具有下列性质的二叉树

·若左子树不空，则左子树上所有结点的值均小于它的根结点的值

·若右子树不空，则右子树上所有结点的值均大于它的根结点的值

·左、右子树也分别为二叉排序树

插入操作：判断与根结点值是否相同，相同则返回已有元素，不同就判断大小，并迭代递归左右子树，直到找到相同元素或者子结点为null，把该元素插入子结点位置。

删除操作：在迭代找到要删除的点的位置之后，需要考虑三种情况

·要删除的结点没有子节点，也就是叶子结点，那就可以直接删除，如上图5、9号点

·要删除的结点只有一个子节点，就将其子结点换到要删除的结点的位置上，如要删除6号结点，就可以把6号删除，再把5号放到这个位置上

·要删除的结点有左右两个子节点，用另一结点代替被删除的结点，有两种方式，用左子树的最大值或右子树的最小值。如要删除上图7号结点，有两种方式，第一种可以用右子树最小值8来代替7；第二种是用左子树最大值6来替换7，再把5补回空缺的位置。

优点：结构上实现了二分查找，提高了查找效率，插入删除操作简单

缺点：由于每次插入都是在叶子结点处插入，如果插入顺序不合适，可能出现链式结构或者非常不平衡，使查找效率降低

4. 二叉平衡树（AVL树）

为了解决二叉查找树的不平衡问题，就有了二叉平衡树，二叉平衡树就是在二叉查找树的基础上，再要求左子树与右子树的高度差最大为1。

插入删除操作：与二叉搜索树一样，但是在插入删除之后，由于还需要保持平衡的性质，所以还需要有一步调整。

调整：不平衡的位置只有四种可能，LL、RR、LR和RL

调整方式有四种：LL旋转、RR旋转、LR旋转和RL旋转

·LL（左左）旋转

如上图的LL不平衡图，LL旋转就是将3号点上移一层，7号点下移一层，此时再检查，6号点不满足二叉树性质，就需要放到6号点的左子树上，调整完成。RR旋转也类似。

·LR（左右）旋转

如上图LR不平衡图，LR旋转就是先

LR旋转要分两步，首先对3、6号点进行RR调整，调整过程和RR旋转一样，再对上面6、7号点进行调整，调整过程和LL旋转一样。