Welcome to Mility!

数据结构中树的介绍

树是一种在实际编程中经常遇到的数据结构。它的逻辑很简单:除了根节点之外每个节点只有一个父节点,根节点没有父节点;除了叶节点之外所有的节点都有一个或多个子节点,叶节点没有子节点。通常树有如下几种遍历方式: 前序遍历:先访问根节点,再访问左子节点,最后访问右子节点。 中序遍历:先访问左子节点,再访问根节点,最后访问右子节点。 后序遍历:先访问左子节点,再访问右子节点,最后访问根节点。 宽度优先遍历:先访问数的第一层节点,再访问树的第二层节点……一直到访问到最下面一层节点。在同一层节点中,以从左到右的顺序依次访问。 二叉树右很多特例,二叉搜索树就是其中的一种。在二叉搜索树中,左子节点总是小于或等于根节点,而右子节点总是大于或等于根节点。 二叉树的另外两个特例是堆和红黑树。堆分为最大堆和最小堆。在最大堆中根节点的值最大,在最小堆中根节点的值最小。有很多需要快速找到最大值或者最小值的问题都可以用堆来解决。红黑树是把树中的节点定义为红、黑两种颜色,并通过规则确保从根节点到叶节点的最长路径的长度不超过最短路径的两倍。 /* * ConstructCore.cpp * * Created on: 2016年7月12日 * Author: mility */ /** * 功能:输入二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如 * 输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}。 */ #include <iostream> #include... Read more »

ReplaceBlank

好久没有更新博客,不过之前也是胡诌的啦。由于最近在看何大牛的剑指Offer,于是就想在这里重新记录一下。 这里的面试题目为:请实现一个函数,把字符中的每个空格替换成“%20”。例如输入“We are happy.”,则输出为“We%20are%20happy.”。 要求时间复杂度为O(n)的解法,搞定offer就靠它了。 源代码如下: #include <iostream> #include <string> #include <vector> using namespace std; void replace_blank(char strs[], int length) { int i, j, count = 0, original_length = 0;... Read more »

难得好天气

开学到现在倒有一月有余,一直阴雨连绵。鞋帽衣袜多有不干,被子更甚。目下,天朗气清,惠风和畅。 遂携被子与长廊之上,晾晒之。 Read more »

When to use subordinate clause

A subordinate clause—also called a dependent clause—will begin with a subordinate conjunction or a relative pronoun and will contain both a subject and a verb. This combination of words will... Read more »