乐趣区

关于java:数据结构与算法学习笔记五-树进阶

jiezi

二叉树

二叉树的定义

二叉树是 n(n>=0)个结点的无限集, 它或为空树(n=0)，或由一个根结点和两棵别离称为左子树和右子树的互不相交的二叉树形成。

二叉树是每个结点最多有两个子树的有序树，二叉树的子树通常被称为“左子树”(left subtree) 和“右子树”(right subtree)。左、右子树的程序不能调换。

二叉树的各种状态

二叉树有不同的状态，依照对问题解决的个别情景和特例情景的分类解决准则，咱们能够演绎分类出二叉树的五种根本状态和两种非凡状态，这样不便对二叉树进行探讨。

(1) 二叉树的根本状态，二叉树能够是空集: 根能够有空的左子树或右子树；或者左右子树皆为空。

(2) 二叉树的非凡状态:

① 满二叉树(Full Binary Tree)

满二叉树是除了叶结点外每一个结点都有左右子树且叶子结点都处在最底层的二叉树。或者, 如果深度为 k 的二叉树，有 2 的 k 次方 - 1 个结点称为满二叉树。

②齐全二叉树(Complete Binary Tree)

如果一棵树除最上层外，每一层的结点数均达到最大值, 在最下一层要么是满的，要么在左边短少间断若干结点(要求从最左边开始)，则此二叉树为齐全二叉树。如下图所示:

能够说满二叉树是齐全二叉树的非凡情景。

基本操作

依据二叉树的逻辑构造定义，二叉树具备如下基本操作:

  • 结构：建设一颗二叉树
  • 查找：查找根结点、双亲结点、孩子结点、叶子结点等。
  • 插入: 在指定地位插入结点
  • 删除: 在指定地位删除结点
  • 遍历: 沿着某条搜寻路线，顺次对二叉树中每个结点均做顺次且仅做一次拜访。
  • 求深度: 计算二叉树的深度

链式构造及其根本实现

二叉链表

二叉树的每个结点含有两个指针域来别离指向相应的分支, 咱们个别称之为二叉链表。

对应的数据结构形容:

public class BinaryTreeNode {
    private int data;
    private BinaryTreeNode leftTreeNode;
    private BinaryTreeNode rightTreeNode;
}

这种模式的二叉树，咱们在拿到一个结点之后，便于获取它的孩子结点，获取它的父亲结点就颇为不易了，如果咱们心愿在获取到结点的时候，既能不便获取它的父亲结点，也能获取它的孩子结点呢？

三叉链表

这也就是三叉链表，结点在存储孩子结点的时候，存储父亲结点的地位，如下图所示:

根本性质

  • 二叉树的第 i 层至少有 2 i-1个结点(i >=1)

    用归纳法证实: i = 1 层，只有一个根结点，21-1= 2 0 = 1。

    演绎假如对于所有的 n，n >= 1, 命题成立。

    演绎证实: 二叉树中每个结点至少有两个子树，则第 n + 1 层的结点数 2 n-1 *2 = 2n。命题成立

  • 深度为 h 的二叉树至少有 2 h- 1 个结点（h >= 1）

    证实: 基于上一条性质，深度 k 的二叉树上的结点数至少为:

    20+ 21+…..+2k-1=2k – 1.

  • 对任何一颗二叉树，若它含有 n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2 + 1。

    设 n1 为度为 1 的结点数。叶子结点的度为 0，一颗二叉树度的取值只能为 0,1,2

​ 设二叉树上结点总数: n = n0 + n1 + n2。

​ 二叉树的分支总数为: b = n1 + 2n2。

​ 树中每个结点上都会有一个支路，但唯独有一个结点是例外 – 根结点。所以有 b = n – 1 = n0 + n1 + n2 – 1。由此，n0 = n2 + 1。

  • 具备 n 个结点的齐全二叉树的深度为[log2n] + 1(方括号示意取整)

