二叉树_堆的实现

1.树树是一种非线性的数据结构是由m(m0)个有限节点组成的有层次关系的结合树的结构中子树之间是不能有交集的否则就是图树是递归定义的。常见树的相关术语⽗结点若⼀个结点含有⼦结点则这个结点称为其⼦结点的⽗结点⼦结点⼀个结点含有的⼦树的根结点称为该结点的⼦结点结点的度⼀个结点有⼏个孩⼦他的度就是多少树的度⼀棵树中最⼤的结点的度称为树的度叶⼦结点度为 0的结点称为叶结点兄弟结点具有相同⽗结点的结点互称为兄弟结点结点的层次从根开始定义起根为第 1层根的⼦结点为第2层以此类推树的⾼度或深度树中结点的最⼤层次树的表示方法对于不规则的普通二叉树通常采用孩子-兄弟表示法(二叉链表)。struct TreeNode { struct Node* child; // 左边开始的第⼀个孩⼦结点 struct Node* brother; // 指向其右边的下⼀个兄弟结点 int data; // 结点中的数据域 };2.二叉树_堆二叉树不存在度大于2的节点且二叉树有左右之分不能颠倒因此二叉树又是有序树何为有序即一个节点最多有两个分支这两个分支被严格定义为左指针和右指针左右不可互换。如图这两棵树是完全不同的树一个是左子树一个是右子树其内存结构与遍历结果都是不一样这就是所谓的有序树。一种特殊的二叉树-满二叉树即每一层的节点个数都达到了最大假设有k层则节点总个数为2的k次方减12.1 完全二叉树假设二叉树层次为k除了第k层外每层节点的个数达到最大节点数第k层节点数不一定达到最大这就是完全二叉树。完全二叉树节点的顺序是从左到右中间不能有空缺满二叉树是一种特殊的完全二叉树。根据满⼆叉树的特点可知1若规定根结点的层数为 1 则⼀棵⾮空⼆叉树的第i层上最多有 2i−1 (2的i次方-1)个结点。2若规定根结点的层数为 1 则深度为 h 的⼆叉树的最⼤结点数是 2h − 1(2的h次方-1)。3若规定根结点的层数为 1 具有 n 个结点的满⼆叉树的深度 h log2 (n 1) ( log以2为底 n1 为对数)。完全二叉树的存储结构包含两类。一类是顺序结构即底层用顺序表实现一般适用完全二叉树因为不完全二叉树就会有空间的浪费在提到完全二叉树的顺序存储不得不提到堆这种特殊的完全二叉树简单理解堆 完全二叉树 最大、最小堆而堆通常用顺序结构而不用链式结构。小堆堆中的某个节点的值总是不小于其父节点。大堆堆中的某个节点的值总是不大于其父节点。对于堆有以下性质对于具有 n 个结点的完全⼆叉树如果按照从上⾄下从左⾄右的数组顺序对所有结点从0 开始编号则对于序号为 i 的结点有1. 若 i0 i 位置结点的双亲序号 (i-1)/2 i0 i 为根结点编号⽆双亲结点2. 若 2i1n 左孩⼦序号 2i1 2i1n 否则⽆左孩⼦3. 若 2i2n 右孩⼦序号 2i2 2i2n 否则⽆右孩⼦另一类是链式结构即用链表来表示数的结构一般由三个部分组成左右指针域数据域。左指针指向左孩子的链结点的存储地址右指针指向右孩子的链结点的存储地址链式结构分为二叉链和三叉链三叉链比如高阶数据结构的红黑树这里简单介绍二叉链。3.堆的实现堆的底层是用数组实现的所以固定结构为typedef int HPDataType; typedef struct Heap { HPDataType* arr; int size;//有效的数据个数 int capacity;//有效的空间大小 }HP;将实现堆用到的自定义函数写在头文件中//默认初始化堆 void HPInit(HP* php); //堆的销毁 void HPDestroy(HP* php); //堆的插⼊ void HPPush(HP* php, HPDataType x); //堆的删除 HPDataType HPTop(HP* php); // 删除堆顶的数据 void HPPop(HP* php); // 判空 bool HPEmpty(HP* php); //求size int HPSize(HP* php); //向上调整算法 void AdjustUp(HPDataType* a, int child); //向下调整算法 void AdjustDown(HPDataType* a, int n, int parent);堆的初始化、销毁其实就是对数组的初始化、销毁void HPInit(HP*php) { assert(php); php-arr NULL; php-capacity php-size 0; } void HPDestroy(HP* php) { assert(php); if(php-arr); free(php-arr); php-arr NULL; php-capacity php-size 0; }堆的插入其实就是顺序表的尾插不过尾插的数据不一定就是比父节点大所以还需要与前面父节点进行比较如果插入的数据更小则需要向上进行交换为此我们设定一个向上调整算法AdjustUpvoid AdjustUp(HPDataType* arr, int child) { int parent (child - 1) / 2; while (child 0) { if (arr[child] arr[parent]) { swap(arr[child], arr[parent]); child parent; parent (child - 1) / 2; } else { break; } } }知道孩子节点找父节点parent (child - 1) / 2如果孩子节点小于父节点则进行交换交换之后让孩子节点走到父节点父节点向上继续走到新的父节点如果发现孩子节点不小于父节点则break停止循环循环的条件是child0不能越界。其中向上调整算法时间复杂度O(n∗ log2n)因为堆是完全⼆叉树⽽满⼆叉树也是完全⼆叉树此处为了简化使⽤满⼆叉树来证明(时间复杂度本 来看的就是近似值多⼏个结点不影响最终结果)证明如下第1层 2^0个结点需要向上移动0层第2层 2^1个结点需要向上移动1层第3层 2^2个结点需要向上移动2层第4层 2^3个结点需要向上移动3层......第h层 2^h−1个结点需要向上移动h-1层则需要移动结点总的移动步数为每层结点个数 * 向上调整次数第⼀层调整次数为0T(h) 2^1 ∗ 1 2^2 ∗ 2 2^3 ∗ 3 .. 2^h−2∗ (h− 2) 2^h−1∗ (h− 1) ①2 ∗T(h) 2^2 ∗ 1 2^3 ∗ 2 2^4 ∗ 3 .. 2^h−1∗ (h− 2) 2^h∗ (h− 1) ②② ⼀ ① 错位相减T(h) −(2^h− 1) 2^h∗ (h− 1) 2^0根据⼆叉树的性质n 2h− 1和hlog2(n 1)F(n) (n 1)(log2(n 1) − 2) 2由此可得向上调整算法建堆时间复杂度为O(n∗ log2n)。写完向上调整算法堆的插入就比较好实现了HPPush//堆的插⼊ void HPPush(HP* php, HPDataType x) { assert(php); if (php-capacity php-size) { int newcapacity php-capacity 0 ? 4 : 2 * php-capacity; HPDataType* tmp (HPDataType*)realloc(php-arr,sizeof(HPDataType)*newcapacity); if (tmp NULL) { perror(realloc fail); exit(1); } php-arr tmp; php-capacity newcapacity; } php-arr[php-size] x; AdjustUp(php-arr,php-size-1); }删除堆数据删的是堆顶的数据但如果直接删堆顶的数据然后让数据整体向前移动一位那么堆的结构就被破坏了想重新变成原来小堆的结构就比较困难了为此我们先将堆顶数据与size-1位置交换然后让size--,这虽然没有破坏堆的结构但此时堆顶数据不一定就是最小这个时候我们就需要向下调整算法AdjustDownvoid AdjustDown(HPDataType* arr, int n, int parent) { //左孩子 int child 2 * parent 1; while (childn) { if (child 1 n arr[child] arr[child 1]) { child; } if (arr[child] arr[parent]) { swap(arr[child], arr[parent]); parent child; child 2 * parent 1; } else { break; } } }向下调整需要先找到孩子节点中较小的那个节点然后向下交换这样才能保证交换上来的节点最小后面实现的逻辑与向上调整算法差不多循环结束的条件是childn而不是parentn因为有时候会有child已经越界了但parent还没有越界此时循环还会继续交换的值是不确定的取决于此时child的值有没有被覆盖child1n是为了防止没有右孩子的情况。第1层 2^0个结点需要向下移动h-1层第2层 2^1个结点需要向下移动h-2层第3层 2^2个结点需要向下移动h-3层第4层 2^3个结点需要向下移动h-4层......第h-1层 2^h−2个结点需要向下移动1层同上证明所以向下调整算法建堆时间复杂度为O(n)。取堆顶数据HPDataType HPTop(HP* php) { assert(php php-size); return php-arr[0]; }判空bool HPEmpty(HP* php) { assert(php); return php-size 0; }4.链式结构实现二叉树三种递归方式二叉树的链式结构实现是一次递归的暴力美学而递归的方式主要分为三类前序遍历(根左右)、中序遍历(左根右)、后序遍历(左右根)。对于上诉二叉树来说如果用前序遍历1 2 4 3中序遍历4 2 1 3后序遍历4 2 3 1如果用代码实现如下//前序遍历 void PreOrder(BTNode* root) { if (root NULL) { return; } printf(%d, root-val); PreOrder(root-left); PreOrder(root-right); } //中序遍历 void InOrder(BTNode* root) { if (root NULL) { return; } InOrder(root-left); printf(%d, root-val); InOrder(root-right); } //后序遍历 void PostOrder(BTNode* root) { if (root NULL) { return; } PostOrder(root-left); PostOrder(root-right); printf(%d, root-val); }在了解三种递归方式后我们来实现一下功能函数// ⼆叉树结点个数 int BinaryTreeSize(BTNode* root); // ⼆叉树叶⼦结点个数 int BinaryTreeLeafSize(BTNode* root); // ⼆叉树第k层结点个数 int BinaryTreeLevelKSize(BTNode* root, int k); //⼆叉树的深度/⾼度 int BinaryTreeDepth(BTNode* root); // ⼆叉树查找值为x的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // ⼆叉树销毁 void BinaryTreeDestory(BTNode** root);求二叉树节点个数int BinaryTreeSize(BTNode* root) { if (root NULL) { return 0; } return 1 BinaryTreeSize(root-left) BinaryTreeSize(root-right); }递归结束条件为root(当前节点为NULL)回归执行剩余代码return 10BinaryTreeSize(root-right)进入BinaryTreeSize内部遇到root NULL回归返回0所以100 1回到上一个函数栈帧继续执下一个代码return 11BinaryTreeSize依此类推。⼆叉树叶⼦结点个数int BinaryTreeLeafSize(BTNode* root) { if (root NULL) { return 0; } if (root-left NULL root-right NULL) { return 1; } return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right); }⼆叉树第k层结点个数int BinaryTreeLevelKSize(BTNode* root, int k) { if (root NULL) { return 0; } if (k 1) { return 1; } return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1); }⼆叉树的深度/⾼度int BinaryTreeDepth(BTNode* root) { if (root NULL) { return 0; } int leftDep BinaryTreeDepth(root-left); int rightDep BinaryTreeDepth(root-right); return leftDep rightDep ? leftDep 1 : rightDep 1; }⼆叉树查找值为x的结点BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root NULL) { return 0; } if (root-val x) { return root; } BTNode* leftfind BinaryTreeFind(root-left,x); if (leftfind) { return leftfind; } BTNode* rightfind BinaryTreeFind(root-right, x); if (rightfind) { return rightfind; } return NULL; }⼆叉树销毁void BinaryTreeDestory(BTNode** root) { if (*root NULL) { return; } BinaryTreeDestory(((*root)-left)); BinaryTreeDestory(((*root)-right)); free(*root); *root NULL; }层序遍历void Levelorder(BTNode* root) { Queue q; QLInit(q); QLPush(q, root); while(!QLEmpty(q)) { BTNode* front QLFront(q); QLPop(q); printf(%d , front-val); if (front-left) { QLPush(q,front-left); } if (front-right) { QLPush(q, front-right); } } QLDestroy(q); }大致思路为:用到队列数据结构改队列存储的数据类型typedef struct BinaryTreeNode* QLDataType;之前存储int整形现在改为存储二叉树结点。将不为空的节点入队列取队头删队头保证每一次取出来的都是最新的队头取一次打印一次循环结束的条件是队列为NULL。判断⼆叉树是否是完全⼆叉树bool BinaryTreeComplete(BTNode* root) { Queue q; QLInit(q); QLPush(q, root); while (!QLEmpty(q)) { BTNode* top QLFront(q); QLPop(q); if (top NULL) { break; } QLPush(q, top-left); QLPush(q, top- right); } while (!QLEmpty(q)) { BTNode* top QLFront(q); QLPop(q); if (top ! NULL) { QLDestroy(q); return false; } } QLDestroy(q); return true; }大致思路与层序遍历类似也需要用到队列不同的是这次我需要将NULL也入队列当我取队头元素取一次删一次保证每次取到的都是最新的队头当取到NULLbreak跳出来第一次循环第二次循环只要我取到了非NULL节点说明该二叉树不是完全二叉树return false。如果两次循环都结束了说明该二叉树为完全二叉树return true。