非线性数据结构（树结构）Java版

1.树

举例：文件夹、公司组织架构、家谱等

优点：数据存储后出奇高效

二分搜索树（Binary search Tree）、

平衡二叉树：AVL；红黑树

堆：并查集

线段树

字典树；前缀树

2.二分搜索树的遍历

（1）层序遍历

遍历过程：根节点28---------中层16----------底层13-----------底层22-------------中层30--------------底层29---------底层42

//二分搜索树的层序遍历 public void levelOrder(){ Queue<Node> q = new LinkedList<>(); q.add(root); while(!q.isEmpty()){ Node cur = q.remove(); System.out.println(cur.e); if(cur.left != null) q.add(cur.left); if(cur.right != null) q.add(cur.right); } }

深度优先遍历的意义：有全图遍历

广度优先遍历的意义：无全图遍历

3.二分搜索树的删除（最大最小值）