关于数据结构:二叉树和树的小问题

先大略说一下二叉树的根本内容。

1. 二叉树

什么是二叉树？

二叉树是一种树形构造，每个结点最多两棵子树，而且子树有左右之分，秩序不能颠倒。左右子树也是一棵二叉树。

1.1 二叉树的存储

二叉树能够用数组和链表存储。

1）顺序存储

应用一组地址间断的存储单元顺次自上而下，自左而右的顺序存储二叉树上的结点。简略来说，就是用数组存储，存二叉树的程序是从上到下，从左到右。

顺序存储形式适宜齐全二叉树或满二叉树。因为数组的长度是固定的，而这种二叉树的空节点少，不会节约很多数组的地址空间。

// java 定义形式int[] array = new int[3];array[0] = 1;array[2] = 3;// 或者是int[] array = {1, 0, 3};  // 0 示意该处节点为空

2）链式存储

因为个别二叉树会有很多节点为空，如果应用顺序存储会导致很多空间节约掉。所以个别的二叉树应用链式存储比拟多。大多状况下，用到的也是链式存储，比方常常应用到的遍历。

链式存储是应用链表节点来存储二叉树中的每个节点。所有须要先定义链表的结点。

// java 定义形式class TreeNode {    int val;    TreeNode left, right;    // 构造函数}

1.2 二叉树的遍历

二叉树的遍历办法：前序遍历、中序遍历、后序遍历，应该没有人不晓得。以下的代码是应用java实现

1）前序遍历

