前言

这里说的树不是日常生活中所见的木本植物，而是一种非线性数据结构，把它叫做“树”是因为它看起来像一棵颠倒的树，也就是说它是根朝上，而叶朝下的。

在生活中，有很多逻辑关系并不是简单的线性关系，在实际场景中，常常存在着一对多、多对多的情况。例如，企业的上下级关系、家谱族谱图（Family tree），字典的目录，计算机文件目录......

树的基础知识

树(tree)，是包含 n(n ≥ 1)个节点，(n-1) 条边的有限集（注意：当 n=0 时，树是空树）。在任意一个非空树中，它具有以下的特点：

1. 有且仅有一个特定的点称为根节点；
2. 当 n ＞ 1 时，除根结点之外，的其余数据元素被分为 m(m ≥ 0)个互不相交的有限集，其中每一个集合本身也是一棵树，被称作原树的子树(subtree)。
   如果要把一个节点和边的集合定义为树，那么从根节点到其他任意一个节点都必须 有且只有一条 路径。

树的常用术语

1. 根节点（root）：最顶层的节点，或者说，没有父节点的节点；
2. 父节点（parent）：若一个节点含有子节点，则这个节点称为其子节点的父节点；
3. 子节点（child）：一个节点含有的子树的根节点称为该节点的子节点；
4. 兄弟节点（sibling）：具有相同父节点的节点互称为兄弟节点；
5. 叶节点（leaf）：度为 0 的节点，或者说，没有子节点的点；
6. 节点的度：一个节点含有的子树的个数称为该节点的度；
7. 节点的层次：从根节点开始定义起，根节点为第 1 层，它的子节点为第 2 层，以此类推；
8. 树的度：一棵树中，最大的结点的度称为树的度；
9. 树的高度或深度：树的最大层次数；
   ......

树的种类

• 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
• 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；

• 二叉树：每个节点最多含有两个子树的树称为二叉树；

  • 完全二叉树：对于一颗二叉树，假设其深度为d（d > 1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；

    • 满二叉树：所有叶节点都在最底层的完全二叉树；
  • 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
  • 排序二叉树（Binary Search Tree）：也称二叉搜索树、二叉查找树、有序二叉树；
  • 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
  • B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树。

二叉树

1. 二叉树（Binary Tree）：是每个节点 最多只有两个 分支（可能只有一个，或者没有）的有序树。它的两个分支，被称作“左子树（left child）”，“右子树（right child）”，左子树和右子树又同样都是二叉树。二叉树的分支具有左右次序，不能随意颠倒。
2. 满二叉树（Full Binary Tree）：一棵深度为 k，且有 (2 k − 1) 个节点的二叉树。
3. 完全二叉树（Complete Binary Tree）：在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点，则此二叉树为完全二叉树。

满二叉树要求所有分支都是满的，而完全二叉树只需要保证最后一个节点之前的节点都齐全即可。
二叉树作为典型的有序树，许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

二叉树的实现

二叉树的每一个节点都包含三个成员变量：存储数据的变量 val、左子节点 left、右子节点 right。

class TreeNode {
    // 节点值
    int val;
    // 左子节点
    TreeNode left;
    // 右子节点
    TreeNode right;
    TreeNode(int x) { val = x; }
}

二叉树属于逻辑结构，也可以使用数组和链表实现。

当使用数组实现时，按照层级顺序把二叉树的节点放进数组中对应的位置上，如果某一个节点没有左子节点或右子节点，那么数组对应的位置也会空缺，所以对于一个稀疏的二叉树来说，用数组实现是非常浪费空间的；满二叉树紧凑排列才能不浪费空间。\r\n假设某节点的索引值为 i，那么它左子节点的索引是 (2 i + 1)，它右子节点的索引是 (2 i + 2)，而它的父节点（如果有）索引则为 (i - 1)/2 。

当使用链表实现时，需要指向子节点的指针，所以实例化每个节点后，需要构建各节点的引用指向。使用链表能避免数组存储浪费空间的问题，算法和结构相对简单，但使用二叉链表，由于缺乏父链的指引，在找回父节点时需要重新扫描树得知父节点的节点地址。

// 实例化节点，n1为根节点
TreeNode n1 = new TreeNode(9);
TreeNode n2 = new TreeNode(6);
TreeNode n3 = new TreeNode(8);
TreeNode n4 = new TreeNode(3);
TreeNode n5 = new TreeNode(4);
// 构建引用指向
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

二叉搜索树

在树中查找数据项的速度和在有序数组中查找一样快，并且插入、删除数据项的速度和链表的一样快。基于这个特点，二叉树最主要的应用在于查找操作和维持相对顺序这两个方面。
在查找操作方面，二叉搜索树更合适。它具有以下性质：

1. 若任意节点的左子树不空，则左子树上所有节点的值均 ＜ 它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均 ≥ 它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；
   
   对于一个节点分布相对均衡的二叉搜索树来说，如果节点总数为 N，那么搜索节点的时间复杂度是 O(log N)，更准确来说，是 O(log2 N)，最坏情况下为 O(N)（数列有序时，树退化成线性表），但也有在二叉搜索树基础上改良的平衡树，如 AVL 树，红黑树，可以使树的高度总是得到平衡，时间复杂度在最坏情况下也能达到 O(log N)。
   

基本操作

// 节点类
class Node{
    public int iData;
    public Node leftChild;
    public Node rightChild;

    public void display(){
        System.out.print('【');
        System.out.print(iData);
        System.out.print(',');
        System.out.print('】');
    }
}

