Feng's Blog

kiwidict.com

0%

数据结构系列之树（Java）

Posted on Edited on In

leetcode树专题

树的定义

树是由n个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
当n=0时，称为空树。

树的特点

  • 每个节点都只有有限个子节点或无子节点；
  • 没有父节点的节点称为根节点；
  • 每一个非根节点有且只有一个父节点；
  • 除了根节点外，每个子节点可以分为多个不相交的子树；
  • 树里面没有环路(cycle)。

树的术语

  • 根节点： 根节点没有父节点，树中最多有一个根节点（如上图的Root）；
  • 节点的度：一个节点含有的子树的个数称为该节点的度（如上图的Root的度为3，L2_*所有节点的度为0）；
  • 树的度：树中最大的节点度称为树的度（如上图树的度=Root的度=L1_C的度）；
  • 叶节点（终端节点）：度为0的节点（如上图L2_*的所有节点）；
  • 父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
  • 子节点：一个节点的子树的根节点称为其孩子节点；
  • 兄弟节点：具有相同父节点的节点互称为兄弟节点；
  • 树的层（节点的层）：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
  • 分支节点（非终端节点）：度不为零的节点；
  • 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
  • 高度：对于任意节点n,n的高度为从n到其子孙中的最长路径，所有树叶的高度为0；
  • 节点的祖先：从根到该节点所经分支上的所有节点；
  • 森林：由m（m>=0）棵互不相交的树的集合称为森林；
  • 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。

有序树

二叉树

二叉树（Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构，是n(n≥0)个节点组成的有限集合：

  • n=0时称为空二叉树；
  • n>0的二叉树由一个根节点和两棵互不相交的子树组合而成，通常分支被称作“左子树”或“右子树”，二叉树的分支具有左右次序，不能随意颠倒。

二叉树的五种形态

三个节点的二叉树有多少种？

五种。

二叉树的性质

  • 二叉树的第i层上至多有$2^{i-1}(i≥1)$个节点；
  • 深度为h的二叉树中至多含有2^{h}-1个节点;

完全二叉树（Complete Binary Tree）

假设二叉树的深度为h，除第h层外，其它各层[1～h-1]的节点数都达到最大个数，第h层所有的节点都连续集中在最左边，这就是完全二叉树
换句话说，在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续一个或若干节点，则此二叉树为完全二叉树。
比如，下面三棵树都是完全二叉树：

完全二叉树的性质
  • 若i≤[n/2]， 则节点i为分支节点，否则为叶子节点。
  • 叶子节点只可能在层次最大的两层上出现。对于最大层次的叶子节点，都依次排在最左边的位置上。
  • 度为1的节点若存在，则最多只能只有一个，且是编号最大的分支节点，其孩子节点一定是左节点。
满二叉树

一棵高度为h的满二叉树（Full Binary Tree）是具有$2^{h}−1(h≥0)$个节点的二叉树。满二叉树的最大特点是每一层次的节点数都达到最大值。

对于编号为i的节点，若存在，其双亲的编号为i/2,左孩子为2i,右孩子为2i+1。

二叉树的存储结构

二叉树可以用数组或链接串列来存储，主要采用的是链式存储结构，至于顺序存储结构仅适用于完全二叉树或满二叉树，若是满二叉树就能紧凑排列而不浪费空间。

顺序存储结构

用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的节点元素。

但是如果二叉树树是非完全二叉树的情况下，就必须使用顺序表的空元素来代替，如：

这样的话，在非完全二叉树的情况下，采用顺序存储结构的二叉树就有很大弊端了，可能会造成很大空间的浪费，比如这种类型的树：

因此，非完全二叉树还是要使用链式存储结构来实现，这也是最常见的实现二叉树的存储结构。

二叉树的链式存储结构
  • 双指针链式存储结构
    双指针链式结构主要由一个数据域和两个分别指向左、右孩子的指针组成。

    从图中可以看出，采用双指针链式存储结构，每个节点只存储了到其孩子节点的单向关系，而没有存储到父节点的关系，这样的话，每次要获取父节点时将消耗较多的时间，因为需要从root根节点开始查找，花费的时间是遍历部分二叉树的时间。
  • 三指针链式存储结构
    三指针链式结构主要是在双指针的基础上多添加了一个指向父节点的域，这样我们就存储了父节点与孩子节点的双向关系，当然这样也增加了一定的空间开销。

