二叉树及其遍历
一、什么是二叉树?
二叉树（英语：Binary tree）是每个节点最多只有两个分支(不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”和“右子树”。二叉树的分支具有左右次序，不能颠倒。 (引用自wiki)
一棵深度为k，且有2^(k+1)-1个节点的二叉树，称为满二叉树（Full Binary Tree）。这种树的特点是每一层上的节点数都是最大节点数。 而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree）。 满二叉树是完全二叉树的一个特例
二叉树的基本数据结构
@Data
public class TreeNode {
/**
* 值
*/
private int value;
/**
* 左节点
*/
private TreeNode left;
/**
* 右节点
*/
private TreeNode right;
}
二、二叉树的遍历
遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。
- 前序遍历：根节点->左子树->右子树
- 中序遍历：左子树->根节点->右子树
- 后序遍历：左子树->右子树->根节点
三种遍历顺序对此二叉树的遍历结果:
- 前序遍历:2,7,2,6,5,11,5,9,4
- 中序遍历:2,7,5,6,11,2,5,4,9
- 后序遍历:2,5,11,6,7,4,9,5,2
前序递归遍历:
/**
* 前序遍历
*
* @param treeNode 需要遍历的二叉树
*/
public static void recurseFront(TreeNode treeNode) {
if (treeNode == null)
return;
System.out.print(treeNode.getValue() + "\t");
recurseFront(treeNode.getLeft());
recurseFront(treeNode.getRight());
}
前序非递归遍历:
/**
* 非递归方式前序遍历二叉树
* @param treeNode 需要遍历的二叉树
* @return 遍历出来的list结果集
*/
public static List<Integer> traverseTreeNodeFront(TreeNode treeNode) {
List<Integer> list = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
if(treeNode == null){
return list;
}
//利用压栈出栈前序遍历二叉树
stack.push(treeNode);
while(!stack.empty()){
treeNode = stack.pop();
if (treeNode != null) {
list.add(treeNode.getValue());
//因为栈后进先出(LIFO)，所以先压入右节点，后压入左节点
stack.push(treeNode.getRight());
stack.push(treeNode.getLeft());
}
}
return list;
}
中序递归遍历:
/**
* 中序遍历
*
* @param treeNode 需要遍历的二叉树
*/
public static void recurseMid(TreeNode treeNode) {
if (treeNode == null)
return;
recurseMid(treeNode.getLeft());
System.out.print(treeNode.getValue() + "\t");
recurseMid(treeNode.getRight());
}
后序递归遍历:
/**
* 后序遍历
*
* @param treeNode 需要遍历的二叉树
*/
public static void recurseEnd(TreeNode treeNode) {
if (treeNode == null)
return;
recurseEnd(treeNode.getLeft());
recurseEnd(treeNode.getRight());
System.out.print(treeNode.getValue() + "\t");
}
层序遍历(BFS)
层序遍历即广度度优先搜索BFS(上面的三种属于深度优先搜索DFS),一般来说，bfs＝队列；dfs=栈。所以层序遍历使用的是队列。