// 树类
class Tree{
    // 根节点
    private Node root;
    public Tree(){ root = null; }

    // 搜索节点
    public Node find(int key){
        Node current = root;
        while(current.iData != key){
            if (key < current.iData){
                current = current.leftChild;
            }else {
                current = current.rightChild;
            }
            if (current == null){
                return null;
            }
        }
        return current;
    }
    // 插入节点：必须确定新节点的插入位置
    public void insert(int key){
        Node newNode = new Node();
        newNode.iData = key;
        if (root == null){
            root = newNode;
        }else{
            Node current = root;
            Node parent;
            while(true){
                parent = current;
                if (key < current.iData){
                    current = current.leftChild;
                    if (current == null){
                        parent.leftChild = newNode;
                        return ;
                    }
                }else {
                    current = current.rightChild;
                    if (current == null){
                        parent.rightChild = newNode;
                        return ;
                    }
                }
            }
        }
    }
    // 删除节点
    public boolean delete(int key){
        Node current = root;
        Node parent = root;
        boolean isLeftChild = true;

        while(current.iData != key){
            parent = current;
            if (key < current.iData){
                isLeftChild = true;
                current = current.leftChild;
            }else {
                isLeftChild = false;
                current = current.rightChild;
            }
            if (current == null){
                return false;
            }
            // 删除没有子节点的节点
            if (current.leftChild == null && current.rightChild == null){
                // 清空根节点
                if (current == root){
                    root = null;
                }
                // 清空父节点的左叶节点
                else if (isLeftChild){
                    parent.leftChild = null;
                }
                // 清空父节点的右叶节点
                else{
                    parent.rightChild = null;
                }
            }
            // 删除只有一个子节点的节点
            else if (current.rightChild == null){
                // 取代根节点
                if (current == root){
                    root = current.leftChild;
                }
                //
                else if (isLeftChild){
                    parent.leftChild = current.leftChild;
                }
                //
                else{
                    parent.rightChild = current.leftChild;
                }
            }
            // 删除有两个子节点的节点：后续节点接上
            else{
                Node successor = getSuccessor(current);
                if (current == root){
                    root = successor;
                }else if (isLeftChild){
                    parent.leftChild = successor;
                }else {
                    parent.rightChild = successor;
                }
                successor.leftChild = current.leftChild;
            }
        }
        return true;
    }
    // 找删除节点delNode的后续节点
    private Node getSuccessor(Node delNode){
        Node successorParent = delNode;
        Node successor = delNode;
        // delNode的右子节点
        Node current = delNode.rightChild;
        while(current != null){
            successorParent = successor;
            successor = current;
            current = current.leftChild;
        }
        if (successor != delNode.rightChild){
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = delNode.rightChild;
        }
        return successor;
    }

遍历二叉树

遍历意味着按照某种特定顺序访问树中所有的节点，但是遍历本身是一种线性操作，而二叉树是非线性数据结构，如何将非线性关联的节点转化为线性的序列输出呢？

从宏观的角度来看，二叉树的遍历分为：

1. 深度优先遍历

   • 前序遍历
   • 中序遍历
   • 后序遍历

2. 广度优先遍历

   • 层序遍历

public static void preOrder(Node t) {
    if (t == null) {
        return;
    }
    System.out.print(t.iData + " ");
    preOrder(t.leftChild);
    preOrder(t.rightChild);
}

public static void inOrder(Node t) {
    if (t == null) {
        return;
    }
    inOrder(t.leftChild);
    System.out.print(t.iData + " ");
    inOrder(t.rightChild);
}

public static void postOrder(Node t) {
    if (t == null) {
        return;
    }
    postOrder(t.leftChild);
    postOrder(t.rightChild);
    System.out.print(t.iData + " ");
}

如果要使用非递归的方式实现深度优先遍历，那么需要使用数据结构 栈 实现，以前序为例：

public static void preOrder2(Node t){
    Stack<Node> stack = new Stack<>();
    Node n = t;
    while (n != null || !stack.isEmpty()){
        // 迭代访问节点t的左子节点，入栈
        while (n != null){
            System.out.print(n.iData);
            stack.push(n);
            n = n.leftChild;
        }
        // 如果没有左子节点，就弹出，访问右子节点
        if (!stack.isEmpty()){
            n = stack.pop();
            n = n.rightChild;
        }
    }
}

层序遍历：使用数据结构 队列 实现：

public static void levelOrder(Node root) {
    Queue<Node> q1 = new ArrayDeque<>();
    if (root == null) {
        return;
    }
    if (root != null) {
        q1.add(root);
    }
    while (!q1.isEmpty()) {
        Node n1 = q1.poll();
        if (n1.leftChild != null) {
            q1.add(n1.leftChild);
        }
        if (n1.rightChild != null) {
            q1.add(n1.rightChild);
        }
        System.out.print(n1.iData + " ");
    }
    System.out.println();
}

public static void levelOrder2(Node root) {
    Queue<Node> q2 = new LinkedList<>();
    if (root == null) {
        return;
    }
    if (root != null) {
        q2.offer(root);
    }
    while (!q2.isEmpty()){
        Node n2 = q2.poll();
        System.out.print(n2.iData + " ");
        if (n2.leftChild != null){
            q2.offer(n2.leftChild);
        }
        if (n2.rightChild != null){
            q2.offer(n2.rightChild);
        }
    }
    System.out.println();
}

参考

博客园
码农有道
LeetCode:91