Java集合分析5

树

树

树的基本概念

节点, 根, 兄弟节点,父子节点, 深度, 路径, 高度 ,边

二叉树

二叉树的概念

表达式树 (使用栈构造表达式树)

二叉查找树

对于树中的每一个节点X, 它的左子树中所有项的值小于X中的项, 右子树中的所有值大于X中的项目; 这意味着这种树可以用某一种方式排序

平衡二叉查找树

对于树中的每一个节点, 左子树和右子树的高度差小于等于1.

伸展树

不记录高度, 每次查找一个元素的时候, 都将这个元素通过一系列的旋转操作移动到根部(如果一个元素被访问了, 那么下次被访问的可能性会变大)

摊还时间复杂度O(M*LgN) M此操作的时间复杂度.

再谈树的遍历

  1. 前序. 中序. 后续遍历
  2. 层序遍历
//使用队列(或者表)装载每层的元素, 每次出队一个元素,把该元素的下一层子节点全部入队(每层全部出队后, 下一层的子节点也已经入队了.)
public void printTreeWithLevel(TreeNode root) {
  List list = new LinkedList();
  TreeNode curNode = null;
  list.add(root);
  while(!list.isEmpty) {
        curNode = list.remove();
    System.out.println("data = " + curNode.data);
    if(curNode.left != null) {
      list.add(curNode.left);
    }
    if(curNode.right != null) {
      list.add(curNode.right);
    }
  }
}

B树

TreeSet和TreeMap类的实现, 将在12章红黑树中

Comments

⬆︎TOP