关于数据结构:数据结构-二叉树

树的定义

树是一种抽象数据类型，用来模仿具备树状构造性质的数据汇合。树的专业术语比拟多，须要理解一下：

• 树的结点：蕴含一个数据元素及若干指向子树分支的信息
• 结点的度：一个结点含有的子树的数目称为该结点的度
• 树的度：树中最大的结点度称为树的度
• 叶子结点：也称终端结点，结点度为零的结点
• 分支结点：也称非终端结点，结点度不为零的结点
• 子结点：一个结点含有的子树的根结点称为该结点的子结点
• 父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点
• 兄弟结点：具备雷同父结点的结点互称为兄弟结点
• 堂兄弟结点：父结点在同一层的结点互为堂兄弟结点
• 结点的先人：从根到该结点所经分支上的所有结点
• 子孙：以某结点为根的子树中任一结点都称为该结点的子孙
• 结点的档次：从根开始定义起，根为第 1 层，根的子结点为第 2 层，以此类推
• 深度：对于任意结点 n，n 的深度为从根到 n 的惟一门路长，根的深度为 0
• 高度：对于任意结点 n，n 的高度为从 n 到叶子结点的最长门路长，所有叶子结点的高度为 0
• 森林：由 m(m>=0) 棵互不相交的树组成的汇合称为森林

二叉树

树的构造多种多样，不过最罕用的还是二叉树。

顾名思义，二叉是指每个结点最多只有两个子结点，别离称为左子结点和右子结点。然而，二叉树并不要求所有结点必须领有两个子结点，有的结点只有左子结点，有的结点只有右子结点。

满二叉树

如图 a 所示，除叶子结点以外，其余的结点每个都有 2 个子结点，这种二叉树被称为满二叉树。

齐全二叉树

如图 b 所示，除最初一层外，每一层的结点数均达到最大值，而且最初一层的叶子结点都靠左排列，只短少左边的若干结点，这种二叉树被称为齐全二叉树。

能够看得出，满二叉树是一种非凡的齐全二叉树。

二叉查找树

二叉查找树是一种非凡的二叉树，罕用作搜寻应用，也被称为二叉搜寻树、二叉排序树。

它有可能是一棵空树，也可能是具备以下性质的二叉树：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
• 若它的右子树不空，则右子树上所有结点的值均大于等于它的根结点的值
• 它的左、右子树也别离为二叉查找树

二叉查找树是一种经典的数据结构，它既具备链表疾速插入、删除的特点，又具备数组疾速查找的劣势。

存储构造

链式存储

应用链表存储树的构造是一种比较简单、直观的办法。

二叉树中每个结点最多只有两个子结点，因而，能够给结点设计一个数据域和两个指针域，这两个指针域别离指向左子结点和右子结点。

这种状况下，应用链表作为存储形式，只有拎住根结点，就能够通过左右子结点的指针，把整棵树都串起来。

这种形式比拟罕用，大部分二叉树代码都是通过这种形式实现的。

顺序存储

二叉树的顺序存储构造是基于数组实现的，用一维数组存储二叉树中的结点，并且数组的下标可能体现出二叉树结点之间的逻辑关系。

在这个存储二叉树结点的数组中，为了使得后续的结点逻辑关系易于了解，下标为 0 的存储地位是不应用的。个别是把根结点存储在 i = 1 的地位上，它的左子结点存储在 2i = 2 的地位上、右子结点存储在 2i + 1 = 3 的地位上。以此类推，左子结点的左子结点存储在 2i = 4 的地位，它的右子结点存储在 2i + 1 = 5 的地位。

总结二叉树结点在数组中的逻辑关系：如果结点 x 存储在数组中下标为 i 的地位，则结点 x 的左子结点存储在数组中下标为 2i 的地位，右子结点存储在数组中下标为 2i+1 的地位。

能够发现，上述展现的是一个齐全二叉树，应用数组存储齐全二叉树时，会发现除了下标为 0 的地位没有存储数据之外，其余的地位都被填满了。