​ 设齐全二叉树的深度为 k，则根据第二条性质得 2 k-1 <= n < 2k 即 k – 1 <= log2n < k. k 只能是整数, 因而 [log2n ] + 1.

  • 若对含 n 个结点的齐全二叉树从上到下且从左至右进行 1 至 n 的编号，则对齐全二叉树中任意一个编号为 i 的结点:

    若 i = 1, 则该结点是二叉树的根，无双。

    若 2i > n , 则该结点无左结点，否则编号为 2i 的结点为其左孩子结点。

    若 2i + 1 > n , 则该结点无右孩子结点，否则编号为 2i+ 1 的结点为其右孩子结点。

    可用归纳法证实，编号为 i 的结点，如果有左结点，那么左结点的编号为 2i，如果有右结点为 2i+1。

    当 i = 1 时，成立。

    假如当 i = n 时成立，假如有左子结点, 编号为 2n，假如有右子结点，编号为 2n+1.

    如果有左子结点，阐明就有右子结点，因为是齐全二叉树，这两颗结点相邻，所以编号为 n + 1 的结点的左子树为 2i+2，2i+3.

    论断成立。

树的遍历

遍历 (Traversal)– 树的遍历(也称树的搜寻) 是图遍历 (Graph Traversal) 的一种, 指的是依照某种规定，不反复的拜访某种树结构的所有结点的过程。具体的拜访操作可能是查看结点的值、更新结点的值等。不同的遍历形式，其拜访结点的程序是不一样的。

在日常生活中树的遍历也是比拟常见的:

例子 1: 机电设备通电自检的简略模型

任何机电设备都是由若干零部件组成的。例如，计算机硬件由板卡、非板卡等一系列器件组成。能够依照计算机这样的组成分类建设起一个计算机硬件组成的二叉树(事实上是多叉树)，如下图所示:

设施失常工作的前提是每个器件都失常工作，对于各个器件及其组成构件乃至整个设施的状态是否失常，显然从底层开始检测才是对的。

设施通电自检模型检测步骤：

  • 步骤 1: 各器件 (叶子结点) 自检失常
  • 步骤 2: 对二叉树进行“后序遍历”直到根结点逐渐检测。
  • 步骤 3: 如有错误信息则报错，否则显示设施失常。
  • 步骤 4: 完结。

具体的检测步骤如下:

  • 左子树：网卡等失常 -> PCI 失常 -> 显卡等失常 -> 非 PCI 失常 -> 板卡失常。
  • 右子树: 硬盘等失常 -> 外存失常 -> 键盘等失常 -> 其余失常 -> 非板卡失常。

  • 整棵树: 板卡失常 -> 非板卡失常 -> 计算机失常。

    在上述的检测过程中,“后序遍历”的意思是指树的根结点是最初被拜访到的，无论是整棵树还是左右子树。

例子 2: 网购商品的治理

某在线食品店通过类别、色彩和种类来分类组织商品，分类图如下:

要通过程序主动的读出树形架构中的信息并把所有商品名称打印进去，应该怎么做能力做到清晰又没有脱漏呢？咱们能够先列表来剖析一下数据的法则, 如下图所示:

由树到表格中每个结点的打印程序法则是什么呢?

根结点: Food

左子树: Meat -> Pork/Beef

右子树: Fruit -> (左子树) Yellow -> Banana

​ Fruit -> (左子树) Red -> Cherry

打印的程序是树的根结点最先被拜访到，无论是整棵树还是左右子树。以这样的法则来拜访树的结点，咱们能够用一个词来称说它 – 先序遍历。

依照搜寻策略不同，二叉树的遍历可分为按广度优先遍历 (Breadth-First Search) 和深度优先遍历(Depth-First Search) 两种形式。

树的广度优先遍历

广度优先遍历是连通图的一种遍历策略，因为它的思维是从一个顶点开始，辐射状地优先遍历其四周间接相邻的宽泛结点区域故得名。

二叉树的广度优先遍历又称为按档次遍历，从二叉树的第一层 (根节点) 开始，自上至下逐层遍历，在同一层中，依照从左到右的程序对结点逐个拜访。

树的广度优先遍历操作，是从根结点开始拜访，而后以这个结点为线索，程序拜访与之间接相邻的结点 (孩子) 序列, 而后下一步的广度遍历该以什么样的结点做开始的线索呢。

如下图所示, 首次被拜访到的结点是 A, 在链式存储构造上搜寻 A 的间接相邻点, 有 B、C 两个结点，则能够拜访到的结点序列为 ABC，下一次新的搜寻结点从 B 开始，即以拜访结点序列中第一个未做过线索的结点为线索，反复操作，直到所有的结点拜访结束。

