二叉树

二叉树是树的一种，每个结点最多可具有两个子树，即结点的度最大为2。

二叉树的遍历

区分到底是前序、中序还是后序其实很简单，主要是相对于当前节点来说的。

• 前序遍历：当前节点先访问
• 中序遍历：当前节点中间访问
• 后序遍历：当前节点后访问

以下图为例：

前序遍历

先访问根节点，然后访问左节点，最后访问右节点。
【root】->【A】->【C】 ->【G】 ->【D】->【B】 ->【E】->【F】

中序遍历

先访问左节点，然后访问根节点，最后访问右节点。
【G】->【C】->【A】 ->【D】 ->【root】->【E】 ->【B】->【F】

后序遍历

先访问左节点，然后访问右节点，最后访问根节点。
【G】->【C】->【D】 ->【A】 ->【E】->【F】 ->【B】->【root】

代码实现

创建节点类

• 存数据的变量 - data（这里为了方便，数据类型用String）
• 指向左节点索引变量（指针）- left
• 指向右节点索引变量（指针）- right

/** * 节点数据结构 */
class TreeNode {
    public String data;
    public TreeNode left = null;
    public TreeNode right = null;
    public TreeNode(String data, TreeNode left, TreeNode right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
    public TreeNode(String data) {
        this.data = data;
    }
    public TreeNode() {}
}

创建二叉树类，并实现三种遍历方式

• 需要一个根节点 - root

/** * 二叉树 */
class BinaryTree {

    // 二叉树的根节点
    public TreeNode root;

    /** * 前序遍历 */
    public void preOrder(TreeNode node) {
        // 只有当前节点不为null 才向下递归遍历 否则在调用node.left或者node.right时就会报空指针异常
        if (node != null) {
            // 1、输出当前节点
            System.out.print(node.data+" ");
            //2、递归向左子树前序遍历
            preOrder(node.left);
            //3、递归向右子树前序遍历
            preOrder(node.right);
        }
    }

    /** * 中序遍历 */
    public void midOrder(TreeNode node) {
        if (node != null) {
            //1、递归向左子树中序遍历
            midOrder(node.left);
            // 2、输出当前节点
            System.out.print(node.data+" ");
            //3、递归向右子树中序遍历
            midOrder(node.right);
        }
    }
    /** * 后序遍历 */
    public void postOrder(TreeNode node) {
        if (node != null) {
            //1、递归向左子树后序遍历
            postOrder(node.left);
            //2、递归向右子树后序遍历
            postOrder(node.right);
            // 3、输出当前节点
            System.out.print(node.data+" ");
        }
    }
}

主方法类测试

public class BinaryTreeDemo {
    public static void main(String[] args) {
        // 先创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        // 为binaryTree创建一个根节点
        TreeNode root = new TreeNode("root");
        binaryTree.root = root;
        // 创建其他节点
        TreeNode nodeA = new TreeNode("A");
        TreeNode nodeB = new TreeNode("B");
        TreeNode nodeC = new TreeNode("C");
        TreeNode nodeD = new TreeNode("D");
        TreeNode nodeE = new TreeNode("E");
        TreeNode nodeF = new TreeNode("F");
        TreeNode nodeG = new TreeNode("G");
        // 手动调整节点的指向关系
        root.left = nodeA; root.right = nodeB;
        nodeA.left = nodeC; nodeA.right = nodeD; nodeB.left = nodeE; nodeB.right = nodeF;
        nodeC.left = nodeG;

        // 前序遍历
        System.out.println("前序遍历:");
        binaryTree.preOrder(binaryTree.root);

        // 中序遍历
        System.out.println();
        System.out.println("中序遍历:");
        binaryTree.midOrder(binaryTree.root);

        // 后序遍历
        System.out.println();
        System.out.println("后序遍历:");
        binaryTree.postOrder(binaryTree.root);

    }
}

输出结果