树基本概念树的定义树是 nn ≥ 0个结点的有限集。当 n 0 时称为空树当 n 0 时称为非空树任意一棵非空树都满足以下条件1.有且仅有一个根结点。2. 当 n 1 时其余结点可分为 mm 0个互不相交的有限集其中每一个集合本身又是一棵树称为子树。树的根结点没有前驱结点除根结点以外的所有结点有且只有一个前驱结点而树中的所有结点可以有多个后继结点。树是一种递归定义的数据结构。基本术语结点间的关系描述类似于人类的亲缘关系1.祖先从根结点到该结点所经分支的所有的结点都是该结点的祖先。2. 子孙以某一结点为根的子树中任意结点都是该结点的子孙。3.孩子/双亲结点所有子树的根结点称为该结点的孩子对应的该结点是孩子的双亲。4.兄弟同一个双亲结点的孩子之前的关系。5.堂兄弟双亲在同一个层的结点是堂兄弟。结点与树之间的属性描述1.度树中一个结点的孩子结点是该结点的度树中结点最大的度数是树的度。2.叶子结点/终端结点度为0结点。3.分支结点/非终端结点度不为0的结点。4.结点的层次从根开始定义根结点是第一层以此往下推5.树的高数/深度树中结点的最大层数称为树的深度/高度。6.有序树和无序树有序树树中的结点按从左到右的顺序结点之间不会随意的调换。无序树则反之需要保证父子之间关系保持不变。7.路径树中的两个结点之间的路径是又这两个结点所经过的结点的序列构成的路径的长度为序列结点个数长度结点树8.边表示双亲和孩子之间的链接关系。一般在图中使用。性质1.树中的结点数所有结点数的度数1根结点数/所有边结点数12.m叉树中第 i 层上至多有m^i−1个结点 i≥ 1m叉树这个树中每一个结点最多有m个孩子至少有0个孩子。3.解释高度为h的m叉树的第h层的每一个分支的叶子结点就是m个这时就为结点树最多的时候所以可以得出第h层的结点数m^k-1假设层数是i则第i层的结点数是m^i-1。当计算从第一层到第i层时是使用等比数列求和公式。二叉树定义二叉树是一个有序树每个结点最多两个孩子最少一个也没有孩子还有左右之分左边的叫左子树右边的叫右子树。二叉树也是一个递归定义的数据结构。特殊的二叉树满二叉树满二叉树一个高度为h的二叉树每层结点树都达到最满合计有2^h -1个结点的二叉树叫满二叉树。满二叉树的叶子结点在最后一层且分支结点的度为均为2。满二叉树是当前⾼度下二叉树结点数的最大的形态。完全二叉树1.高度为h的二叉树前h-1 层都是结点已经到达了最大但是第h层不一定是满的但是满足从左到右结点都是连续的。2.完美二叉树是完全二叉树的特殊情况。3.左边的值表示的是第h层的结点只有一个右边的值表示是完美二叉树4.完全二叉树的叶子一定只出现在树的倒数第一二层并且度为1的结点只有一个其他的结点的度是2或者是0。搜索二叉树与中序遍历有关(左根右)又叫排序二叉树左子树上的值根结点的值右结点的值性质1.在二叉树的第i层之上组最多的结点有 2^(i-1)个。2.高度为h的二叉树至多有2^h -1(h1)3.对任意的二叉树如果度为0结点数是N0度为2的结点树为N2,则N0N21。解释设度为1的结点数是N1.树的结点 度数1 N0N12*N21 结点数 N0N1N2结点是一个一个的所以的树的结点是直接相加而度则是结点下面的所以在度数相加的时算的是结点下面的度把上面的结点没有算进去。4.具有n个结点的完全二叉树的高度为⌊logn⌋ 1二叉树存储结构二叉树可以使用顺序存储结构也可以是链式存储结构。1.顺序存储结构将二叉树每层的结点的元素从右到左从上到下依次存到数组中空结点也要存储在数组中用特殊的元素进行标记这个特殊元素一定是二叉树中没有的。非完全二叉树使用顺序存储会存在一定空间浪费的行为空的结点越多就越浪费。可以使用链式存储的方式。一般l每层结点存储在数组中都是从0开始的有些地方是从0开始的。是0作为开始的 假设x结点的存储位置的下标是i那么x结点的双亲结点的存储位置就是i-1/ 2。x的左孩子结点存储位置的下标是2i1右孩子存储位置的下标是2i2。堆定义小根堆根结点中的值是最小的双亲结点小于或等于孩子结点兄弟之间没有大小之分。大根堆根结点的值最大双亲大于或者等于孩子兄弟之间无大小。两种存放数据的方式可以快速的找到最大值和最小值。堆的插入HeapPush思路将数据插入到最后的位置插入前需要判断一下capacity与size的大小是否是相等的相等说明空间已经满了或者说这里没有空间所以这里需要扩容。在进行扩容时需要注意的是这里是对这个数组进行扩容而不是对这个数据结构结构进行扩容。assert(hp); if (hp-_size hp-_capacity) { int newcapacity hp-_capacity 0 ? 4 : hp-_capacity * 2;//需要扩容到好多空间数 HPDataType* tmp (HPDataType*)realloc(hp-_a, sizeof(HPDataType) * newcapacity);//这里正式开始扩容 if (tmp NULL) { printf(realloc fail\n); exit(0); } hp-_a tmp; hp-_capacity newcapacity; }向上调整算法将插入的结点的值与双亲结点进行比较然后根据大小进行调整。时间复制度O(lgN)然后开始插入数据插入的结点与双亲结点进行比较这里以小根堆为例子注意void HeapPush(Heap* hp, HPDataType x) { assert(hp); if (hp-_size hp-_capacity) { int newcapacity hp-_capacity 0 ? 4 : hp-_capacity * 2;//需要扩容到好多空间数 HPDataType* tmp (HPDataType*)realloc(hp-_a, sizeof(HPDataType) * newcapacity);//这里正式开始扩容 if (tmp NULL) { printf(realloc fail\n); exit(-1); } hp-_a tmp; hp-_capacity newcapacity; } hp-_a[hp-_size] x; hp-_size; //小根堆 int child hp-_size - 1; int parent (hp-_size - 1 - 1) / 2; while (child) { if (hp-_a[child] hp-_a[parent]) { break; } HPDataType tmp hp-_a[parent]; hp-_a[parent] hp-_a[child]; hp-_a[child] tmp; child parent; parent (child - 1) / 2; } }插入的完整步骤把上面的思路拆开来看堆的插入其实只有三步每一步都对应着代码里的一段逻辑检查容量先比较_size与_capacity如果两者相等说明数组已经装满了必须先扩容否则下一步写入就会越界。尾插元素把新元素放到数组的最后一个位置也就是下标_size处然后把_size加一。此时数组的物理结构是完整的但堆的性质可能被破坏。向上调整从新插入的结点出发不断与它的双亲结点比较不满足堆序就交换直到满足堆序或者已经到达根结点为止。向上调整算法AdjustUp向上调整是堆插入的核心它的前提是除了新插入的这个结点之外其余部分已经满足堆的性质。因此只需要沿着从新结点到根结点的这一条路径修复即可不需要动其它分支。以小根堆为例调整规则是如果孩子结点的值小于双亲结点的值就交换两者否则说明已经满足小根堆的性质直接结束循环。//小根堆的向上调整算法 void AdjustUp(HPDataType* a, int child) { int parent (child - 1) / 2; while (child 0) { if (a[child] a[parent]) { break;//已经满足小根堆性质不需要再调整 } HPDataType tmp a[parent]; a[parent] a[child]; a[child] tmp; child parent; parent (child - 1) / 2; } }如果写的是大根堆只需要把判断条件反过来当a[child] a[parent]时结束循环其余逻辑完全一致。几个容易出错的细节循环条件用child 0当child为 0 时说明已经走到根结点根结点没有双亲必须停止否则(0 - 1) / 2在整数除法下会得到 0造成自己和自己比较的死循环。双亲下标用(child - 1) / 2这是顺序存储结构下由孩子下标反推双亲下标的公式与前面二叉树顺序存储中讲的2i1、2i2正好互为逆运算。先判断再交换一旦发现孩子已经不小于双亲就说明整条路径都满足堆序可以提前break不必一路比较到根。扩容只影响数组realloc之后一定要把返回值赋回hp-_a并同步更新_capacity否则下次插入时容量判断会出错。插入后_size必须自增新元素写入_a[_size]之后立刻_size这样_size - 1才是新元素的下标也是向上调整的起点。复杂度分析向上调整最多沿着树的高度走一遍而具有 n 个结点的完全二叉树高度为 ⌊log₂n⌋ 1所以单次插入的时间复杂度是O(logN)。空间上只用了几个临时变量额外空间复杂度为O(1)。需要注意的是这里的 O(logN) 是最坏情况如果新插入的元素恰好不需要移动比如插入的值比双亲大在小根堆中直接满足条件那么一次比较就能结束实际开销会小很多。插入过程示例假设当前小根堆的数组为[10, 15, 30, 40, 50, 100]现在插入元素20尾插后数组变为[10, 15, 30, 40, 50, 100, 20]新元素下标为 6。下标 6 的双亲是(6 - 1) / 2 2值为 30因为 20 30交换数组变为[10, 15, 20, 40, 50, 100, 30]。此时child 2双亲是(2 - 1) / 2 0值为 10因为 20 10满足小根堆性质结束调整。最终数组为[10, 15, 20, 40, 50, 100, 30]堆序依然成立整个过程只比较了两次。与向下调整的区别对比项向上调整插入用向下调整删除堆顶用起点新插入的叶子结点根结点或某个需要下沉的结点方向由孩子向双亲自下而上由双亲向孩子自上而下比较对象只与唯一的双亲比较需要与左右孩子中更合适的那个比较时间复杂度O(logN)O(logN)理解了向上调整后面学习堆的删除HeapPop时向下调整的思路就可以对照着来记一个是从底部往上修一个是从顶部往下修。堆的删除1.在叶子节点进行删除数据又没有什么价值堆的删除是在堆顶进行的删除后使用向下调整算法让他继续保持原来的性质于此同时还可以得到数值的大小。2.删除堆顶元素不用向前挪动覆盖的原则是因为他的效率太低了时间复杂度是O(n);会破坏堆的结构将他重新化成堆结构的成本很大。如何删除将堆顶元素与最后一个叶子结点进行交换然后直接删除叶子节点之后通过向下调度算法把堆变成小根堆或者是大根堆。依图所示反复进行实现向下调度算法//堆的删除HeapPop删除堆顶元素并保持堆的性质 void HeapPop(Heap* hp) { assert(hp); //检查堆结构指针是否为空 assert(hp-_a); //检查底层数组是否已经申请 //1.交换堆顶元素与最后一个叶子结点 HPDataType tmp hp-_a[0]; hp-_a[0] hp-_a[hp-_size - 1]; hp-_a[hp-_size - 1] tmp; //2.删除最后一个叶子结点也就是原来的堆顶元素 hp-_size--; //3.从新的堆顶开始向下调整恢复堆的性质 int parent 0; //向下调整从根结点开始 int child parent * 2 1; //左孩子下标2i1 while (child hp-_size) { //孩子下标越界说明已经到叶子结点调整结束 //选出左右孩子中较小的那个小根堆 if (child 1 hp-_size hp-_a[child 1] hp-_a[child]) { child; //右孩子更小让child指向右孩子 } //如果双亲已经小于等于较小的孩子说明满足小根堆性质不需要再调整 if (hp-_a[parent] hp-_a[child]) { break; } //交换双亲结点和较小的孩子结点 HPDataType a hp-_a[parent]; hp-_a[parent] hp-_a[child]; hp-_a[child] a; //继续向下走一层 parent child; child parent * 2 1; } }
树基本概念树的定义树是 nn ≥ 0个结点的有限集。当 n 0 时称为空树当 n 0 时称为非空树任意一棵非空树都满足以下条件1.有且仅有一个根结点。2. 当 n 1 时其余结点可分为 mm 0个互不相交的有限集其中每一个集合本身又是一棵树称为子树。树的根结点没有前驱结点除根结点以外的所有结点有且只有一个前驱结点而树中的所有结点可以有多个后继结点。树是一种递归定义的数据结构。基本术语结点间的关系描述类似于人类的亲缘关系1.祖先从根结点到该结点所经分支的所有的结点都是该结点的祖先。2. 子孙以某一结点为根的子树中任意结点都是该结点的子孙。3.孩子/双亲结点所有子树的根结点称为该结点的孩子对应的该结点是孩子的双亲。4.兄弟同一个双亲结点的孩子之前的关系。5.堂兄弟双亲在同一个层的结点是堂兄弟。结点与树之间的属性描述1.度树中一个结点的孩子结点是该结点的度树中结点最大的度数是树的度。2.叶子结点/终端结点度为0结点。3.分支结点/非终端结点度不为0的结点。4.结点的层次从根开始定义根结点是第一层以此往下推5.树的高数/深度树中结点的最大层数称为树的深度/高度。6.有序树和无序树有序树树中的结点按从左到右的顺序结点之间不会随意的调换。无序树则反之需要保证父子之间关系保持不变。7.路径树中的两个结点之间的路径是又这两个结点所经过的结点的序列构成的路径的长度为序列结点个数长度结点树8.边表示双亲和孩子之间的链接关系。一般在图中使用。性质1.树中的结点数所有结点数的度数1根结点数/所有边结点数12.m叉树中第 i 层上至多有m^i−1个结点 i≥ 1m叉树这个树中每一个结点最多有m个孩子至少有0个孩子。3.解释高度为h的m叉树的第h层的每一个分支的叶子结点就是m个这时就为结点树最多的时候所以可以得出第h层的结点数m^k-1假设层数是i则第i层的结点数是m^i-1。当计算从第一层到第i层时是使用等比数列求和公式。二叉树定义二叉树是一个有序树每个结点最多两个孩子最少一个也没有孩子还有左右之分左边的叫左子树右边的叫右子树。二叉树也是一个递归定义的数据结构。特殊的二叉树满二叉树满二叉树一个高度为h的二叉树每层结点树都达到最满合计有2^h -1个结点的二叉树叫满二叉树。满二叉树的叶子结点在最后一层且分支结点的度为均为2。满二叉树是当前⾼度下二叉树结点数的最大的形态。完全二叉树1.高度为h的二叉树前h-1 层都是结点已经到达了最大但是第h层不一定是满的但是满足从左到右结点都是连续的。2.完美二叉树是完全二叉树的特殊情况。3.左边的值表示的是第h层的结点只有一个右边的值表示是完美二叉树4.完全二叉树的叶子一定只出现在树的倒数第一二层并且度为1的结点只有一个其他的结点的度是2或者是0。搜索二叉树与中序遍历有关(左根右)又叫排序二叉树左子树上的值根结点的值右结点的值性质1.在二叉树的第i层之上组最多的结点有 2^(i-1)个。2.高度为h的二叉树至多有2^h -1(h1)3.对任意的二叉树如果度为0结点数是N0度为2的结点树为N2,则N0N21。解释设度为1的结点数是N1.树的结点 度数1 N0N12*N21 结点数 N0N1N2结点是一个一个的所以的树的结点是直接相加而度则是结点下面的所以在度数相加的时算的是结点下面的度把上面的结点没有算进去。4.具有n个结点的完全二叉树的高度为⌊logn⌋ 1二叉树存储结构二叉树可以使用顺序存储结构也可以是链式存储结构。1.顺序存储结构将二叉树每层的结点的元素从右到左从上到下依次存到数组中空结点也要存储在数组中用特殊的元素进行标记这个特殊元素一定是二叉树中没有的。非完全二叉树使用顺序存储会存在一定空间浪费的行为空的结点越多就越浪费。可以使用链式存储的方式。一般l每层结点存储在数组中都是从0开始的有些地方是从0开始的。是0作为开始的 假设x结点的存储位置的下标是i那么x结点的双亲结点的存储位置就是i-1/ 2。x的左孩子结点存储位置的下标是2i1右孩子存储位置的下标是2i2。堆定义小根堆根结点中的值是最小的双亲结点小于或等于孩子结点兄弟之间没有大小之分。大根堆根结点的值最大双亲大于或者等于孩子兄弟之间无大小。两种存放数据的方式可以快速的找到最大值和最小值。堆的插入HeapPush思路将数据插入到最后的位置插入前需要判断一下capacity与size的大小是否是相等的相等说明空间已经满了或者说这里没有空间所以这里需要扩容。在进行扩容时需要注意的是这里是对这个数组进行扩容而不是对这个数据结构结构进行扩容。assert(hp); if (hp-_size hp-_capacity) { int newcapacity hp-_capacity 0 ? 4 : hp-_capacity * 2;//需要扩容到好多空间数 HPDataType* tmp (HPDataType*)realloc(hp-_a, sizeof(HPDataType) * newcapacity);//这里正式开始扩容 if (tmp NULL) { printf(realloc fail\n); exit(0); } hp-_a tmp; hp-_capacity newcapacity; }向上调整算法将插入的结点的值与双亲结点进行比较然后根据大小进行调整。时间复制度O(lgN)然后开始插入数据插入的结点与双亲结点进行比较这里以小根堆为例子注意void HeapPush(Heap* hp, HPDataType x) { assert(hp); if (hp-_size hp-_capacity) { int newcapacity hp-_capacity 0 ? 4 : hp-_capacity * 2;//需要扩容到好多空间数 HPDataType* tmp (HPDataType*)realloc(hp-_a, sizeof(HPDataType) * newcapacity);//这里正式开始扩容 if (tmp NULL) { printf(realloc fail\n); exit(-1); } hp-_a tmp; hp-_capacity newcapacity; } hp-_a[hp-_size] x; hp-_size; //小根堆 int child hp-_size - 1; int parent (hp-_size - 1 - 1) / 2; while (child) { if (hp-_a[child] hp-_a[parent]) { break; } HPDataType tmp hp-_a[parent]; hp-_a[parent] hp-_a[child]; hp-_a[child] tmp; child parent; parent (child - 1) / 2; } }插入的完整步骤把上面的思路拆开来看堆的插入其实只有三步每一步都对应着代码里的一段逻辑检查容量先比较_size与_capacity如果两者相等说明数组已经装满了必须先扩容否则下一步写入就会越界。尾插元素把新元素放到数组的最后一个位置也就是下标_size处然后把_size加一。此时数组的物理结构是完整的但堆的性质可能被破坏。向上调整从新插入的结点出发不断与它的双亲结点比较不满足堆序就交换直到满足堆序或者已经到达根结点为止。向上调整算法AdjustUp向上调整是堆插入的核心它的前提是除了新插入的这个结点之外其余部分已经满足堆的性质。因此只需要沿着从新结点到根结点的这一条路径修复即可不需要动其它分支。以小根堆为例调整规则是如果孩子结点的值小于双亲结点的值就交换两者否则说明已经满足小根堆的性质直接结束循环。//小根堆的向上调整算法 void AdjustUp(HPDataType* a, int child) { int parent (child - 1) / 2; while (child 0) { if (a[child] a[parent]) { break;//已经满足小根堆性质不需要再调整 } HPDataType tmp a[parent]; a[parent] a[child]; a[child] tmp; child parent; parent (child - 1) / 2; } }如果写的是大根堆只需要把判断条件反过来当a[child] a[parent]时结束循环其余逻辑完全一致。几个容易出错的细节循环条件用child 0当child为 0 时说明已经走到根结点根结点没有双亲必须停止否则(0 - 1) / 2在整数除法下会得到 0造成自己和自己比较的死循环。双亲下标用(child - 1) / 2这是顺序存储结构下由孩子下标反推双亲下标的公式与前面二叉树顺序存储中讲的2i1、2i2正好互为逆运算。先判断再交换一旦发现孩子已经不小于双亲就说明整条路径都满足堆序可以提前break不必一路比较到根。扩容只影响数组realloc之后一定要把返回值赋回hp-_a并同步更新_capacity否则下次插入时容量判断会出错。插入后_size必须自增新元素写入_a[_size]之后立刻_size这样_size - 1才是新元素的下标也是向上调整的起点。复杂度分析向上调整最多沿着树的高度走一遍而具有 n 个结点的完全二叉树高度为 ⌊log₂n⌋ 1所以单次插入的时间复杂度是O(logN)。空间上只用了几个临时变量额外空间复杂度为O(1)。需要注意的是这里的 O(logN) 是最坏情况如果新插入的元素恰好不需要移动比如插入的值比双亲大在小根堆中直接满足条件那么一次比较就能结束实际开销会小很多。插入过程示例假设当前小根堆的数组为[10, 15, 30, 40, 50, 100]现在插入元素20尾插后数组变为[10, 15, 30, 40, 50, 100, 20]新元素下标为 6。下标 6 的双亲是(6 - 1) / 2 2值为 30因为 20 30交换数组变为[10, 15, 20, 40, 50, 100, 30]。此时child 2双亲是(2 - 1) / 2 0值为 10因为 20 10满足小根堆性质结束调整。最终数组为[10, 15, 20, 40, 50, 100, 30]堆序依然成立整个过程只比较了两次。与向下调整的区别对比项向上调整插入用向下调整删除堆顶用起点新插入的叶子结点根结点或某个需要下沉的结点方向由孩子向双亲自下而上由双亲向孩子自上而下比较对象只与唯一的双亲比较需要与左右孩子中更合适的那个比较时间复杂度O(logN)O(logN)理解了向上调整后面学习堆的删除HeapPop时向下调整的思路就可以对照着来记一个是从底部往上修一个是从顶部往下修。堆的删除1.在叶子节点进行删除数据又没有什么价值堆的删除是在堆顶进行的删除后使用向下调整算法让他继续保持原来的性质于此同时还可以得到数值的大小。2.删除堆顶元素不用向前挪动覆盖的原则是因为他的效率太低了时间复杂度是O(n);会破坏堆的结构将他重新化成堆结构的成本很大。如何删除将堆顶元素与最后一个叶子结点进行交换然后直接删除叶子节点之后通过向下调度算法把堆变成小根堆或者是大根堆。依图所示反复进行实现向下调度算法//堆的删除HeapPop删除堆顶元素并保持堆的性质 void HeapPop(Heap* hp) { assert(hp); //检查堆结构指针是否为空 assert(hp-_a); //检查底层数组是否已经申请 //1.交换堆顶元素与最后一个叶子结点 HPDataType tmp hp-_a[0]; hp-_a[0] hp-_a[hp-_size - 1]; hp-_a[hp-_size - 1] tmp; //2.删除最后一个叶子结点也就是原来的堆顶元素 hp-_size--; //3.从新的堆顶开始向下调整恢复堆的性质 int parent 0; //向下调整从根结点开始 int child parent * 2 1; //左孩子下标2i1 while (child hp-_size) { //孩子下标越界说明已经到叶子结点调整结束 //选出左右孩子中较小的那个小根堆 if (child 1 hp-_size hp-_a[child 1] hp-_a[child]) { child; //右孩子更小让child指向右孩子 } //如果双亲已经小于等于较小的孩子说明满足小根堆性质不需要再调整 if (hp-_a[parent] hp-_a[child]) { break; } //交换双亲结点和较小的孩子结点 HPDataType a hp-_a[parent]; hp-_a[parent] hp-_a[child]; hp-_a[child] a; //继续向下走一层 parent child; child parent * 2 1; } }