上述的操作过程是一个线索结点一直在“曾经拜访序列”中被后移，新拜访结点一直在“已拜访序列”被增加的过程，因而，对“已拜访序列”的操作过程就是一个队列的解决办法. 先进先出。二叉树的数据结构如下图所示:

public class BinaryTreeNode {
    private int data;
    private BinaryTreeNode leftTreeNode;
    private BinaryTreeNode rightTreeNode;
}

队列 add 和 offer 的区别: add 是抛出异样让你解决, offer 是返回 false

树的广度优先遍历:

    /**
     * 广度优先遍历
     * @param root 根结点
     */
    public static void levelOrder(BinaryTreeNode root) {
        // LinkedList 实现了 Queue 咱们用 LinkedList 来实现队列
        LinkedList<BinaryTreeNode>  nodeQueue = new LinkedList<>();
        // 根结点首先入队
        nodeQueue.offer(root);
        while (nodeQueue.size() > 0){BinaryTreeNode node = nodeQueue.poll();
            System.out.println(node.getData());
            BinaryTreeNode leftNode = node.getLeftTreeNode();
            if (leftNode != null){nodeQueue.offer(leftNode);
            }
            BinaryTreeNode rightNode = node.getRightTreeNode();
            if (rightNode != null){nodeQueue.offer(rightNode);
            }
        }
  }

二叉树的深度优先遍历

由二叉树定义可知，一颗二叉树由根结点、根结点的左子树和根结点的右子树三局部组成。因而对二叉树的遍历也能够相应的分解成三项“子工作”。

①: 拜访根结点

②: 遍历左子树(即顺次拜访左子树上的全副结点)

③: 遍历右子树(即顺次拜访右子树上的全副结点)

因为左、右子树又都是二叉树(能够是一颗空的二叉树)。对它们的遍历能够按上述防备持续合成，直到每颗子树均为空二叉树为止。由此可见，上述三项子工作之间的秩序。若以 D、L、R 别离示意这三项子工作，则有 6 种可能的程序:

①: DLR ②: LDR ③: LRD ④: DRL ⑤: RDL ⑥: RLD

通常咱们附带的限度是“先左后右”, 即子工作二在子工作三前实现，这样就只剩下三种秩序:

  • DLR– 先根遍历(前序遍历)
  • LDR– 中根遍历(中序遍历)
  • LRD– 后跟遍历(或后序遍历)

三种遍历办法定义如下:

先序遍历: 先拜访根结点 D, 而后依照先序遍历的策略别离遍历 D 的左子树和右子树。根结点最先拜访，即每次遇到要遍历的子树，都是先拜访子树的根结点。

艰深一点的解释就是: 如果我达到一个结点, 先打印以后结点，再去拜访其余结点。

中序遍历: 先依照中序遍历的策略先遍历根 D 的左子树，而后拜访根结点 D，最初依照中序遍历的策略遍历 D 的右子树。根在两头拜访。

艰深一点的解释就是: 当我达到一个结点的时候, 先判断以后结点的左结点是否为空，如果有就接着向下拜访，没有的话就打印以后结点。

后续遍历: 先后序遍历根的左、右子树，而后拜访根结点 D，根在最初拜访。

艰深一点的解释就是: 当我达到一个结点的时候, 先判断以后结点的左结点是否为空，如果有就接着向下拜访，如果左子树为空就拜访有结点，没有的话就打印以后结点。

从定义上来看这就是递归, 咱们能够依据递归写出代码:

// 前序遍历  
public void frontShow(BinaryTreeNode root){System.out.println(root.getData());
        if (root.getLeftTreeNode() != null){frontShow(root.leftTreeNode);
        }
        if (root.getRightTreeNode() != null){frontShow(root.rightTreeNode);
        }
 }
    public void middleShow(BinaryTreeNode root){if (root.getLeftTreeNode() != null){frontShow(root.leftTreeNode);
        }
        System.out.println(root.getData());
        if (root.getRightTreeNode() != null){frontShow(root.rightTreeNode);
        }
    }
 public void rightShow(BinaryTreeNode root){if (root.getLeftTreeNode() != null){frontShow(root.leftTreeNode);
        }
        if (root.getRightTreeNode() != null){frontShow(root.rightTreeNode);
        }
        System.out.println(root.getData());
 }

