)
二叉树一.二叉树的存储结构-顺序存储堆堆的基本操作1.堆的插入2.堆的删除建堆向上调整建小堆向下调整建小堆堆排序二.二叉树的存储结构-链式存储二叉树前中后序遍历前序遍历中序遍历后序遍历层序遍历一.二叉树的存储结构-顺序存储如上图当我们知道任意一个结点i(i0)的下标时候那么就可以利用下标得到它的双亲下标为(i-1)/2当我们知道一个结点i(i0)的下标的时候,我们可以求出它的左孩子下标2*i1, 右孩子下标2*i2。堆堆可以分为大堆和小堆大堆指的是每一个根结点都会比它的孩子值大如下小堆则相反每个根都要小于或者等于它的孩子结点如下堆不一定有序但有序的一定是堆。堆的基本操作#pragmaonce#includestdio.h#includestdlib.h#includestdbool.h#includeassert.htypedefintDataType;typedefstructHeap{DataType*arr;intsize;intcapacity;}Heap;//初始化voidHeapInit(Heap*hp);//获取堆顶元素DataTypeHeapTop(Heap*hp);//堆的销毁voidHeapDestroy(Heap*hp);//判空boolHeapEmpty(Heap*hp);//获取堆个数intHeapSize(Heap*hp);//堆的插入voidHeapPush(Heap*hp,DataType x);//向上调整voidAdjustUp(DataType*arr,intchild);//向下调整voidAdjustDown(DataType*arr,intn,intparent);//删除堆顶voidHeapPop(Heap*hp);1.堆的插入当我们在插入一个数据的时候假如此时的堆是小堆小堆的堆顶比插入的值还要大那么此时就不是一个小堆我们要进行调整用插入的这个值从下往上依次比较然后交换最后成为一个小堆。注意如果需要向上调整那么受影响的只有插入值的双亲和祖先其余的都不会受任何影响为什么由于这是一个小堆遵循着孩子结点大于双亲结点的此时如果插入的值比双亲还要小那么受影响的只有双亲兄弟结点一定比插入的结点大所以不受影响由此可以推出插入值只会影响它对应的双亲和祖先。//堆插入voidHeapPush(Heap*hp,DataType x){assert(hp);if(hp-capacityhp-size){DataType*tmp(DataType*)realloc(hp-arr,sizeof(DataType)*hp-capacity*2);if(tmpNULL){perror(tmp);}hp-arrtmp;hp-capacity*2;}hp-arr[hp-size]x;AdjustUp(hp-arr,hp-size-1);}先把插入的数存放在末尾此时这个数一定是孩子结点那么我们需要利用孩子结点的下标来找到这个孩子的双亲以及祖先所以向上调整的参数有对应的空间以及孩子结点的下标。//向上调整voidAdjustUp(DataType*arr,intchild){assert(arr);intparent(child-1)/2;while(child0){if(arr[child]arr[parent])// 小堆 大堆{Swap(arr[child],arr[parent]);childparent;parent(child-1)/2;}else{break;}}}向上调整中小堆利用孩子结点找到双亲结点进行比较如果孩子结点双亲结点就进行交换然后再重复找双亲操作向上找如果遇到双亲结点值孩子结点的值时候就不需要调整了就已经调整好了或者当孩子结点等于0的时候也表示调整好了。2.堆的删除堆的删除是删除堆的顶部删除后必须依旧保持对应的 小/大 堆那么该如何进行操作呢以小堆举例将首尾进行互换就可以做到删除但现在就不符合小堆的规定那么就要进行向下调整操作通过孩子进行比较找到两个孩子中较小的那个进行互换然后再重复找孩子过程当孩子结点个下标大于给定的个数的时候就说明调整完毕或者遇到一个比它大的孩子那么此时就不必进行互换向下调整完毕。//删除堆顶voidHeapPop(Heap*hp){assert(hp);assert(!HeapEmpty(hp));Swap(hp-arr[0],hp-arr[hp-size-1]);hp-size--;AdjustDown(hp-arr,hp-size,0);}需要给定个数防止越界再把根结点作为参数去找孩子结点。//向下调整voidAdjustDown(DataType*arr,intn,intparent){assert(arr);intchild2*parent1;while(childn){if(child1narr[child]arr[child1])//先去找兄弟中最小那个{child;}if(arr[child]arr[parent]){Swap(arr[child],arr[parent]);parentchild;child2*parent1;}else{break;}}}先去寻找这个双亲结点的左孩子2*i1,再去找右孩子前提右孩子也不能越界必须在这个数组的个数内此时比较两个孩子较小的那个并和双亲结点进行比较如果结点孩子结点小于双亲结点就互换否则就停止调整。建堆有些时候我们需要直接在一个数组里面创建大堆/小堆操作不需要额外到一个数组里面那么此时我们就需要建堆拿建小堆进行举例。向上调整建小堆首先我们把下标为0的数看成一个堆拿下标为1的数看成一个孩子结点进行向上调整比较这两个数当孩子结点小于这个下标为0的数就互换直到孩子结点下标为0或者孩子结点大于双亲结点结束。然后把下标为2的数当作孩子进行插入进行向上调整比较是否符合调整的条件如图所示然后把下标为3的数作为孩子结点插入然后进行向上调整操作…等等最后就会得到一个完整的小堆。代码实现intarr[]{4,6,1,8,9,7,3};for(inti1;i6;i){AdjustUp(arr,i);}向下调整建小堆这是一棵二叉树那么我们向下建堆该怎么建呢我们可以先对末尾下标对应的分支树进行向下调调整然后再调整另一棵分支树最后把整棵树给调整即可。代码实现intarr[]{4,6,1,8,9,7,3};intsizesizeof(arr)/sizeof(arr[0]);for(inti((size-1)-1)/2;i0;i--){AdjustDown(arr,size,i);}堆排序堆本质就是快速筛选出一棵完全二叉树的最大/最小的数删除堆顶后再利用堆的特点快速找到次要大/小的数那么我们就可以利用堆的特点进行排序。如下图这是一个数组当我们需要给这个数组进行升序排序的时候那么我们应该建大堆还是小堆呢答建立大堆先利用大堆的性质下标为0一定是那个最大的数那么就可以把下标为0和下标为5的数进行互换此时最大的数就已经来到了末尾那么由于堆顶现在并不是最大的,就需要向下调整调整的范围就在0-4的范围内找到第二大的数再重复之前步骤即可voidAdjustDown(int*arr,intsize,intparent){intchild2*parent1;//找到左孩子;while(childn){if(child1narr[child]arr[child1];//child;//找到这两个孩子中哪个较大且不能越界if(arr[child]arr[parent]{Swap(arr[child],arr[parent]);parentchild;child2*parent1;}else{break;}}}voidheapsort(int*arr,intsize){//先进行向下调整,找到for(inti((size-1)-1)/2;i0;i--)//找到最后一个双亲结点{AdjustDown(arr,size,i);}while(size1)//当个数只有一个的时候就不用排序了{Swap(arr[0],arr[size-1]);//将下标为0和末尾的下标值交换size--;//交换完后末尾就不管了接着找前size-1个AdjustDown(arr,size,0)//再从size-1个进行调整并找到次要大的数放在下标为0处}//走出来就表明已经排好序了。}intmain(){intarr[]{9,4,2,1,5,3};heapsort(arr,6);}总结先确定是升序还是降序升序建大堆降序建小堆此时的最值一定在堆顶将堆顶的值和size-1的下标值进行互换再去把剩下的size-1个数进行建堆然后在去和size-1下标的值进行互换。二.二叉树的存储结构-链式存储二叉树前中后序遍历前序遍历指访问顺序是先根节点左子树右子树。由上图前序遍历的顺序就是a b d NULL NULL e NULL NULL c NULL f NULL NULL-a b d e c f (省去NULL)voidProTree(BTNode*root){if(rootNULL)return;printf(%c ,root-val);ProTree(root-left);ProTree(root-right);}中序遍历指访问顺序为左子树根结点右子树。由上图NULL d NULL b NULL e NULL a NULL c NULL f NULL-d b e a c fvoidProTree(BTNode*root){if(rootNULL)return;ProTree(root-left);printf(%c ,root-val);ProTree(root-right);}后序遍历指访问顺序为左子树右子树根节点由上图NULL NULL d NULL NULL e b NULL NULL NULL f c a-d e b f c avoidProTree(BTNode*root){if(rootNULL)return;ProTree(root-left);ProTree(root-right);printf(%c ,root-val);}层序遍历层序遍历指让每一层从左到右依次打印出来实现思路就是利用队列先把每一个根存放进去并取出根同时再把根的左右孩子结点给存放进去如果左右孩子是空就不能存放进去。voidlevelorder1(BTNode*root){BTNode*arr[1024];intfront0;intrear0;if(root!NULL)arr[rear]root;//先把根结点存放进去while(front!rear){BtNode*frontNodearr[front];front--;//取出就表示这个数就没在了printf(%c ,frontNode-val);//取出并打印if(frontNode-left)//判断左结点是否为NULLarr[rear]frontNode-left;if(frontNode-right)arr[rear]frontNode-right;}printf(\n);
二叉树一.二叉树的存储结构-顺序存储堆堆的基本操作1.堆的插入2.堆的删除建堆向上调整建小堆向下调整建小堆堆排序二.二叉树的存储结构-链式存储二叉树前中后序遍历前序遍历中序遍历后序遍历层序遍历一.二叉树的存储结构-顺序存储如上图当我们知道任意一个结点i(i0)的下标时候那么就可以利用下标得到它的双亲下标为(i-1)/2当我们知道一个结点i(i0)的下标的时候,我们可以求出它的左孩子下标2*i1, 右孩子下标2*i2。堆堆可以分为大堆和小堆大堆指的是每一个根结点都会比它的孩子值大如下小堆则相反每个根都要小于或者等于它的孩子结点如下堆不一定有序但有序的一定是堆。堆的基本操作#pragmaonce#includestdio.h#includestdlib.h#includestdbool.h#includeassert.htypedefintDataType;typedefstructHeap{DataType*arr;intsize;intcapacity;}Heap;//初始化voidHeapInit(Heap*hp);//获取堆顶元素DataTypeHeapTop(Heap*hp);//堆的销毁voidHeapDestroy(Heap*hp);//判空boolHeapEmpty(Heap*hp);//获取堆个数intHeapSize(Heap*hp);//堆的插入voidHeapPush(Heap*hp,DataType x);//向上调整voidAdjustUp(DataType*arr,intchild);//向下调整voidAdjustDown(DataType*arr,intn,intparent);//删除堆顶voidHeapPop(Heap*hp);1.堆的插入当我们在插入一个数据的时候假如此时的堆是小堆小堆的堆顶比插入的值还要大那么此时就不是一个小堆我们要进行调整用插入的这个值从下往上依次比较然后交换最后成为一个小堆。注意如果需要向上调整那么受影响的只有插入值的双亲和祖先其余的都不会受任何影响为什么由于这是一个小堆遵循着孩子结点大于双亲结点的此时如果插入的值比双亲还要小那么受影响的只有双亲兄弟结点一定比插入的结点大所以不受影响由此可以推出插入值只会影响它对应的双亲和祖先。//堆插入voidHeapPush(Heap*hp,DataType x){assert(hp);if(hp-capacityhp-size){DataType*tmp(DataType*)realloc(hp-arr,sizeof(DataType)*hp-capacity*2);if(tmpNULL){perror(tmp);}hp-arrtmp;hp-capacity*2;}hp-arr[hp-size]x;AdjustUp(hp-arr,hp-size-1);}先把插入的数存放在末尾此时这个数一定是孩子结点那么我们需要利用孩子结点的下标来找到这个孩子的双亲以及祖先所以向上调整的参数有对应的空间以及孩子结点的下标。//向上调整voidAdjustUp(DataType*arr,intchild){assert(arr);intparent(child-1)/2;while(child0){if(arr[child]arr[parent])// 小堆 大堆{Swap(arr[child],arr[parent]);childparent;parent(child-1)/2;}else{break;}}}向上调整中小堆利用孩子结点找到双亲结点进行比较如果孩子结点双亲结点就进行交换然后再重复找双亲操作向上找如果遇到双亲结点值孩子结点的值时候就不需要调整了就已经调整好了或者当孩子结点等于0的时候也表示调整好了。2.堆的删除堆的删除是删除堆的顶部删除后必须依旧保持对应的 小/大 堆那么该如何进行操作呢以小堆举例将首尾进行互换就可以做到删除但现在就不符合小堆的规定那么就要进行向下调整操作通过孩子进行比较找到两个孩子中较小的那个进行互换然后再重复找孩子过程当孩子结点个下标大于给定的个数的时候就说明调整完毕或者遇到一个比它大的孩子那么此时就不必进行互换向下调整完毕。//删除堆顶voidHeapPop(Heap*hp){assert(hp);assert(!HeapEmpty(hp));Swap(hp-arr[0],hp-arr[hp-size-1]);hp-size--;AdjustDown(hp-arr,hp-size,0);}需要给定个数防止越界再把根结点作为参数去找孩子结点。//向下调整voidAdjustDown(DataType*arr,intn,intparent){assert(arr);intchild2*parent1;while(childn){if(child1narr[child]arr[child1])//先去找兄弟中最小那个{child;}if(arr[child]arr[parent]){Swap(arr[child],arr[parent]);parentchild;child2*parent1;}else{break;}}}先去寻找这个双亲结点的左孩子2*i1,再去找右孩子前提右孩子也不能越界必须在这个数组的个数内此时比较两个孩子较小的那个并和双亲结点进行比较如果结点孩子结点小于双亲结点就互换否则就停止调整。建堆有些时候我们需要直接在一个数组里面创建大堆/小堆操作不需要额外到一个数组里面那么此时我们就需要建堆拿建小堆进行举例。向上调整建小堆首先我们把下标为0的数看成一个堆拿下标为1的数看成一个孩子结点进行向上调整比较这两个数当孩子结点小于这个下标为0的数就互换直到孩子结点下标为0或者孩子结点大于双亲结点结束。然后把下标为2的数当作孩子进行插入进行向上调整比较是否符合调整的条件如图所示然后把下标为3的数作为孩子结点插入然后进行向上调整操作…等等最后就会得到一个完整的小堆。代码实现intarr[]{4,6,1,8,9,7,3};for(inti1;i6;i){AdjustUp(arr,i);}向下调整建小堆这是一棵二叉树那么我们向下建堆该怎么建呢我们可以先对末尾下标对应的分支树进行向下调调整然后再调整另一棵分支树最后把整棵树给调整即可。代码实现intarr[]{4,6,1,8,9,7,3};intsizesizeof(arr)/sizeof(arr[0]);for(inti((size-1)-1)/2;i0;i--){AdjustDown(arr,size,i);}堆排序堆本质就是快速筛选出一棵完全二叉树的最大/最小的数删除堆顶后再利用堆的特点快速找到次要大/小的数那么我们就可以利用堆的特点进行排序。如下图这是一个数组当我们需要给这个数组进行升序排序的时候那么我们应该建大堆还是小堆呢答建立大堆先利用大堆的性质下标为0一定是那个最大的数那么就可以把下标为0和下标为5的数进行互换此时最大的数就已经来到了末尾那么由于堆顶现在并不是最大的,就需要向下调整调整的范围就在0-4的范围内找到第二大的数再重复之前步骤即可voidAdjustDown(int*arr,intsize,intparent){intchild2*parent1;//找到左孩子;while(childn){if(child1narr[child]arr[child1];//child;//找到这两个孩子中哪个较大且不能越界if(arr[child]arr[parent]{Swap(arr[child],arr[parent]);parentchild;child2*parent1;}else{break;}}}voidheapsort(int*arr,intsize){//先进行向下调整,找到for(inti((size-1)-1)/2;i0;i--)//找到最后一个双亲结点{AdjustDown(arr,size,i);}while(size1)//当个数只有一个的时候就不用排序了{Swap(arr[0],arr[size-1]);//将下标为0和末尾的下标值交换size--;//交换完后末尾就不管了接着找前size-1个AdjustDown(arr,size,0)//再从size-1个进行调整并找到次要大的数放在下标为0处}//走出来就表明已经排好序了。}intmain(){intarr[]{9,4,2,1,5,3};heapsort(arr,6);}总结先确定是升序还是降序升序建大堆降序建小堆此时的最值一定在堆顶将堆顶的值和size-1的下标值进行互换再去把剩下的size-1个数进行建堆然后在去和size-1下标的值进行互换。二.二叉树的存储结构-链式存储二叉树前中后序遍历前序遍历指访问顺序是先根节点左子树右子树。由上图前序遍历的顺序就是a b d NULL NULL e NULL NULL c NULL f NULL NULL-a b d e c f (省去NULL)voidProTree(BTNode*root){if(rootNULL)return;printf(%c ,root-val);ProTree(root-left);ProTree(root-right);}中序遍历指访问顺序为左子树根结点右子树。由上图NULL d NULL b NULL e NULL a NULL c NULL f NULL-d b e a c fvoidProTree(BTNode*root){if(rootNULL)return;ProTree(root-left);printf(%c ,root-val);ProTree(root-right);}后序遍历指访问顺序为左子树右子树根节点由上图NULL NULL d NULL NULL e b NULL NULL NULL f c a-d e b f c avoidProTree(BTNode*root){if(rootNULL)return;ProTree(root-left);ProTree(root-right);printf(%c ,root-val);}层序遍历层序遍历指让每一层从左到右依次打印出来实现思路就是利用队列先把每一个根存放进去并取出根同时再把根的左右孩子结点给存放进去如果左右孩子是空就不能存放进去。voidlevelorder1(BTNode*root){BTNode*arr[1024];intfront0;intrear0;if(root!NULL)arr[rear]root;//先把根结点存放进去while(front!rear){BtNode*frontNodearr[front];front--;//取出就表示这个数就没在了printf(%c ,frontNode-val);//取出并打印if(frontNode-left)//判断左结点是否为NULLarr[rear]frontNode-left;if(frontNode-right)arr[rear]frontNode-right;}printf(\n);
