树形结构

我们之前研究的基本都是一对一的问题，而树是一种非线性数据结构，它是由n(n≥0)个结点组成的具有有层次关系的有限集
特点：
当 n=0 时，称为空树，在任何一个非空树中：

• 有且只有一个根结点

• 当 n>1 时，其余结点可分为 m(m>0) 个互不相交的有限集T1，T2，…Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)，每棵子树的根节点有且只有一个前驱，可以有0个或多个后继
  如图所示：
  .
  

• 树是递归定义的

概念

树和非树(图)的区别

• 子树是不相交的
• 除了根节点外，每个节点有且仅有一个父节点
• 一颗 n 个节点的树，有 n-1 条边

树的表示形式

最常用的方法—孩子兄弟表示法：

class Node{
    int value;  //树中存储的数据
    Node firstChild;  //树中第一个孩子引用
    Node nextBrother; //下一个兄弟引用
}

画图表示：

二叉树

概念和特点

概念：

对于在某个阶段都是两种结果的情形，比如：0和1、真和假、上和下、对与错、正和反等，都适合用树状结构来建模，而这种树是很特殊的树状结构，叫做二叉树

二叉树(Binary Tree)是 n(n≥0) 个节点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成

特点：

• 每个节点最多有两棵子树，二叉树的度大能超过 2
  注意不是只有两棵子树，而是最多有，没有子树或者有一棵子树也是可以的

• 二叉树的子树有左右之分，其子树的次序不能任意颠倒，因此二叉树是有序树

• 即使树中某节点只有一棵子树，也要区分它是左子树还是右子树
  二叉树的基本形态：

• 空二叉树

• 只有一个根节点

• 根节点只有左子树

• 根节点只有右子树

• 根结点既有左子树又有右子树

特殊的二叉树：

满二叉树：

一个二叉树，若每一个层的节点数都达到最大值(即：2)，则就为满二叉树
一个二叉树的层数为 n，且节点总数是 2n-1

满二叉树的特点：

• 叶子只出现在最下一层，出现在其他层就不可能达到平衡
• 非叶子节点的度一定是2
• 在同样深度的二叉树中，满二叉树的节点个数最大，叶子个数也最多

完全二叉树：

直观来说：相比于满二叉树来说，完全二叉树右小角缺了一块

完全二叉树是效率很高的数据结构，对于深度为K的，有n个节点的二叉树，当且仅当其每一个节点都与深度为K的满二叉树中编号从1至n的节点一一对应时称之为完全二叉树，满二叉树是一种特殊的完全二叉树

完全二叉树的特点：

• 叶子节点只能出现在最下两层
• 最下层的叶子一定集中在左边连续位置
• 倒数第二层，如果有叶子节点，一定出现在右边连续位置
• 若节点度为1，则该节点只有左子树
• 同样节点数的二叉树，完全二叉树的深度最小

二叉树的相关操作

二叉树的表示

可通过左右孩子来表示

class Node{
    int val;      //存储的数据
    Node left;    //左子树根节点的引用
    Node right;   //右子树根节点的引用
    Node parent;  //双亲的引用(可选)
}

二叉树的遍历🔺

遍历： 遍历按照一定的顺序访问到集合中的每个元素，不重复不遗漏
由于二叉树不是线性结构，故遍历起来相对复杂

手动构造一棵树：

class Node{
    char val;      //存储的数据
    Node left;    //左子树根节点的引用
    Node right;   //右子树根节点的引用
    Node parent;  //双亲的引用(可选)

    //提供构造方法
    public Node(char val) {
        this.val = val;
    }
}

//构建一棵树
public static Node buildTree(){
    Node a = new Node('A');
    Node b = new Node('B');
    Node c = new Node('C');
    Node d = new Node('D');
    Node e = new Node('E');
    
    a.left = b;
    a.right = c;
    b.left = d;
    b.right = e;

    return a;
}

1.先序遍历

先访问根节点，递归遍历左子树，递归遍历右子树 (根左右)

例图：

代码实现：

public static void preOrder(Node root){
    //若为空树，直接返回
    if(root == null){
        return;
    }
    //先访问根节点
    System.out.print(root.val+" ");
    
    //递归访问左子树
    preOrder(root.left);
    //递归访问右子树
    preOrder(root.right);
}

2.中序遍历

先递归遍历左子树，访问根节点，再递归遍历右子树 (左根右)

例图：

public static void inOrder(Node root){
    //若为空树，直接返回
    if(root == null){
        return;
    }
    //递归访问左子树
    inOrder(root.left);
    //访问根节点
    System.out.print(root.val+" ");
    //递归访问右子树
    inOrder(root.right);
}

3.后序遍历

先递归遍历左子树，再递归遍历右子树，最后访问根节点 (左右根)

例图：

public static void postOrder(Node root){
    //若为空树，直接返回
    if(root == null){
        return;
    }
    //递归访问左子树
    postOrder(root.left);
    //递归访问右子树
    postOrder(root.right);

    //访问根节点
    System.out.print(root.val+" ");
}

4.层序遍历

一层一层往下遍历，每层从左向右访问，为非递归操作

public static void levelOrder(Node root){
    //创建一个空队列并把根节点加入队列中
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while( !queue.isEmpty()){
        //队列非空，取出队首元素
        Node cur = queue.poll();
        //访问元素
        System.out.print(cur.val + " ");

        //把左右子树入队列
        if(cur.left != null){
            queue.offer(cur.left);
        }
        if(cur.right != null){
            queue.offer(cur.right);
        }
    }
}

例图：

遍历规律：

• 先序遍历，第一个访问的节点一定是根节点
• 后续遍历，最后一个访问的节点一定是根节点
• 中序遍历和后序遍历，第一个访问的节点是树的最左侧节点
• 针对先 / 后序遍历来说，子树的遍历结果是嵌套在整个遍历结果中的
• 中序遍历，左子树的遍历结果在根节点的左侧，右子树的遍历结果在根节点的右侧

输出结果：

求二叉树节点个数

public static int size(Node root){
    if(root == null){
        return 0;
    }
    //树节点总数 = 根节点个数(1) + 左子树节点个数 + 右子树节点个数
    return 1 + size(root.left) + size(root.right);
}

输出结果：5

画图分析：

执行顺序和"后序遍历"一模一样

求二叉树叶子节点的个数

叶子节点：即度为0的节点

public static int leafSize(Node root){
    //空树
    if(root == null){
        return 0;
    }
    //只有根节点时，根节点就是唯一的叶子节点
    if(root.left == null && root.right == null){
        return 1;
    }
    // root叶子节点个数 = root.left叶子节点个数 + root.right叶子节点个数
    return leafSize(root.left) + leafSize(root.right);
}

输出结果：3

画图分析：

求第 K 层节点个数

public static int kLevelSize(Node root,int k){
    //若 k<1 或root为空，则为空树
    if(k < 1 || root == null){
        return 0;
    }
    //若 k=1，即为根节点
    if(k == 1){
        return 1;
    }
    // k 层节点个数 = 左子树的(k-1)层节点个数 + 右子树的(k-1)层节点个数
    return kLevelSize(root.left,k-1) + kLevelSize(root.right,k-1);
}

输出结果：2

画图分析：

在二叉树中寻找指定元素

public static Node find(Node root,char toFind){
    if(root == null){
        return null;
    }
    if(root.val == toFind){
        return root;
    }
    //递归查找左右子树
    Node result = find(root.left,toFind);
    if(result != null){
        return result;
    }
    return find(root.right,toFind);
}

画图分析：