vlambda博客
学习文章列表

一、什么是二叉树

二叉树顾名思义，即每个节点最多有两个子树的树形数据结构。如下图的二叉树中，3 为二叉树的根节点，9 为元素 3 的左节点，20 为元素 3 的右节点。由其形态的特点还可以细分为满二叉树、平衡二叉树等等等等，这里不做过多描述。

二、二叉树的遍历

大体分为广度优先遍历和深度优先遍历。深度优先又分为前、中、后序遍历。

三、遍历方式算法

• 二叉树数据结构

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

1、前序遍历

• 递归算法
  先输出节点的值，再改变节点的值为左右子树。

public static void preorderTraversal(TreeNode root) {
    if (null != root) {
      System.out.println(root.val);
      preorderTraversal(root.left);
      preorderTraversal(root.right);
    }
  }

• 非递归算法
  同样先输出节点的值，然后遍历其左子树，但是这个过程中为了回溯到各节点遍历其右子树，考虑用栈做存储。

public static void preorderTraversal(TreeNode root) {
    // 存放当前节点
    TreeNode node = root;
    // 顺序存放二叉树的每个节点
    Stack<TreeNode> stack = new Stack<>();
    // 什么时候结束循环？
    // 到了最后一个节点时结束，即节点的左右子树都为空并且栈中也没有其他节点了
    while (null != node || !stack.isEmpty()) {
      // 若左子节点为空，则结束本次遍历
      while (null != node) {
        // 首先输出节点的值
        System.out.println(node.val);
        // 顺序入栈
        stack.push(node);
        // 遍历左子节点
        node = node.left;
      }
      if (!stack.isEmpty()) {
        // 顺序出栈
        node = stack.pop();
        // 指向右子节点
        node = node.right;
      }
    }
  }

2、中序遍历

类比前序遍历很容易可以得到中序遍历的算法。

• 递归算法

public static void recursionMiddleorderTraversal(TreeNode root) {
    if (null != root) {
        recursionMiddleorderTraversal(root.left);
        System.out.print(root.val);
        recursionMiddleorderTraversal(root.right);
    }
}

• 非递归算法

public static void middleorderTraversal(TreeNode root) {
    Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
    TreeNode node = root;
    while (null != node || !treeNodeStack.isEmpty()) {
      while (null != node) {
        treeNodeStack.push(node);
        node = node.left;
      }
      if (!treeNodeStack.isEmpty()) {
        node = treeNodeStack.pop();
        // 本轮循环中因为栈存的是左子树，所以先输出左子树
        System.out.print(node.val + " ");
        node = node.right;
      }
    }
  }

3、后序遍历

• 递归算法

public static void recursionPostorderTraversal(TreeNode root) {
    if (null != root) {
        recursionPostorderTraversal(root.left);
        recursionPostorderTraversal(root.right);
        System.out.print(root.val);
    }
}

• 非递归算法

public static void postorderTraversal(TreeNode root) {
    Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
    TreeNode node = root;
    TreeNode lastVisit = root;
    while (node != null || !treeNodeStack.isEmpty()) {
        while (node != null) {
            treeNodeStack.push(node);
            node = node.left;
        }
        //查看当前栈顶元素
        node = treeNodeStack.peek();
        //如果其右子树也为空，或者右子树已经访问
        //则可以直接输出当前节点的值
        if (node.right == null || node.right == lastVisit) {
            System.out.print(node.val + " ");
            treeNodeStack.pop();
            lastVisit = node;
            node = null;
        } else {
            //否则，继续遍历右子树
            node = node.right;
        }
    }
}

4、广度优先遍历

• 
  

1. 定义节点 TreeNode lastNode指向当前行最右节点，TreeNode nlastNode指向下一行最右节点。

• 
  

2. 利用队列，首先将根节点入队,再循环里出队,并将其子节点入队,定义TreeNode tmpNode节点指向当前出队列的节点，当tmpNode==lastNode时，代表当前行遍历结束，输出换行，再令lastNode=nlastNode，nlastNode在子节点入队列时指向下一行最右节点。循环直到对列为空就行。

public static int[][] breadthFirstSearch(TreeNode root) {
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    list.add(new ArrayList<Integer>());
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    // 当前行最右节点
    TreeNode lastNode = root;
    // 下一行最右节点
    TreeNode nLastNode = root;
    TreeNode tmpNode = null;
    // 树的高度
    int height = 0;
    while (!queue.isEmpty()) {
      tmpNode = queue.poll();
      if (null != tmpNode) {
        list.get(height).add(tmpNode.val);
      }
      if (null != tmpNode.left) {
        queue.add(tmpNode.left);
        nLastNode = tmpNode.left;
      }
      if (null != tmpNode.right) {
        queue.add(tmpNode.right);
        nLastNode = tmpNode.right;
      }
      if (tmpNode == lastNode) {
        lastNode = nLastNode;
        height++;
        list.add(new ArrayList<Integer>());
      }
    }
    int[][] data = new int[list.size()][];
    for (int i = 0; i < list.size(); i++) {
      for (int j = 0; j < list.get(i).size(); j++) {
        data[i][j] = list.get(i).get(j);
      }
    }

    return data;
  }