(三)、分析堆
1.向下调整算法建堆的时间复杂度分析
void AdjustDown(int* a, int size, int parent) { int child = parent * 2 + 1; while (child < size)//思考1：while的结束条件是什么？ { // 假设左孩子小，如果解设错了，更新一下 if (child + 1 < size && a[child + 1] < a[child])//思考2：if中“child + 1 < size”的意义是什么？ { ++child; } if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } }
结论：
向下调整算法时间复杂度为O(logN)
向下调整算法建堆的时间复杂度是多少？O(N)
2.向上调整算法建堆的时间复杂度分析
//小堆 void AdjustUp(HPDataType* a, int child) { assert(a); int parent = (child - 1) / 2; while (child > 0) //思考：请思考while括号内的结束条件是什么？ { //提示选项如下：1.parent>=0 2.child>=0 3.child>0 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (parent - 1) / 2; } else { break; } } }
结论：
向上调整算法的时间复杂度为O(logN)
向上调整算法建堆的时间复杂度为：O(N * log(N))
思考：向上调整算法与向下调整算法同为调整算法，且时间复杂度都为O(logN),为什么向下调整算法建堆的时间复杂度为O(N)，而向上调整算法却到达了O(N*logN)?
答：
说的简单一点，对于单个结点的向上调整/向下调整，都大概最差要调整高度次，也就是差不多是logN，但是对于一整个堆而言，这个堆中如果用向上调整算法，第一行不需要调整，如果用向下调整算法，最后一行不需要调整，而往往在N足够大的情况下，最后一行的结点个数占百分之50左右。
3.堆排序的时间复杂度分析
堆排序有两部分组成，第一步是建堆，第二是首尾交换，尾不视为堆内，对N-1个数据向下调整算法重新成为堆。
在第一步，可以使用向上/向下调整算法建堆，肯定是选择向下调整算法建堆。时间复杂度上面经过分析为O(N)
在第二步，时间复杂度为O(N*logN)
代码如下：
void HeapSort(int* a, int n) { // a数组直接建堆 O(N) for (int i = (n - 1 - 1) / 2; i >= 0; --i) { AdjustDown(a, n, i); } int end = n - 1; while (end > 0)//思考：while的结束条件是什么？ { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); --end; } }
综上，堆排的时间复杂度为O(N*logN)
结论：堆排的时间复杂度为O(N*logN)
(四)、一般的二叉树
上面所说的堆是特殊的二叉树+满足大堆小堆的条件才可以称为堆，下面来简单说一下对于一般二叉树的常规知识点。
每棵树都可以分为根、左子树、右子树，其中左子树又可以分为根、左子树、右子树…二叉树也不例外。
同时，因为一般二叉树放入顺序结构中比较浪费空间，一般选用链式结构来构造一般的二叉树。
1.一般二叉树的遍历
二叉树的遍历可以分为前序遍历、中序遍历、后序遍历。
- 二叉树的前序遍历(根、左子树、右子树)：
前序遍历本质上是深度优先遍历
void PreOrder(Tree* root) { if (root == NULL) { printf("N "); return; } printf("%d ", root->val); PreOrder(root->left); PreOrder(root->right); }
拓展练习题：二叉树的前序遍历LINK
示例代码如下：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ int TreeSize(struct TreeNode* root) { if(root == NULL) { return 0; } return TreeSize(root->left) + TreeSize(root->right) + 1; } void PreOrder(struct TreeNode* root,int* arr,int* pi) { if(root == NULL) return; arr[(*pi)++] = root->val;//思考，这个小括号是否可以省略？ PreOrder(root->left,arr,pi); PreOrder(root->right,arr,pi); } int* preorderTraversal(struct TreeNode* root, int* returnSize) { int n = *returnSize = TreeSize(root); int* arr = (int*)malloc(sizeof(int) * n); int i = 0;//思考：这里为什么要传地址 PreOrder(root,arr,&i); return arr; }
思考1：这个小括号是否可以省略？
不能，语法优先级问题。
思考2：这里为什么要传地址？
使用递归，要改变一个固定空间的i值，要传入地址或者搞一个全局变量。
- 二叉树的中序遍历(左子树、根、右子树)
void InOrder(Tree* root) { if (root == NULL) { printf("N "); return; } InOrder(root->left); printf("%d ", root->val); InOrder(root->right); }
拓展练习题：二叉树的中序遍历LINK
- 二叉树的后序遍历(左子树、右子树、根)
void PostOrder(Tree* root) { if (root == NULL) { printf("N "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->val); }
拓展练习题：二叉树的后序遍历LINK
2.树的节点个数接口
- 思想1：分置思路
int TreeSize(Tree* root) { if (root == NULL) { return 0; } return TreeSize(root->left) + TreeSize(root->left) + 1; }
int TreeSize(Tree* root) { return root == NULL ? 0 :TreeSize(root->left) + TreeSize(root->right) + 1; }
- size统计思路
//思考：如果用size进行统计结点个数，要定义为局部变量/全局变量/全局变量/指针变量？？？ //局部变量，否定，统计结果永远为0/1 //全局变量，可以，需要每次调用需要置为空size //局部静态变量，否定，不能置空操作，多次调用之后会出问题 //指针变量：可以，每次也都需要置空
思考：size统计思路各种处理size方法的利弊。
如果用size进行统计结点个数，要定义为局部变量/全局变量/全局变量/指针变量？？？
//局部变量，否定，统计结果永远为0/1
//全局变量，可以，需要每次调用需要置为空size
//局部静态变量，否定，不能置空操作，多次调用之后会出问题
//指针变量：可以，每次也都需要置空
代码技巧：要想写好递归，需要控制好两个条件，
- 子问题
- 结束条件(返回条件)
对于本接口，那么需要把握好下面两个条件：
- 子问题：一棵树的结点个数 = 左子树结点个数 + 右子树结点个数 + 1
- 结束条件：NULL，返回0
拓展1：实现一棵树叶子结点个数：自己思考，参考代码如下
int TreeLeafSize(Tree* root) { if (root == NULL) { return 0; } if (root->right == NULL && root->left == NULL) { return 1; } return TreeLeafSize(root->left) + TreeLeafSize(root->right); }
拓展2：求树的第K层结点个数，参考代码如下：
int TreeSize_K(Tree* root,int k) { if (root == NULL || k < 1) { return 0; } if (k == 1) { return 1; } return TreeSize_K(root->left, k - 1) + TreeSize_K(root->right, k - 1); }
3.树的高度接口
思路：这里要求树的高度，那么就是对于一个子树的高度就是左子树的高度，右子树的高度取其大的进行返回 +1(这个1是指自己) 。
int TreeHeight(Tree* root) { if (root == NULL) { return 0; } int leftheight = TreeHeight(root->left);//思考：这里为啥不直接返回而是用变量记录的意义。 int rightheight = TreeHeight(root->right); return leftheight > rightheight ? leftheight + 1 : rightheight + 1; }
思考：这里为啥不直接返回而是用变量记录的意义
其意义在于，防止重复调用，这里其实就是一个不断多次重复的问题。
int TreeHeight(Tree* root) { return root == NULL ? 0 : (TreeHeight(root->left) > TreeHeight(root->right) ? >TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1); }
这样第一次多调用一次，那么第二层要多调用2^1 第三层要多调用2^2次 第四层要多调用2^3次…
4.树的查找接口
Tree* TreeFind(Tree* root, int x) { if (root == NULL) { return NULL; } if (root->val == x) { return root; } Tree* left = TreeFind(root->left,x); if (left) { return left; } Tree* right = TreeFind(root->right,x); if (right)//思考，这里为什么要加这个if条件 { return right; } return NULL; }
思考：至于为什么要加上if，防止空指针也被返回，如果没有if可能会提前返回出问题。
就是左子树返回后，会直接返回到上一级函数，没有机会执行右子树了。
拓展练习题：单值二叉树
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isUnivalTree(struct TreeNode* root) { if(root == NULL)//如果走到空结点，直接返回true { return true; } if(root->left && root->val!=root->left->val) { return false; } if(root->right && root->val!=root->right->val) { return false; } return isUnivalTree(root->left) && isUnivalTree(root->right); }
拓展练习题2：对称二叉树LINK
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool _isSymme(struct TreeNode* q,struct TreeNode* p) { if(q == NULL && p == NULL) { return true; } if(q == NULL || p == NULL) { return false; } if(q->val != p->val) { return false; } return _isSymme(q->left,p->right) && _isSymme(q->right,p->left); } bool isSymmetric(struct TreeNode* root) { return _isSymme(root,root); }
拓展练习题：另一颗树的子树LINK
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isSameTree(struct TreeNode* root, struct TreeNode* subRoot) { if(root == NULL && subRoot == NULL) { return true; } if(root == NULL || subRoot == NULL) { return false; } if(root->val != subRoot->val) { return false; } return isSameTree(root->left,subRoot->left) && isSameTree(root->right,subRoot->right); } bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) { if (root == NULL) { return false; } if (root->val == subRoot->val) { if(isSameTree(root, subRoot) == true)//思考：这里if的意义在哪里？ { return true; } } return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot); }
思考：上面if返回的意义在于，要把整个树的每一个结点都比较一遍，防止特殊情况出现。
比如：
5.树的构建接口
Tree* TreeCreat(char* a, int* pi) { if (a[*pi] == '#') { (*pi)++; return NULL; } Tree* root = (Tree*)malloc(sizeof(Tree)); if (root == NULL) { perror("malloc fail"); exit(-1); } root->val = a[(*pi)++]; root->left = TreeCreat(a, pi); root->right = TreeCreat(a, pi); return root; }
test_TreeCreat() { char* a = "abc##de#g##f###"; int i = 0; Tree* root = TreeCreat(a, &i); PreOrder(root); } int main() { //test_heap(); //test_TopK(); //test_HeapSort(); //test_GenBTree(); test_TreeCreat(); return 0; }
6.层序遍历接口
本质上是广度优先遍历
思路：
void TreeLevelOrder(Tree* root) { Queue q; QueueInit(&q); if (root != NULL) { QueuePush(&q,root); } while (!QueueEmpty(&q)) { Tree* front = QueueFront(&q); QueuePop(&q); printf("%d ", front->val); if (root->left != NULL) { QueuePush(&q, root->left); } if (root->right != NULL) { QueuePush(&q, root->right); } } printf("\n"); QueueDestroy(&q); }
7.树的销毁
oid TreeDestroy(Tree* root) { if (root == NULL) { return; } TreeDestroy(root->left); TreeDestroy(root->right); free(root); }
待续。