二叉查找树（二叉排序树、二叉搜索树、Binary Seary Tree）

二叉查找树的特性是，对于树种的每个节点T,它的左子树中所有项的值小T中的值，而它的右子树中所有项的值都大于T中的值。

它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势。

二叉排序树的查询

二叉树非空时，查找根结点，若相等则查找成功;
若不等，则当小于根结点值时，查找左子树;当大于根结点的值时，查找右子树。
当查找到叶节点仍没查找到相应的值，则查找失败。

BOILERPLATE（递归转非递归并非一定要通过栈）:

1
2
3
4
5
6
7
8
9
10
public TreeNode searchBST(TreeNode node, int key){
    while(node !=null && key != node.val){
        if(key < node.val){
            node = node.left;
        }else{
            node = node.right;
        }
    }
    return node;
}

二叉树的遍历

先序（先根次序）遍历
  • 访问根节点
  • 先序遍历左子树
  • 先序遍历右子树

比如以下二叉树的访问次序是：1、2、4、5、3

先根遍历的递归实现
1
2
3
4
5
6
7
8
9
10
private String preOrder(BinaryNode<T> node){
    if (node!=null) {
        //先访问根节点
        peek(node);
        //遍历左子树
        preOrder(node.left);
        //遍历右子树
        preOrder(node.right);
    }
}

也可以使用非递归实现，比如使用栈。

中序（中根次序）遍历

二叉搜索树的中序遍历的序列是递增排序的序列，中序遍历的遍历次序：Left -> Node -> Right。

  • 中序遍历左子树
  • 遍历根节点
  • 中序遍历右子树

比如以下二叉树遍历顺序是a、b、c，也就是4、2、5、1、3、6：

中序遍历的递归实现

1
2
3
4
5
6
7
8
9
10
private String inOrder(BinaryNode<T> node){
    if (node!=null) {
        //遍历左子树
        inOrder(node.left);
        //先访问根节点
        peek(node);
        //遍历右子树
        inOrder(node.right);
    }
}
中序遍历的非递归实现

可以使用栈来实现。

遍历思想：

  • 1、初始时依次扫描根节点的所有左侧节点并将它们进栈;
  • 2、出栈一个节点，访问它;
  • 3、扫描该节点的右节点并将其进栈;
  • 4、依次扫描右节点的所有左侧节点并一一进栈;
  • 5、反复该过程直到栈空为止。

比如以下树，进出栈顺序为：

  • 进栈：1、2、4、7（遍历思想第1步）；
  • 出栈：7；（栈中：：1、2、4，遍历思想第2步）
  • 访问7所在节点，尝试拿到其右节点压入栈，但是此时为空，不能递归空节点是否有左节点（遍历思想上面的第3步）；
  • 出栈：4；（栈中：1、2，遍历思想第2步）
  • 遍历思想第3步，此时为空；
  • 出栈：2；（栈中：1，遍历思想第2步）
  • 遍历思想第3步，发现其右节点；
  • 进栈：5；（栈中：1、5）
  • 遍历思想第4步，此时为空；
  • 出栈：5；（栈中：1，遍历思想第2步）
  • 遍历思想第3步，此时为空；
  • 出栈：1（遍历思想第2步）
  • 遍历思想第3步，此时发现右节点，进栈3（栈中：3）；
  • 遍历思想第4步，此时发现左节点，进栈6（栈中：3、6）；
  • 重复第2步2次，至此结束。

所以不难发现，其实z整个过程只是在遍历思想的5步中循环，从第3步到第4步，只要访问想要的节点为空就退回到上一步然后继续往后走，直至栈空。

