男女做暖暖视频网站,vue做网站cms,wordpress玻璃质感主题,wordpress增加中英文切换完全二叉树#xff08;Complete Binary Tree#xff09;是一种特殊的二叉树结构#xff0c;它具有以下特点#xff1a;
所有的叶子节点都集中在树的最后两层#xff1b;最后一层的叶子节点都靠左排列#xff1b;除了最后一层#xff0c;其他层的节点数都达到最大值。
…完全二叉树Complete Binary Tree是一种特殊的二叉树结构它具有以下特点
所有的叶子节点都集中在树的最后两层最后一层的叶子节点都靠左排列除了最后一层其他层的节点数都达到最大值。
满二叉树Full Binary Tree又称为真二叉树是一种特殊的完全二叉树结构它具有以下特点
所有的叶子节点都在同一层每个非叶子节点都有两个子节点所有节点的子节点数都为0或2。
满二叉树是完全二叉树的一种特殊情况每个非叶子节点都有两个子节点而完全二叉树可以有一个或没有一个子节点。
树的定义遍历输入构建一些递归复习求叶子节点数的高度
ABC##DE#G##F###
5 第二次实验——二叉树中序遍历
ABD##FE###CG#H##I##
DBEFAGHCI
第十一周后序中序确定二叉树
树的性质
第二次实验的思考题 一棵非空二叉树若后序遍历与中序遍历的序列相同则该二叉树所有结点均无右孩子。
非空的二叉树一定满足某结点若有左孩子则其中序前驱一定没有右孩子。
二分查找法
二叉搜索树复习
寻找公共祖先
排序算法
第二次实验——快速排序的过程
5 4 5 3 2 1
输出
2 1 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 插入排序还是归并排序
10 3 1 2 8 7 5 9 4 6 0 1 2 3 7 8 5 9 4 6 0
Insertion Sort 1 2 3 5 7 8 9 4 6 0
10 3 1 2 8 7 5 9 4 0 6 1 3 2 8 5 7 4 9 0 6
Merge Sort 1 2 3 8 4 5 7 9 0 6
插入排序冒泡排序选择排序堆排序归并排序
第八周习题——冒泡排序
第九周习题——二路归并排序
归并排序逆序对
第七周——插入排序
结构体排序
第九周习题——成绩排名 第八周习题——小球装箱
排序算法性质
合并排序算法是稳定的排序方法。 直接插入排序在最好的情况下时间复杂度为O(n) 直接插入排序是稳定的 逆序对倍数对
堆的调整构建
调整
void shiftup(int child) {//在末尾插入一个孩子然后就这个孩子一直往上调整这样的话调整路径都满足堆的性质int parent (child - 1) / 2;while (child 0) {if (arr[parent] arr[child]) {break;}else {swap(arr[parent], arr[child]);child parent;//往上调整一步parent (child - 1) / 2;//这里是先调整了孩子指针所以这时候的父母就是父母的父母}}
}
void shiftup(int child) {int parent (child - 1) / 2;while (child 0) {if (arr[parent] arr[child]) { break; }//大顶堆上面大就不调整了else {swap(arr[parent], arr[child]);child parent;parent (child - 1) / 2;}}
}
//向上调整的话就是找到最后一个孩子然后找到它的父母节点孩子对应的父母节点是唯一的所以可以直接比较
//直接比较完后直接交换直到到底
//向下调整的话就是先找到堆顶元素然后由于堆是完全二叉树所以对应两个孩子找到最小的孩子然后调整
//调整后使被调整的孩子作为父母节点找到其左孩子节点
//即向上调整只需要找到一个节点信息即当下节点信息就可以确定父母节点单向比较即可
//而向下调整需要两个节点信息一个是当下节点信息父母节点还要直到它是否有孩子默认为左孩子然后判断一下有没有右孩子
//由此向下递归进行需要两个信息一个父母节点一个孩子节点递归时默认孩子节点为左孩子2*cur1,然后尝试找右孩子
//如果在下次递归时左孩子越界那就说明此时父母节点已是叶子节点到底了无法继续调整。
void shiftdown(int[]arr, int size, int parent) {int child parent * 2 1;while (child size) {if (child 1 size arr[child 1] arr[child]) {child 1;}if (arr[parent] arr[child]) {swap(arr, parent, child);parent child;//由此完成向下移动child parent * 2 1;//孩子与父母指针都向下移动}else {return;}}
}
void shiftdown(int[]arr, int parent) {//父母直接指向要交换的元素int child 2 * parent 1;//孩子指针指向要交换的元素int size arr.length();while (child size) {//只要有这一步就说明当下节点至少存在左孩子if (child 1 size arr[child 1] arr[child]) {child 1;//如果向右一个单位存在就说明当下节点有右孩子找最小的}//确定较小的孩子if (arr[parent] arr[child]) {break;}else {int t arr[parent];parr[parent] arr[child];arr[child] t;parent child;child parent * 2 1;}}
}
如果左孩子存在则childsize,不断进行操作直到左孩子不存在
检测右孩子是否存在找左右孩子中最小的孩子
堆的创建
这个就是先输入输入一个数组输入完后再开始调整从最后一个非叶子结点开始然后不断往上往回走进行向下调整
public static void createHeap(int[] array) {// 找倒数第一个非叶子节点从该节点位置开始往前一直到根节点遇到一个节点应用向下调整for(int root (array.length-2)/2; root 0; root--){shiftDown(array, array.length, root);}
}
插入边插边保持堆 int arr[100];
int siz 0;
void shiftup(int child) {int parent (child - 1) / 2;while (child 0) {if (arr[parent] arr[child]) {break;}else {swap(arr[parent], arr[child]);child parent;parent (child - 1) / 2;}}
}
void insert(int num) {arr[siz] num;shiftup(siz - 1);
} 二叉树指针关系
对于二叉树的孩子双亲指针指引如果是从1开始记录的那么
左孩子结点索引 2 * i 右孩子结点索引 2 * i 1
其中i表示当前结点的索引位置。
当索引从1开始记录时根节点的索引为1其左孩子结点的索引为2而右孩子结点的索引为3。对于任意结点i其左孩子结点的索引位置为2 * i右孩子结点的索引位置为2 * i 1。
如果是从0开始记录的
二叉树以数组形式存储时一般约定根节点的索引位置为0其左孩子结点的索引位置为1右孩子结点的索引位置为2。对于任意结点i其左孩子结点的索引位置为2 * i 1右孩子结点的索引位置为2 * i 2。
堆的一些性质
下标从0开始计数的堆大小为size时其最后一个非叶子结点是(size-2)/2;
最后一个叶子结点的下标为size-1.
由于是下标从0所以对结点i而言其双亲结点下标为(i-1)/2
(如果下标从1开始那么整体往右偏移一位
所以对于下标为size-1的结点它的双亲结点为(size-1-1)/2; 最大堆大顶堆、max-heap从根结点到其它任一结点的路径上的所有结点值是从大到小排列的。 第十二周堆的操作堆的建立
找第k小
