目录

二叉树

为什么需要树这种结构

数组和链式存储都有各自的优缺点,数组查找效率高,增删效率低,链式存储查找效率低,增删效率高。树可以提高数据存储、读取的效率,比如二叉排序树,既可以保证数据的查找速度,也可以保证数据的插入、删除、修改速度。

树的相关术语

https://gitee.com/lienhui68/picStore/raw/master/null/20200627141931.png

  1. 节点
  2. 根节点
  3. 父节点
  4. 子节点
  5. 叶子节点:没有子节点的节点
  6. 节点的权:节点的值
  7. 路径:从root节点找到该节点的路线
  8. 子树
  9. 树的高度:最大层数
  10. 森林:多颗子树构成森林

二叉树概念

  1. 树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树。 https://gitee.com/lienhui68/picStore/raw/master/null/20200627143853.png
  2. 二叉树的子节点分为左节点和右节点
  3. 如果该二叉树的所有叶子节点都在最后一层,并且结点总数= 2^n -1 , n 为层数,则我们称为满二叉树。
  4. 如果一棵具有n个结点的二叉树与满二叉树的前n个结点的结构相同,则称这棵二叉树为完全二叉树。 https://gitee.com/lienhui68/picStore/raw/master/null/20200627145151.png

二叉树的遍历

依据父节点的输出顺序分为前序遍历、中序遍历和后序遍历。

前序

先输出当前节点,再遍历左子树,最后遍历右子树

中序

先遍历左子树,再输出当前节点,最后遍历右子树

后序

先遍历左子树,再遍历右子树,最后输出当前节点

代码实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
package com.eh.ftd.dsa.ds;

/**
 * 二叉树
 *
 * @author David Li
 * @create 2020/06/27 14:27
 */
public class BinaryTree {

    /**
     * 定义节点
     *
     * @param <T>
     */
    static class Node<T> {
        T data;
        Node left;
        Node right;

        public Node(T data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }

    /**
     * 初始化一个二叉树,如图1所示
     *
     * @return
     */
    static Node init() {
        Node<Integer> n1 = new Node(1);
        Node<Integer> n2 = new Node(2);
        Node<Integer> n3 = new Node(3);
        Node<Integer> n4 = new Node(4);
        Node<Integer> n5 = new Node(5);
        Node<Integer> n6 = new Node(6);
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n3.right = n6;
        return n1;
    }

    /**
     * 前序遍历
     *
     * @param node
     */
    static void preOrder(Node node) {
        // 1. 输出当前节点
        System.out.print(node + " ");
        // 2. 如果左节点不为空则遍历左子树
        if (node.left != null) {
            preOrder(node.left);
        }
        // 3. 如果右节点不为空则遍历右子树
        if (node.right != null) {
            preOrder(node.right);
        }
    }

    /**
     * 中序遍历
     *
     * @param node
     */
    static void inOrder(Node node) {
        // 1. 如果左节点不为空则遍历左子树
        if (node.left != null) {
            inOrder(node.left);
        }
        // 2. 输出当前节点
        System.out.print(node + " ");
        // 3. 如果右节点不为空则遍历右子树
        if (node.right != null) {
            inOrder(node.right);
        }
    }

    /**
     * 后序遍历
     *
     * @param node
     */
    static void postOrder(Node node) {
        // 1. 如果左节点不为空则遍历左子树
        if (node.left != null) {
            postOrder(node.left);
        }
        // 2. 如果右节点不为空则遍历右子树
        if (node.right != null) {
            postOrder(node.right);
        }
        // 3. 输出当前节点
        System.out.print(node + " ");
    }

    public static void main(String[] args) {
        inOrder(init());
    }

}