BOILERPLATE：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void inOrder(TreeNode node){
    Stack stack = new Stack();
    Object e = node;
    while(e != null || !stack.isEmpty()){
        if(e != null){
            stack.push(e);
            e = e.left;
        }else{
            e = stack.pop();
            peek(e);
            e = e.right;
        }
    }
}
后序（后根次序）遍历
  • 后序遍历左子树
  • 后序遍历右子树
  • 访问根节点

比如以下二叉树遍历顺序是a、b、c，也就是4、5、2、6、3、1：

后序遍历的递归实现
1
2
3
4
5
6
7
8
9
10
private String postOrder(BinaryNode<T> node){
    if (node!=null) {
        //遍历左子树
        postOrder(node.left);
        //遍历右子树
        postOrder(node.right);
        //先访问根节点
        peek(node);
    }
}

同样也可以使用栈来实现。

层次遍历

使用队列来实现。

遍历思想：

  • 1、初始将根入队并访问根结点，然后出队;
  • 2、若有左子树，则将左子树的根入队;
  • 3、若有右子树，则将右子树的根入队;
  • 4、然后出队，访问该结点;
  • 5、反复该过程直到队列空为止。

BOILERPLATE：

1
2
3
4
5
6
7
8
9
10
void levelOrder(BiTree root){
    queue.push(root);
    BiTree node;
    while(!queue.isEmpty()){
        node = queue.pop();
        peek(node);
        if(node.left != null) queue.push(node.left);
        if(node.right != null) queue.push(node.right);
    }
}
遍历序列确定唯一二叉树

后序或者先序遍历序列+中序遍历序列，可以确定一颗唯一二叉树。
比如：

  • 先序遍历序列（1、2、4、5、3、6）
  • 中序遍历序列（4、2、5、1、6、3）

其对应的树如下：

线索二叉树

线索化：

  • 若无左子树，则将左指针指向其前驱结点;
  • 若无右子树，则将右指针指向其后继结点。
线索二叉树

比如先序遍历序列为124536的二叉树先序线索化如下图：

同样是这颗树的中序序列为425163，其对应的中序线索化如下图：

其后序线索二叉树452631也是同理。
最常用的是中序线索二叉树。
中序线索二叉树线索化的BOILERPLATE:

1
2
3
4
5
6
7
class TreeNode {
        String data;    //数据域
        Node left;      //左节点
        Node right;     //右节点
        boolean isLeftToPre;  
        boolean isRightToNext; 
}
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
// 方法调用传入二叉树的中序遍历后的顺序的第一个节点对象实例
public void initInThread(TreeNode first){
    TreeNode pre = null;
    inThreadOrder(first, pre);
    pre.right = null;
    pre.isLeftToPre = true;
}
public void inThreadOrder(TreeNode node, TreeNode pre){
    if(node == null) return;
    inThreadOrder(node.left, node);
    if(node.left == null){
        node.left = pre;
        node.isLeftToParent = true;
    }
    if(pre != null && pre.right == null){
        pre.right = node;
        pre.isRightToNext = true;
    }
    pre = node;
    inThreadOrder(node.right, node.pre);
}
// 寻找中序排列第一个节点，传入根节点
publid TreeNode firstNode(TreeNode node){
    while(!node.isLeftToPre){
        node = node.left;
    }
    return node;
}
// 寻找中序排序之后的后继节点
publid TreeNode nextNode(TressNode node){
    if(!node.isRightToNext){
        return firstNode(node.right);
    }
    return node.right;
}
// 所以，中序线索化遍历某颗树可以这么实现：
// 传入树的根节点，简单明了
public void inOrder(TreeNode root){
    for(TreeNode temp = firstNode(root); temp != null; temp = nextNode(temp)){
        peek(temp);
    }
}
线索二叉树数据结构特点

其节点数据结构增加两个Boolean类型的标志域（成员变量）：

  • isLeftToPretrue时代表其左孩子节点指向其前驱节点，反之代表其左孩子节点指向其后继节点。
  • isRightToNext：当为true时代表其右孩子节点指向其前驱结点，反之代表其右孩子节点指向其后继节点。

字典树（前缀树、trie）

trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值（或者说真实的值）。

霍夫曼树

B树

无序树

参考来源维基百科、王道考研等