dvlproadの博客

必备知识架构-数据结构

[toc]

Here are main question we will ask during interview:
1.Data Structure:
a.linked lists
b.Stacks
c.Queues
d.binary trees
e.hash tables
2.Algorithms:
a.Sort (like quick sort and merge sort), binary search, greedy algorithms.
b.Binary tree(like traversal, construction, manipulation..)
You can find more to do exercises on https://leetcode.com/

以下是我们在面试中要问的主要问题：

1.数据结构：
a、 链接列表
b、 堆栈
c、 队列
d、 二叉树
e、 哈希表

2.算法：
a、 排序（像快速排序和合并排序），二进制搜索，贪婪算法。
b、 二叉树（比如遍历、构造、操作…）

你可以找到更多的练习https://leetcode.com/

一、二叉树

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。

在二叉树中，一个元素也称作一个结点。

节点:二叉树中每个元素都称为节点。

叶子结点：就是出度为0的结点，就是没有子结点的结点。

二、几种二叉树

满二叉树、完全二叉树、平衡二叉树、最优二叉树

1、完全二叉树

若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边，这就是完全二叉树。

2、满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

满二叉树的第i层上有2

个结点 (i≥1)。

满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

3、平衡二叉树

一文读懂平衡二叉树｜技术头条

二叉搜索树（Binary Search Tree），又叫二叉排序树，简单而言就是左子树上所有节点的值均小于根节点的值，而右子树上所有结点的值均大于根节点的值，左小右大，并不是乱序，因此得名二叉排序树。

二叉搜索树的结构与值的插入顺序有关，同一组数，若其元素的插入顺序不同，二叉搜索树的结构是千差万别的。

为了避免二叉搜索树变成“链表”，我们引入了平衡二叉树(平衡二叉树必须是二叉搜索树)，即让树的结构看起来尽量“均匀”，左右子树的节点数尽量一样多。

举例：给出一组数[1,3,5,8,9,13]。假设我们就按[1,3,5,8,9,13]这样的顺序插入，其流程是这样的：

4、最优二叉树（哈夫曼树）

漫画：什么是 “哈夫曼树”？

在介绍哈弗曼树之前，我们必须先弄清楚和树相关的四个概念。

概念1：什么是路径？

在一棵树中，从一个结点到另一个结点所经过的所有结点，被我们称为两个结点之间的路径。

概念2：什么是路径长度？

在一棵树中，从一个结点到另一个结点所经过的“边”的数量，被我们称为两个结点之间的路径长度。

概念3：什么是结点的带权路径长度？

结点的带权路径长度，是指树的【根结点到该结点的路径长度】和【该结点权重】的【乘积】。

概念4：什么是树的带权路径长度？

在一棵树中，【所有】【叶子结点】的带权路径长度之和，被称为树的带权路径长度，也被简称为WPL。

哈夫曼树（Huffman Tree）是在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树。

问：怎样构建二叉树，才能保证其带权路径长度最小？

答：原则上，我们应该让权重小的叶子结点远离树根，权重大的叶子结点靠近树根。

例：下图左侧的这棵树就是一颗哈夫曼树，它的WPL是46，小于之前例子当中的53。

1*3+3*3+4*2+6*2+8*2=48 （3+6)*3+（1+4+8）*2=27+26=53

需要注意的是，同样叶子结点所构成的哈夫曼树可能不止一颗，下面这几棵树都是哈夫曼树

问：怎么利用给定的结点和权重，构建哈弗曼树？

答：想看 漫画：什么是 “哈夫曼树”？ 还是很好理解的。

二叉树遍历

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

参考文章：二叉树的遍历（前序、中序、后序、已知前中序求后序、已知中后序求前序）

前序遍历：根节点->左子树->右子树（根->左->右）

中序遍历：左子树->根节点->右子树（左->根->右）

后序遍历：左子树->右子树->根节点（左->右->根）

• 前序遍历结果：GDAFEMHZ
• 中序遍历结果：ADEFGHMZ
• 后序遍历结果：AEFDHZMG

进入正题，已知两种遍历结果求另一种遍历结果（其实就是重构二叉树）

1、前序遍历的第一元素是整个二叉树的根节点

2、中序遍历中根节点的左边的元素是左子树，根节点右边的元素是右子树

3、后序遍历的最后一个元素是整个二叉树的根节点