8.1.1 简单二叉树

1. 二叉树的概念

* 树有很多中，每个节点只能有两个子节点的称为二叉树
* 节点：二叉树的子节点分为左节点和右节点
* 满二叉树：二叉树的所有叶子节点都在最后一层
* 完全二叉树：符合从上到下，从左到右的顺序结构

2. 定义结构

定义一颗树： 属性只要有个根节点就够了 树作为类独立存在，主要在于树类需要承载对树而不是节点操作的方法，如遍历等

/**
 * 定义节点
 * 注意： 是向下描述关系没有parent
 */
@Data
class Node {
    // 节点的值（权）
    private int value;
    // 左节点
    private Node left;
    // 右节点
    private Node right;
}

/**
 * 定义二叉树
 * 定义一颗树：
 *      属性只要有个根节点就够了
 *      树作为类独立存在，主要在于树类需要承载对树而不是节点操作的方法，如遍历等
 */
@Data
class BinaryTree {
    // 根节点
    private Node root;

    // TODO 前序遍历
    public void preOrder(Node node){}

    // TODO 中序遍历
    public void infixOrder(Node node){}

    // TODO 后序遍历
    public void postOrder(Node node){}
}

3. 二叉树遍历

1. 二叉树遍历有三种方式：

前序、中序、后序 （主要看当前节点输出的顺序）

1. 基于遍历的拓展
   1. 查找指定元素
   2. 删除指定元素

3.1 前序遍历

前序遍历思路 先处理当先节点（输出） 然后处理左子树 最后处理右子树

1. 前序输出方法（定义在Tree类上）

    public void preOrder(Node node) {
   
        // 输出当前节点（父节点）
        System.out.print(node.getValue()+"\t");
        // 递归向左子树遍历
        if(node.getLeft()!=null) {
            preOrder(node.getLeft());
        }
        // 遍历右子树
        if(node.getRight()!=null) {
            preOrder(node.getRight());
        }
    }
   

2. 测试前序输出

   /**
     * 前序遍历测试
     * 树结构
     *           11
     *         /     \
     *       21       31
     *      /  \      / \
     *     14   15   61  71
     *    / \
     *  81   91
     *
     *  输出结果：
     *      11    21    14    81    91    15    31    61    71
     */
    public static void main(String[] args) {
   
        // 1.构造树
   
        // 1.1 创建节点
        Node node_11 = new Node(11, null, null);
        Node node_21 = new Node(21, null, null);
        Node node_31 = new Node(31, null, null);
        Node node_14 = new Node(14, null, null);
        Node node_15 = new Node(15, null, null);
        Node node_61 = new Node(61, null, null);
        Node node_71 = new Node(71, null, null);
        Node node_81 = new Node(81, null, null);
        Node node_91 = new Node(91, null, null);
   
        // 1.2 建立节点关系
        node_11.setLeft(node_21); node_11.setRight(node_31);
        node_21.setLeft(node_14); node_21.setRight(node_15);
        node_31.setLeft(node_61); node_31.setRight(node_71);
        node_14.setLeft(node_81); node_14.setRight(node_91);
   
        // 1.3 创建树
        BinaryTree binaryTree = new BinaryTree(node_11);
   
        // 2. 测试前序遍历,从root节点开始
        binaryTree.preOrder(binaryTree.getRoot());
    }
   

   3.2 中序遍历

   先处理左子树

        然后输出自己
         最后输出右子树
   

3. 中序输出方法（定义在Tree类上）

    public void infixOrder(Node node) {
   
        if(node.getLeft()!=null) {
            infixOrder(node.getLeft());
        }
        System.out.print(node.getValue()+"\t");
        if(node.getRight()!=null) {
            infixOrder(node.getRight());
        }
    }
   

4. 中序遍历测试（定义在Tree上） ```java /**

   • 中序遍历测试
   • 树结构
   • 11
   • / \
   • 21 31
   • / \ / \
   • 14 15 61 71
   • / \
   • 81 91 *
   • 输出结果：
   • 81 14 91 21 15 11 61 31 71 */

public static void main(String[] args) {

    // 1.构造树

    // 1.1 创建节点
    Node node_11 = new Node(11, null, null);
    Node node_21 = new Node(21, null, null);
    Node node_31 = new Node(31, null, null);
    Node node_14 = new Node(14, null, null);
    Node node_15 = new Node(15, null, null);
    Node node_61 = new Node(61, null, null);
    Node node_71 = new Node(71, null, null);
    Node node_81 = new Node(81, null, null);
    Node node_91 = new Node(91, null, null);

    // 1.2 建立节点关系
    node_11.setLeft(node_21); node_11.setRight(node_31);
    node_21.setLeft(node_14); node_21.setRight(node_15);
    node_31.setLeft(node_61); node_31.setRight(node_71);
    node_14.setLeft(node_81); node_14.setRight(node_91);

    // 1.3 创建树
    BinaryTree binaryTree = new BinaryTree(node_11);

    // 2. 测试中序遍历,从root节点开始
    binaryTree.infixOrder(node_11);

}

<a name="qAAH6"></a>
### 3.3 后序遍历

1. 后序输出方法（定义在Tree类上）
```java
public void postOrder(Node node) {

    if(node.getLeft()!=null) {
        postOrder(node.getLeft());
    }
    System.out.print(node.getValue()+"\t");
    if(node.getRight()!=null) {
        postOrder(node.getRight());
    }
}

1. 测试后序输出

    /**
     * 后序遍历测试
     * 树结构
     *           11
     *         /     \
     *       21       31
     *      /  \      / \
     *     14   15   61  71
     *    / \
     *  81   91
     *  输出结果：81    91    14    15    21    61    71    31    11
     *
     */
    public static void main(String[] args) {
   
        // 1.构造树
   
        // 1.1 创建节点
        Node node_11 = new Node(11, null, null);
        Node node_21 = new Node(21, null, null);
        Node node_31 = new Node(31, null, null);
        Node node_14 = new Node(14, null, null);
        Node node_15 = new Node(15, null, null);
        Node node_61 = new Node(61, null, null);
        Node node_71 = new Node(71, null, null);
        Node node_81 = new Node(81, null, null);
        Node node_91 = new Node(91, null, null);
   
        // 1.2 建立节点关系
        node_11.setLeft(node_21); node_11.setRight(node_31);
        node_21.setLeft(node_14); node_21.setRight(node_15);
        node_31.setLeft(node_61); node_31.setRight(node_71);
        node_14.setLeft(node_81); node_14.setRight(node_91);
   
        // 1.3 创建树
        BinaryTree binaryTree = new BinaryTree(node_11);
   
        // 2. 测试后序遍历,从root节点开始
        binaryTree.postOrder(node_11);
    }