Binary Tree - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

入门链接

【计算机二级选择题重点】二叉树的遍历结构

图解

前序遍历 (Pre-order Traversal):首先访问根节点,然后遍历左子树,最后遍历右子树

中序遍历 (In-order Traversal):首先遍历左子树,然后访问根节点,最后遍历右子树

后序遍历 (Post-order Traversal):首先遍历左子树,然后遍历右子树,最后访问根节点

层次遍历

详解

深入学习二叉树(一) 二叉树基础 二叉树的详解与实现 树的层次遍历 Binary Tree 二叉树 二叉树的前序遍历、中序遍历和后序遍历之间还原二叉树 二叉树前驱节点与后继节点

时间复杂度

先序遍历 中序遍历 后序遍历 层次遍历 height
时间复杂度 O(n) O(n) O(n) O(n) O(h)

若树严重左偏或右偏,h会变成n

标准写法

步骤1: 定义Node的接口,即Node应该有的功能

public interface Node<T> {

    // 获取左结点
    Node<T> getLeft();

    // 设置左结点
    void setLeft(Node<T> node);

    // 获取右结点
    Node<T> getRight();

    // 设置右结点
    void setRight(Node<T> node);

    // 获取值
    T getData();

    // 设置值
    void setData(T data);

    // 判断是否为叶子结点
    boolean isLeaf();
}

步骤2: 定义Binary Tree的结点Node

public class BinaryNode<T> implements Node<T> {

    // 左子结点
    private BinaryNode<T> left;

    // 右子结点
    private BinaryNode<T> right;

    // 值
    private T data;

    // 初始化一个结点,包括值和它的左右子结点
    public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    // 初始化一个没有左右子结点的结点
    public BinaryNode(T data) {
        this(data, null, null);
    }

    // 获取左结点
    @Override
    public BinaryNode<T> getLeft() {
        return left;
    }

    @Override
    public void setLeft(Node<T> node) {
        this.left = (BinaryNode<T>) node;
    }

    // 获取右结点
    @Override
    public BinaryNode<T> getRight() {
        return right;
    }

    @Override
    public void setRight(Node<T> node) {
        this.right = (BinaryNode<T>) node;
    }

    // 获取值
    @Override
    public T getData() {
        return data;
    }

    @Override
    public void setData(T data) {
        this.data = data;
    }

    // 判断是否为叶子结点
    @Override
    public boolean isLeaf() {
        return this.left == null && this.right == null;
    }
}

步骤3: 定义Tree的接口,即Tree应该有的功能

public interface Tree<T> {

    // 判空
    boolean isEmpty();

    // 二叉树的结点个数
    int size();

    // 返回二叉树的高度或者深度,即结点的最大层次
    int height();

    // 先序遍历
    String preOrder();

    // 中序遍历
    String inOrder();

    // 后序遍历
    String postOrder();

    // 层次遍历
    String levelOrder();

    // 插入值
    void insert(T data);

    // 删除值
    void remove(T data);

    // 是否包含某个值
    boolean contains(T data);

    // 查找最大值
    T findMin();

    // 查找最小值
    T findMax();

    // 根据值找到结点
    BinaryNode<T> findNode(T data);

    // 查找后继结点 -- 右子树最小值结点
    BinaryNode<T> findSuccessor(BinaryNode<T> note);

    // 查找前驱结点 -- 左子树最大值结点
    BinaryNode<T> findPredecessor(BinaryNode<T> note);

    // 清空
    void clear();

    // 打印树结构图
    void print();
}

步骤4: 定义Binary Tree的结点Node

public class BinaryNode<T> {

    // 左子结点
    public BinaryNode<T> left;

    // 右子结点
    public BinaryNode<T> right;

    public T data;

    // 定义一个结点,包括值和它的左右子结点
    public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    // 定义一个没有左右子结点的结点
    public BinaryNode(T data) {
        this(data, null, null);
    }

    /**
     * 判断是否为叶子结点
     * @return
     */
    public boolean isLeaf() {
        return this.left == null && this.right == null;
    }
}

先序和中序遍历,中序和后序遍历,可以唯一确定一棵二叉树(无重复元素)

要点

  • 具有n个节点的完全二叉树的深度为log2(n) + 1
  • 已知先序和中序,后序和中序遍历序列之后,可以唯一确定一棵二叉树(无重复元素)。但是,只知道先序和后序遍历序列,是无法知道哪个结点是左子树还算右子树