Java 二叉树基础概念、遍历与基本操作

孩子双亲表示法后序在平衡树位置介绍，本文采用孩子表示法来构建二叉树。

1.5 二叉树的基本操作

1.5.1 二叉树的简单创建

在学习二叉树的基本操作前，需先创建一棵二叉树，然后才能学习其相关的基本操作。为了简单些，此处手动创建一颗简单的二叉树。先学习二叉树的操作，后续再研究二叉树真正的创建方式。

public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }

    public void createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B; A.right = C;
        B.left = D; B.right = E;
        C.left = F; C.right = G;
        E.right = H;
    }
}

再看二叉树基本操作前，回顾下二叉树的概念：

1. 空树
2. 非空：根节点，根节点的左子树、根节点的右子树组成的。

1.5.2 二叉树的遍历

1. 前中后序遍历

• NLR（前序遍历 Preorder Traversal）：访问根结点 --> 根的左子树 --> 根的右树。
• LNR（中序遍历 Inorder Traversal）：根的左子树 --> 根节点 --> 根的右子树。
• LRN（后序遍历 Postorder Traversal）：根的左子树 --> 根的右子树 --> 根节点。

下图是前序遍历的递归过程，中序遍历和后序遍历类似。

前序遍历结果：A B D E H C F G 中序遍历结果：D B H E A F C G 后序遍历结果：D H E B F G C A

以上图二叉树为例，代码实现前中后序递归遍历。

注意: 根的左子树，不只是根的左节点，而是根左边的整颗子树。右子树同理。如上右图。

代码实现前分析 (以前序遍历为例): 前序遍历的顺序为 根 左子树 右子树，凡是递归必有一终止条件，以上右图为例，从根节点往左递到 H，H 的左子树为 null，则返回。所以终止条件为 root 等于 null 则返回。按照顺序：先打印根节点，再递归左子树，后递归右子树。

// 前序遍历：根 左 右
public void preOrder(TreeNode root) {
    if(root == null) return; // 终止条件
    System.out.print(root.val + " "); // 先打印根
    preOrder(root.left); // 再处理左子树
    preOrder(root.right); // 最后处理右子树
}

// 中序遍历：左 根 右
public void inOrder(TreeNode root) {
    if (root == null) return;
    inOrder(root.left);
    System.out.print(root.val + " ");
    inOrder(root.right);
}

// 后序遍历：左 右 根
public void postOrder(TreeNode root) {
    if(root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.val + " ");
}

画图理解前序遍历的递归过程。

A 的右子树递归过程与上图类似。

2. 层序遍历

层序遍历：除了前序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为 1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第 2 层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历，如下图所示，层序遍历的结果：A B C D E F G H

代码实现非递归层序遍历：非递归层序遍历，我们可以借助队列，利用队列'先进先出'的特点，实现层序遍历思路：二叉树以根节点、左节点、右节点的顺序入队，出队顺序即为层序遍历，如下图：

具体步骤：先将根节点入队，进入循环 while(!queue.isEmpty())，弹出栈顶元素赋给 cur。打印根节点，将 cur 的左右节点入队。

import java.util.LinkedList;
import java.util.Queue;

// 二叉树的层序遍历
public void levelOrder1(TreeNode root) {
    if(root == null) { return; }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()) {
        TreeNode cur = queue.poll();
        System.out.print(cur.val + " ");
        if(cur.left != null) { queue.offer(cur.left); }
        if(cur.right != null) { queue.offer(cur.right); }
    }
}

1.5.3 二叉树的基本操作

1. 获取树中节点的个数 int size(Node root)

第一种方法：通过二叉树的遍历求，每递归遍历一次，size++。

public int nodeSize(TreeNode root) {
    if(root == null) return 0;
    return 1 + nodeSize(root.left) + nodeSize(root.right);
}

第二种方法：通过子问题解决：总节点数 = 左子树 + 右子树 + 1。

public int nodeSize2(TreeNode root) {
    if(root == null) return 0;
    return nodeSize2(root.left) + nodeSize2(root.right) + 1;
}

2. 获取叶子节点的个数 int getLeafNodeCount(Node root)

第一种思路：定义 leafSize 存储叶子节点的个数，在前序遍历中，当某个节点的左右节点都为 null 时，则 leafSize++。

public int gerLeafSize(TreeNode root) {
    if(root == null) return 0;
    if(root.left == null && root.right == null) { return 1; }
    return gerLeafSize(root.left) + gerLeafSize(root.right);
}

第二种思路：求二叉树叶子节点的个数 = 左子树叶子节点的个数 + 右子树叶子节点的个数。

public int getLeafSize2(TreeNode root) {
    if(root == null) return 0;
    if(root.left == null && root.right == null) { return 1; }
    return getLeafSize2(root.left) + getLeafSize2(root.right);
}

3. 获取第 K 层节点的个数 int getKLevelNodeCount(Node root, int k)

public int getKLeveNodeCount(TreeNode root, int k) {
    if(root == null) return 0;
    if(k == 1) { return 1; }
    return getKLeveNodeCount(root.left, k-1) + getKLeveNodeCount(root.right, k-1);
}

4. 获取二叉树的高度 int getHeight(Node root)

思路：二叉树的高度 = 左子树与右子树之中最大高度 + 1。

public int getHeight(TreeNode root) {
    if(root == null) return 0;
    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);
    return Math.max(leftHeight, rightHeight) + 1;
}

5. 检测值为 value 的元素是否存在 boolean find(Node root, char key)

还是一样的，通过遍历来确定二叉树是否存在值为 value 的节点，以前序遍历为例，判断根节点，递归左子树，再判断左子树，递归右子树，再判断右子树。如果全都没找到则 return false。

public boolean find(TreeNode root, char key) {
    if(root == null) return false;
    if(root.val == key) { return true; }
    boolean leftVal = find(root.left, key);
    if(leftVal == true) { return true; }
    boolean rightVal = find(root.right, key);
    if(rightVal == true) { return true; }
    return false;
}

6. 判断一棵树是不是完全二叉树 boolean isCompleteTree(Node root)

思路：利用层序遍历，将节点入队，当 cur 遇到 null 之后，如果后面还有不为空的节点就说明该二叉树不是完全二叉树，否则是。

public boolean isCompleteTree(TreeNode root) {
    if(root == null) { return true; }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()) {
        TreeNode cur = queue.poll();
        if(cur != null) {
            queue.offer(cur.left);
            queue.offer(cur.right);
        } else {
            break;
        }
    }
    while(!queue.isEmpty()) {
        TreeNode cur = queue.poll();
        if(cur != null) {
            return false;
        }
    }
    return true;
}
}