void preOrder(TreeNode root) {    // 终止条件    if (root == null) return;    getValue(root);  // 拜访该结点，做一些计算等    preOrder(root.left); // 遍历左结点点    preOrder(root.right);  // 遍历右结点}

2）中序遍历

void preOrder(TreeNode root) {    // 终止条件    if (root == null) return;    preOrder(root.left); // 遍历左结点点    getValue(root);  // 拜访该结点，做一些计算等    preOrder(root.right);  // 遍历右结点}

3）后序遍历

void preOrder(TreeNode root) {    // 终止条件    if (root == null) return;    preOrder(root.left); // 遍历左结点点    preOrder(root.right);  // 遍历右结点    getValue(root);  // 拜访该结点，做一些计算等}

4）例子

这三种遍历办法的代码并不难，平时做题的时候也没有很大的问题。然而有一次在极度缓和下，我发现做题时居然分不清过后用的是哪种遍历，是前序还是中序还是回溯来着？？是该用哪种写代码呢？？

以求树中的最大值、最小值为例。有这样一棵树，通过遍历的形式求出二叉树中的最大值、最小值。

那么，在遍历中，须要记录以后结点的最大值和最小值，上面的图中，[最大值, 最小值] 记录的是以后的最大值和最小值。

前序遍历

走到结点 1 （遍历结点），记录下以后的最大值和最小值 [1, 1] （拜访结点），而后遍历左子树，遍历完左子树再右子树。图中圆圈中记录的是结点的拜访程序，前序的遍历程序和拜访程序雷同。

中序遍历

以结点 1 为例，走到结点 1 （遍历结点），不记录。当把左子树的节点拜访完之后，而后拜访结点 1，也就是记录结点 1 此时的最大值最小值 [5, 1] 。而后再拜访结点 1 的右子树。

所以，第一个记录最大值和最小值的结点是结点 4 ，也就是第一个拜访的结点是结点 4 。第二个记录最大值和最小值的结点是结点 2 ，也就是第二个拜访的结点是结点 2 。

图中圆圈中记录的是结点的拜访程序，中序的遍历程序和拜访程序不同。

后序遍历

以结点 1 为例，走到结点 1 （遍历结点），不记录。当把左子树的节点拜访完之后，而后再拜访结点 1 的右子树。最初拜访结点 1 ，也就是记录结点 1 此时的最大值最小值 [6, 1] 。

所以，第一个记录最大值和最小值的结点是结点 4 ，也就是第一个拜访的结点是结点 4 。第二个记录最大值和最小值的结点是结点 5 ，也就是第二个拜访的结点是结点 5 。

图中圆圈中记录的是结点的拜访程序，后序的遍历程序和拜访程序不同。

遍历程序的问题就到这里了。上面的代码是求二叉树中的最大值和最小值，代码应用java实现。

int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;public void getMaxDifference(TreeNode root) {    if (root == null) return;        if (root.val > max) max = root.val;    if (root.val < min) min = root.val;       getMaxDifference(root.left);    getMaxDifference(root.right);}

4）档次遍历

档次遍历是通过队列实现的，以下的代码是应用java实现

// 遍历二叉树，其余什么也没做void level(TreeNode root) {    LinkedList<TreeNode> queue = new LinkedList<>();    if (root != null) queue.offer(root);  // 退出根节点    while (!queue.isEmpty()) {        // 弹出队首节点        TreeNode cur = queue.poll();          // 退出左右节点        if(cur.left != null) queue.offer(cur.left);        if(cur.right != null) queue.offer(cur.right);    }}

2. 树

二叉树是树，但树不肯定是二叉树。所以，二叉树和树的关系就很显著：二叉树能够应用树的货色，树不能应用二叉树的货色。

为什么这里会说到树呢？

因为在一次面试中遇到一道题，是应用数组存储二叉树，数组中的值是它的父节点的下标。嗯嗯，如果把二叉树和树割裂开记忆学习，思维会局限在那一小块。不只是二叉树和树，其余的常识也应该分割在一起，也能够分割在一起。

2.1 树的存储形式

树的存储形式有很多中，即可用顺序存储，也可用链式存储。然而不论哪种存储形式，都要可能惟一的反映树中各节点之间的逻辑关系。这一点，对于二叉树来说也是一样。因为树中有几个子节点，是不确定的，所以不能像二叉树中那样，间接定义两个子节点 left， right ，就能够示意整个树。

1）双亲表示法

记录的是以后节点的父结点。应用数组存储，存储的是以后节点的父节点在数组中的地位。

正式点的术语说就是，采纳一组间断空间来存储每个节点，同时每个节点减少一个变量（指针），用来记录该节点的双亲节点在数组中的地位。

这种构造，找到以后结点的父节点很容易，然而找到以后结点的孩子节点，须要遍历整个树，也就整个存储构造。

下面的树的存储构造，能够示意为以下（应用 java 实现）

// 定义结点class TreeNode {    int val;    int parent;    // 构造函数}// 定义一棵树TreeNode[] tree = new TreeNode[10];

如果一棵树中节点的值就是数组中的下标，那么还能够不存储 val ，示意如下（应用 java 形容）

int[] tree = new int[10];

举个例子，如果一个数组是 int[] tree = {1, -1, 1, 0} ，那么这棵树示意的就是，根节点是 1， 1 的两个子节点是 0 ，2 ， 0 的一个子节点是 3 。

嗯嗯嗯，这个如同是二叉树？？嗯，就是二叉树，用数组示意了一棵一般的二叉树（当然了，这种示意形式不能辨别左右子节点）。

2）孩子表示法

记录的是以后节点的所有子结点。

正式点的术语说就是，每个结点的孩子都用单链表连接起来，造成一个线性构造，

这种构造，找到以后结点的孩子节点很容易，然而找到以后结点的父节点，须要遍历整个树，也就整个存储构造。

下面的树的存储构造，能够示意为以下（应用 java 实现）

// 定义结点class TreeNode {    int val;    List<TreeNode> child;    // 构造函数}// 定义一棵树TreeNode[] tree = new TreeNode[10];

如果一棵树中节点的值就是数组中的下标，那么还能够不存储 val ，示意如下（应用 java 形容）

List<Integer>[] tree = new List[10];

3）孩子兄弟表示法

记录的是以后节点的第一个子结点和下一个兄弟节点。孩子兄弟表示法又称二叉树链表法，也就是将二叉链表作为树的存储构造，一个子结点指向孩子结点，一个子结点指向兄弟节点。

下面的树的存储构造，能够示意为以下（应用 java 实现）

// 定义结点class TreeNode {    int val;    TreeNode firstChild, nextsibling;    // 构造函数}// 定义一棵树TreeNode[] tree = new TreeNode[10];

参考资料

王道数据结构书籍