二叉树及其遍历

Posted by RussXia on March 8, 2018

二叉树及其遍历

一、什么是二叉树?

二叉树(英语: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(上面的三种属于深度优先搜索DFS),一般来说,bfs=队列;dfs=栈。所以层序遍历使用的是队列。