而如果是非齐全二叉树，则会呈现节约数组中内存空间的状况。如下图所示：

因而，个别应用顺序存储构造存储齐全二叉树，在这种状况下，相比拟链式存储构造会更节俭内存。

堆其实就是一种齐全二叉树，最罕用的存储形式就是数组。

二叉树的遍历

二叉树的遍历是指从根结点登程，依照某种秩序顺次拜访二叉树中的所有结点，使得某个结点仅且被拜访一次。

深度优先遍历

深度优先遍历形式是指尽可能深地搜寻树的分支，即先遍历到叶子结点再更改搜寻门路。二叉树经典的深度优先遍历形式有三种：前序遍历、中序遍历、后序遍历。

其中，前、中、后序，示意的是结点与它的左右子树结点遍历打印的先后顺序：

• 前序遍历是指，对于树中的任意结点来说，先打印这个结点，而后再打印它的左子树，最初打印它的右子树
• 中序遍历是指，对于树中的任意结点来说，先打印它的左子树，而后再打印它自身，最初打印它的右子树
• 后序遍历是指，对于树中的任意结点来说，先打印它的左子树，而后再打印它的右子树，最初打印这个结点自身

其实，二叉树的前、中、后序遍历就是一个递归的过程。比方，前序遍历就是先打印根结点，而后再递归地打印左子树，最初递归地打印右子树。

下述是递归实现前、中、后序遍历的伪代码展现：

void preOrder(Node* root) {if (root == null) return;
    // 打印根结点
    print root;
    // 递归打印左子树
    preOrder(root->left);
    // 递归打印右子树
    preOrder(root->right);
}

void inOrder(Node* root) {if (root == null) return;
    // 递归打印左子树
    inOrder(root->left);
    // 打印根结点
    print root;
    // 递归打印右子树
    inOrder(root->right);
}

void postOrder(Node* root) {if (root == null) return;
    // 递归打印左子树
    postOrder(root->left);
    // 递归打印右子树
    postOrder(root->right);
    // 打印根结点
    print root;
}

除了应用递归的形式实现深度优先遍历外，能够应用栈这种数据结构以非递归形式实现，前序遍历形式如下：

1. 将 A 结点压入栈中，栈的构造是 [A]；
2. 将 A 结点弹出，而后将 A 结点的子结点 B、C 压入栈中，栈的构造是 [C, B]；
3. 将 B 结点弹出，而后将 B 结点的子结点 D、E 压入栈中，栈的构造是 [C, E, D]；
4. 将 D 结点弹出，D 结点没有子结点，无需做解决，栈的构造是 [C, E]；
5. 将 E 结点弹出，E 结点没有子结点，无需做解决，栈的构造是 [C]；
6. 将 C 结点弹出，顺次类推，最终遍历实现。

广度优先遍历

广度优先遍历又称为档次遍历，从上往下对每一层顺次拜访，在每一层中，从左往右（也能够从右往左）拜访结点，拜访完一层再拜访下一层。

档次遍历须要应用到队列这种数据结构，队列的特点是先进先出。整个遍历过程如下：

1. 将 A 结点入队，队列的构造是 [A]；
2. 将 A 结点出队，而后将 A 结点的子结点 B、C 入队，队列的构造是 [B, C]；
3. 将 B 结点出队，而后将 B 结点的子结点 D、E 入队，队列的构造是 [C、D、E]；
4. 将 C 结点出队，而后将 C 结点的子结点 F、G 入队，队列的构造是 [D、E、F、G]；
5. 将 D 结点出队，D 结点没有子结点，无需做解决，栈的构造是 [E、F、G]；
6. 以此类推，最终遍历实现。

优缺点

对于深度优先遍历算法，都是优先搜寻完一颗子树，有着内存占用绝对较小的长处，通常存储结点数是数的深度；非递归的深度优先遍历形式会进行回溯，相对效率比拟低。

对于广度优先遍历算法，对于解决最短或最小问题特地无效，而且结点只拜访一遍，效率绝对较高；应用广度优先算法须要存储一层结点的状态，内存占用绝对较高。