栈是实现递归时最罕用的辅助构造，利用一个栈来记录尚待遍历的结点, 以备当前拜访，咱们能够将递归的深度优先遍历改为非递归的算法。

(1) 非递归前序遍历

对于二叉树各结点的拜访程序是沿其左链一路拜访下来, 在拜访结点的同时将其入栈，直到左链为空。而后结点出栈, 对于每个出栈结点，即示意该结点和其左子树已被拜访完结，应该拜访该结点的右子树。

  • 筹备一个长期变量指向根结点
  • 打印以后结点, 以后长期变量指向左子结点并进栈，反复(2)，直到左孩子为 NULL
  • 顺次退栈, 将以后指针指向右孩子
  • 若栈非空或以后指针非 NULL, 执行(2)，否则完结。

遇到一个结点，就拜访该结点，并把此节点推入栈中，而后去遍历它的左子树。

代码示例 1:

public void frontShowNoRecursion(BinaryTreeNode root) {Stack<BinaryTreeNode> stack = new Stack<>();
        do{while (root != null){System.out.println(root.getData());
                stack.push(root);
                root = root.getLeftTreeNode();}
            if (!stack.isEmpty()){root = stack.pop();
                 root = root.getRightTreeNode();}
        }while (!stack.isEmpty() || root != null); // 只有栈外面有元素或者 root 不为 null 都代表没完结
    }

代码示例 2:

public void frontShowNoRecursion2(BinaryTreeNode root) {Stack<BinaryTreeNode> stack = new Stack<>();
        if (root != null){stack.push(root);
            while (!stack.isEmpty()){BinaryTreeNode head = stack.pop();
                System.out.println(head);
                if (head.rightTreeNode != null){stack.push(head.rightTreeNode);
                }
                if (head.leftTreeNode != null){stack.push(head.leftTreeNode);
                }
            }
        }
 }

代码示例 2 的思路是: 先压入根结点, 因为栈是先进后出的, 先序遍历是 根 左 右，所以须要让右结点先入栈，而后再进入左结点。

(2) 非递归中序遍历

中序遍历的程序是左 头 右。依据栈的特点为了实现这样的个性，越晚打印的咱们越早入栈。遍历步骤为:

  • 首先将整颗左子树压入栈中。如下图的左子树:

  • 下一个结点不再有左子树的时候, 出栈每个结点都当作曾经拜访过其左子结点了，而后打印以后结点，而后用这样的形式拜访以后结点的有子树。
 public void middleShowNoRecursion(BinaryTreeNode head) {Stack<BinaryTreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || head != null) {if (head != null) {stack.push(head);
                head = head.leftTreeNode;
            } else {BinaryTreeNode node = stack.pop();
                System.out.println(node.getData());
                head = node.rightTreeNode;
            }
        }
   }

(3) 非递归后序遍历

后序遍历是左 右 根，也就是 3 4 2 6 7 5 1

头 右 左这种模式来遍历的话: 是 1 5 7 6 2 4 3 , 刚好是后序遍历的逆序模式。

头 右 左的遍历模式也就是先压左, 再压右。一个栈来收集头 右 左 这样模式的结点，另一个栈来收集头右左的出栈结点即可实现后序遍历。

代码示例 1:

 public void afterShowNoRecursion(BinaryTreeNode root) {if (root != null) {Stack<BinaryTreeNode> s1 = new Stack<>();
            Stack<BinaryTreeNode> s2 = new Stack<>();
            s1.push(root);
            while (!s1.isEmpty()) {BinaryTreeNode node = s1.pop();
                s2.push(node);
                if (node.leftTreeNode != null){s1.push(node.leftTreeNode);
                }
                if (node.rightTreeNode != null){s1.push(node.rightTreeNode);
                }
            }
            while (!s2.isEmpty()) {System.out.println(s2.pop().getData());
            }
        }
    }

参考资料

  • 《数据结构与算法剖析新视角》周幸妮 任智源 马彦卓 樊凯 编著
退出移动版