接着上次的,这里主要介绍的是堆排序,二叉树的遍历,以及之前讲题时答应过的简单二叉树问题求解
给一组数据,升序(降序)排列
思路
思考:如果排列升序,我们应该建什么堆?
首先,如果排升序,数列最后一个数是 最大数,我们的思路是通过 向上调整 或者 向下调整,数组存放的第一个数不是最小值(小堆)就是最大值(大堆),此时我们将最后一个数与第一个数交换,使得最大值放在最后,此时再使用向上调整 或者 向下调整,得到第二大的数,重复上述动作,很明显,我们需要的第一个数是最大值,因此我们需要建大堆
反之,排降序,建立小堆
代码
#include<stdio.h> void downAdjust(int* pa, int parent, int n) { int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && pa[child] > pa[child + 1]) { child++; } if (pa[parent] > pa[child]) { swap(&pa[parent], &pa[child]); } else { break; } parent = child; child = parent * 2 + 1; } } int main() { int arr[] = { 1,3,2,5,7,4,7,4,2,5,6,8}; int n = sizeof(arr) / sizeof(arr[0]); for (int i = (n - 1 - 1) / 2; i >= 0; i--) { downAdjust(arr, i, n); } for (int i = n; i > 0; ) { swap(&arr[0], &arr[i - 1]); downAdjust(arr, 0, --i); } for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
在一组数据中,选出k个最大(最小)的数
思路
如果我们选择k个最大的数,假设数组的前k个数就是最大的数,这 k个数建立 小堆,带一个数与 后面的从第 k + 1个数开始,进行比较,如果比第一个数的就换下来,然后向下调整,直到每个所有数都比较完了
代码
void downAdjust(int* pa, int parent, int n) { int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && pa[child] > pa[child + 1]) { child++; } if (pa[parent] > pa[child]) { swap(&pa[parent], &pa[child]); } else { break; } parent = child; child = parent * 2 + 1; } } #include<stdio.h> int main() { int arr[] = { 1,6,10,3,5,8,46,23,6,25,3,40 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 0; scanf("%d", &k); for (int i = (k - 1 - 1) / 2; i >= 0; i--) { downAdjust(arr, i, n); } for (int i = k; i < n; i++) { if (arr[i] > arr[0]) { swap(&arr[i], &arr[0]); downAdjust(arr, 0, k); } } for (int i = 0; i < k; i++) { printf("%d ", arr[i]); } return 0; }
代码
typedef int TLType; typedef struct TreeList { TLType val; struct TreeList* left; struct TreeList* right; }TL; TL *creatnode(TLType x) { TL*pa = (TL*)malloc(sizeof(TL)); if (pa == NULL) { perror("malloc"); return; } TL* newnode = pa; newnode->left = newnode->right = NULL; newnode->val = x; return newnode; } TL* CreatTree() { TL* tree1 = creatnode(1); TL *tree2 = creatnode(2); TL* tree3 = creatnode(3); TL* tree4 = creatnode(3); tree1->left = tree2; tree1->right = tree3; tree2->left = tree4; return tree1; } #include<stdio.h> int main() { TL* p = NULL; p = CreatTree(); }
我们搭建了一个这样的树结构:
二叉树的遍历可以分三种:前序,中序,后序,层序
举例
这棵树的前序遍历是怎样的?(包括空树,用N表示)
val1 val2 val4 N N val5 N N val3 val6 N N val7 N N
代码实现?
#include<stdio.h> #include<stdlib.h> typedef int TLType; typedef struct TreeList { TLType val; struct TreeList* left; struct TreeList* right; }TL; TL *creatnode(TLType x) { TL*pa = (TL*)malloc(sizeof(TL)); if (pa == NULL) { perror("malloc"); return; } TL* newnode = pa; newnode->left = newnode->right = NULL; newnode->val = x; return newnode; } TL* CreatTree() { TL* tree1 = creatnode(1); TL *tree2 = creatnode(2); TL* tree3 = creatnode(3); TL* tree4 = creatnode(4); TL* tree5 = creatnode(5); TL* tree6 = creatnode(6); TL* tree7 = creatnode(7); tree1->left = tree2; tree1->right = tree3; tree2->left = tree4; tree2->right = tree5; tree3->left = tree6; tree3->right = tree7; return tree1; } #include<stdio.h> void PrevOrder(TL *root) { if (root == NULL) { printf("N "); return; } printf("%d ", root->val); PrevOrder(root->left); PrevOrder(root->right); } int main() { TL* p = NULL; p = CreatTree(); PrevOrder(p); }
运行结果:
举例
这棵树的中序遍历是怎样的?(包括空树,用N表示)
N val4 N val2 N val5 N val1 N val6 N val3 N val7 N
?代码实现
#include<stdio.h> #include<stdlib.h> typedef int TLType; typedef struct TreeList { TLType val; struct TreeList* left; struct TreeList* right; }TL; TL *creatnode(TLType x) { TL*pa = (TL*)malloc(sizeof(TL)); if (pa == NULL) { perror("malloc"); return; } TL* newnode = pa; newnode->left = newnode->right = NULL; newnode->val = x; return newnode; } TL* CreatTree() { TL* tree1 = creatnode(1); TL *tree2 = creatnode(2); TL* tree3 = creatnode(3); TL* tree4 = creatnode(4); TL* tree5 = creatnode(5); TL* tree6 = creatnode(6); TL* tree7 = creatnode(7); tree1->left = tree2; tree1->right = tree3; tree2->left = tree4; tree2->right = tree5; tree3->left = tree6; tree3->right = tree7; return tree1; } #include<stdio.h> void InOder(TL* root) { if (root == NULL) { printf("N "); return; } InOder(root->left); printf("%d ", root->val); InOder(root->right); } int main() { TL* p = NULL; p = CreatTree(); InOder(p); }
运行结果:
举例
这棵树的后序遍历是怎样的?(包括空树,用N表示)
N N val4 N N val5 val2 N N val6 N N val7 val3 val1
代码实现?
#include<stdio.h> #include<stdlib.h> typedef int TLType; typedef struct TreeList { TLType val; struct TreeList* left; struct TreeList* right; }TL; TL* creatnode(TLType x) { TL* pa = (TL*)malloc(sizeof(TL)); if (pa == NULL) { perror("malloc"); return; } TL* newnode = pa; newnode->left = newnode->right = NULL; newnode->val = x; return newnode; } TL* CreatTree() { TL* tree1 = creatnode(1); TL* tree2 = creatnode(2); TL* tree3 = creatnode(3); TL* tree4 = creatnode(4); TL* tree5 = creatnode(5); TL* tree6 = creatnode(6); TL* tree7 = creatnode(7); tree1->left = tree2; tree1->right = tree3; tree2->left = tree4; tree2->right = tree5; tree3->left = tree6; tree3->right = tree7; return tree1; } void PostOder(TL* root) { if (root == NULL) { printf("N "); return; } PostOder(root->left); PostOder(root->right); printf("%d ", root->val); } int main() { TL* p = NULL; p = CreatTree(); PostOder(p); }
运行结果:
一排排的遍历
画图举例
实现思路?
这里我们借助队列(可以先进先出),开辟的数组里面存放根节点的地址(通过地址可以找到左右子树,否则如果存值是没有办法找到左右子树),打印完根节点的值,就释放,存入左右子树的节点
代码实现
实现的二叉树是这样的:
#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int TLType; typedef struct TreeList { TLType val; struct TreeList* left; struct TreeList* right; }TL; TL* creatnode(TLType x) { TL* pa = (TL*)malloc(sizeof(TL)); if (pa == NULL) { perror("malloc"); return; } TL* newnode = pa; newnode->left = newnode->right = NULL; newnode->val = x; return newnode; } TL* CreatTree() { TL* tree1 = creatnode(1); TL* tree2 = creatnode(2); TL* tree3 = creatnode(3); TL* tree4 = creatnode(4); TL* tree5 = creatnode(5); TL* tree6 = creatnode(6); TL* tree7 = creatnode(7); tree1->left = tree2; tree1->right = tree3; tree2->left = tree4; tree2->right = tree5; tree3->left = tree6; tree3->right = tree7; return tree1; } typedef struct QueueNode { struct QueueNode* next; TL* data; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Que; void QueueInit(Que* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } void QueueDestroy(Que* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; pq->size = 0; } void QueuePush(Que* pq, TL* x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } bool QueueEmpty(Que* pq) { assert(pq); return pq->head == NULL; } void QueuePop(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } pq->size--; } TL* QueueFront(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } int QueueSize(Que* pq) { assert(pq); return pq->size; } void leverOrder(TL* root, Que* pq) { QueuePush(pq, root); while (!QueueEmpty(pq)) { TL* pa = QueueFront(pq); printf("%d ", pa->val); QueuePop(pq); if (pa->left != NULL) { QueuePush(pq, pa->left); } if (pa->right != NULL) { QueuePush(pq, pa->right); } } } int main() { TL* p = NULL; p = CreatTree(); Que q; QueueInit(&q); leverOrder(p, &q); return 0; }
运行结果:
思路
想要求二叉树的节点可以分成 根节点 + 左子树 + 右子树
这里的遍历类似 前序遍历
代码
实现的树是这样的:
#include<stdio.h> #include<stdlib.h> typedef int TLType; typedef struct TreeList { TLType val; struct TreeList* left; struct TreeList* right; }TL; TL* creatnode(TLType x) { TL* pa = (TL*)malloc(sizeof(TL)); if (pa == NULL) { perror("malloc"); return; } TL* newnode = pa; newnode->left = newnode->right = NULL; newnode->val = x; return newnode; } TL* CreatTree() { TL* tree1 = creatnode(1); TL* tree2 = creatnode(2); TL* tree3 = creatnode(3); TL* tree4 = creatnode(4); TL* tree5 = creatnode(5); TL* tree6 = creatnode(6); TL* tree7 = creatnode(7); tree1->left = tree2; tree1->right = tree3; tree2->left = tree4; tree2->right = tree5; tree3->left = tree6; tree3->right = tree7; return tree1; } int TreeSize(TL* root) { if (root == NULL) { return 0; } return 1 + TreeSize(root->left) + TreeSize(root->right); } int main() { TL* p = NULL; p = CreatTree(); int size = TreeSize(p); printf("%d ", size); return 0; }
思路
求二叉树的高度,我们需要找到到那个最长的路径,这里采用分治的思想,如果为空树,返回 0 (空树高度为 0),调用左子树和右子树都会 + 1(+ 1可以理解成加上节点的高度),对比左子树和右子树,返回高度最大的那个
注:每求一次左右节点个数时,一定要保存,否则会有很大的时间浪费
代码
#include<stdio.h> #include<stdlib.h> typedef int TLType; typedef struct TreeList { TLType val; struct TreeList* left; struct TreeList* right; }TL; TL* creatnode(TLType x) { TL* pa = (TL*)malloc(sizeof(TL)); if (pa == NULL) { perror("malloc"); return; } TL* newnode = pa; newnode->left = newnode->right = NULL; newnode->val = x; return newnode; } TL* CreatTree() { TL* tree1 = creatnode(1); TL* tree2 = creatnode(2); TL* tree3 = creatnode(3); TL* tree4 = creatnode(4); TL* tree5 = creatnode(5); TL* tree6 = creatnode(6); TL* tree7 = creatnode(7); TL* tree8 = creatnode(8); tree1->left = tree2; tree1->right = tree3; tree2->left = tree4; tree2->right = tree5; tree3->left = tree6; tree3->right = tree7; tree4->left = tree8; return tree1; } int TreeHigh(TL* root) { if (root == NULL) { return 0; } int Left = 1 + TreeHigh(root->left); int Right = 1 + TreeHigh(root->right) ; return Left > Right ? Left : Right; } int main() { TL* p = NULL; p = CreatTree(); int high = TreeHigh(p); printf("%d ", high); return 0; }
思路
判断是否是根节点的方法就是判断它的左右子树是否是 空树,我们只需要遍历这棵树就行,但如果遍历时,根节点遇到空树这也是一种结束条件
代码
#include<stdio.h> #include<stdlib.h> typedef int TLType; typedef struct TreeList { TLType val; struct TreeList* left; struct TreeList* right; }TL; TL* creatnode(TLType x) { TL* pa = (TL*)malloc(sizeof(TL)); if (pa == NULL) { perror("malloc"); return; } TL* newnode = pa; newnode->left = newnode->right = NULL; newnode->val = x; return newnode; } TL* CreatTree() { TL* tree1 = creatnode(1); TL* tree2 = creatnode(2); TL* tree3 = creatnode(3); TL* tree4 = creatnode(4); TL* tree5 = creatnode(5); TL* tree6 = creatnode(6); TL* tree7 = creatnode(7); TL* tree8 = creatnode(8); tree1->left = tree2; tree1->right = tree3; tree2->left = tree4; tree2->right = tree5; tree3->left = tree6; tree3->right = tree7; tree4->left = tree8; return tree1; } int RootSize(TL* root) { if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL) { return 1; } return RootSize(root->left) + RootSize(root->right); } int main() { TL* p = NULL; p = CreatTree(); int root = RootSize(p); printf("%d ", root); return 0; }
思路
这个可以是求树的高度的变形,将计数倒过来
代码?
#include<stdio.h> #include<stdlib.h> typedef int TLType; typedef struct TreeList { TLType val; struct TreeList* left; struct TreeList* right; }TL; TL* creatnode(TLType x) { TL* pa = (TL*)malloc(sizeof(TL)); if (pa == NULL) { perror("malloc"); return; } TL* newnode = pa; newnode->left = newnode->right = NULL; newnode->val = x; return newnode; } TL* CreatTree() { TL* tree1 = creatnode(1); TL* tree2 = creatnode(2); TL* tree3 = creatnode(3); TL* tree4 = creatnode(4); TL* tree5 = creatnode(5); TL* tree6 = creatnode(6); TL* tree7 = creatnode(7); TL* tree8 = creatnode(8); tree1->left = tree2; tree1->right = tree3; tree2->left = tree4; tree2->right = tree5; tree3->left = tree6; tree3->right = tree7; tree4->left = tree8; return tree1; } int TreeHigh(TL* root) { if (root == NULL) { return 0; } int Left = 1 + TreeHigh(root->left); int Right = 1 + TreeHigh(root->right) ; return Left > Right ? Left : Right; } int RootKsize(TL* root,int n,int k) { if (root == NULL) { return 0; } if (n == k) { return 1; } return RootKsize(root->left, n - 1, k) + RootKsize(root->right, n - 1, k); } int main() { int k = 0; scanf("%d", &k); TL* p = NULL; p = CreatTree(); int high = TreeHigh(p); int rootk = RootKsize(p, high, k); printf("%d ", rootk); return 0; }
思路
采用前序,先比较根节点是否相同,再比较左右子树是否相同
代码
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> typedef int TLType; typedef struct TreeList { TLType val; struct TreeList* left; struct TreeList* right; }TL; TL* creatnode(TLType x) { TL* pa = (TL*)malloc(sizeof(TL)); if (pa == NULL) { perror("malloc"); return; } TL* newnode = pa; newnode->left = newnode->right = NULL; newnode->val = x; return newnode; } TL* CreatTree1() { TL* tree1 = creatnode(1); TL* tree2 = creatnode(2); TL* tree3 = creatnode(3); TL* tree4 = creatnode(4); TL* tree5 = creatnode(5); TL* tree6 = creatnode(6); TL* tree7 = creatnode(7); TL* tree8 = creatnode(8); tree1->left = tree2; tree1->right = tree3; tree2->left = tree4; tree2->right = tree5; tree3->left = tree6; tree3->right = tree7; tree4->left = tree8; return tree1; } TL* CreatTree2() { TL* tree1 = creatnode(1); TL* tree2 = creatnode(2); TL* tree3 = creatnode(3); TL* tree4 = creatnode(4); TL* tree5 = creatnode(5); TL* tree6 = creatnode(6); TL* tree7 = creatnode(7); tree1->left = tree2; tree1->right = tree3; tree2->left = tree4; tree2->right = tree5; tree3->left = tree6; tree3->right = tree7; return tree1; } bool IsSameTree(TL* root1,TL* root2) { if (root1 == NULL && root2 == NULL) { return true; } if (root1 == NULL || root2 == NULL) { return false; } if (root1->val != root2->val) { return false; } return IsSameTree(root1->left, root2->left) && IsSameTree(root1->right, root2->right); } int main() { TL* p = NULL; p = CreatTree1(); TL* q = CreatTree2(); printf("%d ", IsSameTree(p, q)); return 0; }
思路
前序遍历完数组,如果对比左右子树,判断是否找到节点的地址
代码
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> typedef int TLType; typedef struct TreeList { TLType val; struct TreeList* left; struct TreeList* right; }TL; TL* creatnode(TLType x) { TL* pa = (TL*)malloc(sizeof(TL)); if (pa == NULL) { perror("malloc"); return; } TL* newnode = pa; newnode->left = newnode->right = NULL; newnode->val = x; return newnode; } TL* CreatTree() { TL* tree1 = creatnode(1); TL* tree2 = creatnode(2); TL* tree3 = creatnode(2); TL* tree4 = creatnode(4); TL* tree5 = creatnode(5); TL* tree6 = creatnode(6); TL* tree7 = creatnode(7); TL* tree8 = creatnode(8); tree1->left = tree2; tree1->right = tree3; tree2->left = tree4; tree2->right = tree5; tree3->left = tree6; tree3->right = tree7; tree4->left = tree8; return tree1; } TL* FindRoot(TL* root,int m) { if (root == NULL) { return NULL; } if (root->val == m) { return root; } TL* Left = FindRoot(root->left, m); TL* Right = FindRoot(root->right, m); if (Left == NULL && Right == NULL) { return NULL; } if (Left == NULL && Right != NULL) { return Right; } else { return Left; } } int main() { TL* p = NULL; p = CreatTree(); int m = 0; scanf("%d", &m); TL *root = FindRoot(p,m); if (root == NULL) { printf("找不到\n"); } else { printf("%d ", root->val); } return 0; }