乐趣区

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

jiezi

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

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）例子

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

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

<img src=”https://gitee.com/withered-wood/picture/raw/master/20220119223731.jpg” alt=”1-1″ style=”zoom: 80%;” />

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

前序遍历

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

<img src=”https://gitee.com/withered-wood/picture/raw/master/20220119234925.jpg” alt=”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）孩子表示法

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

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

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

<img src=”https://gitee.com/withered-wood/picture/raw/master/20220119183800.png” alt=”image-20220119183757642″ style=”zoom:80%;” />

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

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

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

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

3）孩子兄弟表示法

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

<img src=”https://gitee.com/withered-wood/picture/raw/master/20220119214510.png” alt=”image-20220119214509319″ style=”zoom:80%;” />

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

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

参考资料

王道数据结构书籍

退出移动版