【数据结构】堆和二叉树（2）

---

前言

接着上一篇博客，我们继续分享关于堆和二叉树的知识，这里小编会跟大家分享关于如何建堆，堆排序，二叉树的链式结构以及相关知识。

---

一、建堆和堆排序

如果我们这里想要实现堆排序，那么我们就需要一个堆，在堆的基础之上实现排序。所以这里就需要建堆了。那这里就有一个问题了。
如果是升序的话我们该建大堆还是小堆呢？降序又该建大堆还是小堆呢？

这里我们可以得出结论了嘛！降序建小堆，升序建大堆

1.堆排序

1.建堆：
跟之前的堆的插入一样，但是这样有个弊端就是，每插入一个数据就要申请一个空间呀。大大地减低了代码的运行效率。那我们是数组的话那是不是太浪费时间了呀，还要一个个的插入。那有没有一种方法就是在不开辟新的空间的前提下让数组里面的数据有序呀？这里就要用到排序了呀。可以用冒号，选择。但是这两种的效率是不是很低呀？时间复杂度是O(N)^2。欧克，今天我们就要引入一个新的排序方法：堆排序。既然是堆排序，那是不是就需要一个堆呀？那怎样建堆呢？有两种建堆方式：

//   向上建堆
void HeapSort(int* arr, int n)
{for (int i = 0; i < n; i++){AdjustUp(arr, i);}int main()
{int arr[] = { 2,4,5,6,7 };HeapSort(arr, sizeof(arr) / sizeof(int));return 0;
}
//向下建堆 
void HeapSort(int* arr, int n)
{for (int i = (n-1-1)/2; i >=0; i--){AdjustDowan(arr, n,i);}
}int main()
{int arr[] = { 2,4,5,6,7 };HeapSort(arr, sizeof(arr) / sizeof(int));return 0;
}

这里需要注意的是。向下调整是从最后一个父亲节点开始依次向下调整的。拿为什么不是从最后一个数据开始呢?因为最后一个数据已经有序了呀！那还需要调整吗？
这样建堆的话是不是就避免了要重新开辟一个新的空间呀?在原数组之上直接建堆。
2.向上调整建堆和向下调整建堆

//                            向上调整建堆
void AdjustUp(int* arr, int chiled)
{int parent = (chiled - 1) / 2;while (chiled > 0){if (arr[chiled] < arr[parent]){Swap(&arr[chiled], &arr[parent]);chiled = parent;parent = (chiled - 1) / 2; }else{break;}}
}
//                            向下调整建堆
void AdjustDown(int* arr, int n, int parent)
{int chiled = 2 * parent + 1;while (chiled < n){if (chiled + 1 < n && arr[chiled + 1] < arr[chiled]){++chiled;}if (arr[parent] >arr[chiled]){Swap(&arr[parent], &arr[chiled]);parent = chiled;chiled = 2 * parent + 1;}else{break;}}
}

这个就是向上和向下调整建堆，这个就是我们之前的堆的插入和堆删除那里的向上调整建堆是一样的。如果不知道的可以取看一下小编之前讲堆的那个章节：https://editor.csdn.net/md/articleId=142728291

void Swap(int* p1, int* p2)
{int* tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustUp(int* arr, int chiled)
{int parent = (chiled - 1) / 2;while (chiled > 0){if (arr[chiled] < arr[parent]){Swap(&arr[chiled], &arr[parent]);chiled = parent;parent = (chiled - 1) / 2; }else{break;}}
}
void AdjustDown(int* arr, int n, int parent)
{int chiled = 2 * parent + 1;while (chiled < n){if (chiled + 1 < n && arr[chiled + 1] < arr[chiled]){++chiled;}if (arr[parent] >arr[chiled]){Swap(&arr[parent], &arr[chiled]);parent = chiled;chiled = 2 * parent + 1;}else{break;}}
}
void HeapSort(int* arr, int n)
{for (int i = 0; i < n; i++){AdjustUp(arr, i);}int end = n - 1;//最后一个数据while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);--end; }for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}
int main()
{int arr[] = { 2,4,5,6,7 };HeapSort(arr, sizeof(arr) / sizeof(int));return 0;
}

大家可以看出我们我们这个代码则是一个建小堆的过程，建小堆是不是降序呀？我们来来看看这个代码的运行结果：

那如果是升序的话，只需要把向上和向下调整建堆哪里改一下就欧克了，改成大堆就行了，这回该知道为什么：降序建小堆，升序建大堆
以上就是关于建堆和堆排序的相关知识了。接下来我们来看看二叉树链式结构的实现

二、二叉树链式结构的实现

为了方便学习链式二叉树的知识，那我们必须要有一棵树呀！这里呢为了方便好理解，我这里呢就直接手搓一颗树用来分享：

这下面是他的代码实现：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->left = NULL;newnode->right = NULL;return newnode;
}
BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}
int main()
{CreatBinaryTree();return 0;
}

注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。

1.二叉树的遍历

二叉树的遍历呢分为前序遍历，中序遍历，后序遍历按照规则，每种遍历的顺序是不一样的。

前序遍历：根—>左子树—>右子树
中序遍历：左子树—>根—>右子树
后序遍历：左子树—>右子树—>根
我们拿第一种来说，他的意思就是先访问根节点，然后在访问左子树，最后才右子树

首先我们先访问的是1，然后在访问1节点的左子树，1的左子树不为空，所以访问2，在访问2的左子树，2的左子树不为空，所以访问3，然后在访问3的左子树，3的左子树为空，返回到3，在访问3的右子树，3的右子树为空 ，返回到3，然后3访问完了就返回到2，在访问2的右子树。右子树为空，返回到2，2也访问完了返回到1，1的左子树全部访问完毕，接下来就访问右子树4，4的左子树不为空，所以访问5，在访问5的左子树，5的左子树为空，返回到5，在访问5的右子树，右子树为空返回到5，5访问完了在返回到4，在访问4的右子树，右子树不位空，所以访问6，在访问6的左子树，左子树为空，返回到6，在访问6的右子树，右子树为空，返回到6，6已经被访问完，返回到4，4的已经被访问完，在返回到1，1也被访问完了，所以跳出。
注意：不管怎样访问，我们都把二叉树分为根，左子树和右子树三部分。
一般的情况从逻辑的角度的方面来说，逻辑上我们就是将一棵树的前序遍历分为根的访问和左右子树的遍历。左右子树的遍历我们又可以看成一棵树的前序遍历。所以这里要用到了递归。

代码实现：我们现在已经了解前序遍历。那我们要怎样才能实现代码呢？

void PreOrder(BTNode* root)//前序遍历
{if (root == NULL){printf("N");return;}printf("%d", root->data);PreOrder(root->left);PreOrder(root->right );
}
void InOrder(BTNode* root)//中序遍历
{if (root == NULL){printf("N");return;}InOrder(root->left);printf("%d", root->data); InOrder(root->right);
}
void PostOrder(BTNode* root)//后序遍历
{if (root == NULL){printf("N");return;}PostOrder(root->left); PostOrder(root->right);printf("%d", root->data);
}

由于前序，中序，后序遍历大同小异，所以我这里就全部写出来了。

层序遍历：
从字面意思来理解就是一层一层的遍历嘛。确实，它的确是一层一层的遍历。首先访问第一层的根节点，然后在从左到右访问第二层，这样依次类推。那样怎样代码实现，这里就要借助我们之前学的队列了 。利用队列先进先出的规则来实现。

void TreeLevelOrder(BTNode* p)//层序遍历
{Queue pq;QueueInit(&pq);//初始化队列if(p)QueuePush(&pq, p);//第一层入队列while (!QueueEmpty(&pq))//队列不为空{BTNode* head = QueueFron(&pq);//取出队头数据QueuePop(&pq);//出队列printf("%d ", head->a);//访问if (head->left){QueuePush(&pq, head->left);//左孩子入队列}if (head->right){QueuePush(&pq, head->right);//右孩子入队列}}QueueDestroy(&pq);//销毁队列
}

这里需要注意的是：我们这里存储的是结点指针，因为我们要访问左右子树。

三、链式二叉树的功能函数

1.二叉树结点个数

想要算出二叉树的个数，大多数情况我们会想到在遍历的时候用一个变量来表示节点的个数：就像这样：

int TreeSize(BTNode* root)
{int size = 0;if (root == NULL){return 0;}size++;TreeSize(root->left); TreeSize(root->right);return size;
}
int main()
{BTNode *root= CreatBinaryTree();printf("节点的个数：");int ret = TreeSize(root); printf("%d", ret);
}

但是这里的结果却是1呀？为什么呢？其实呀？这里的size是一个局部变量，每次调用呢都会被置为0，所以后面最多只能自加一次，所以结果是1，那我们把这里改为静态的使他的生命周期变为全局变量呢？

int TreeSize(BTNode* root)
{static int size = 0;if (root == NULL){return 0;}size++;TreeSize(root->left);TreeSize(root->right);return size;
}
int main()
{int size = 0;BTNode *root= CreatBinaryTree();printf("节点的个数：");int ret = TreeSize(root); printf("%d", ret);printf("\n");printf("节点的个数："); int ret1 = TreeSize(root);printf("%d", ret1);
}

这里呢我们可以看见第一次呢是没有问题的，但是第二次调用为什么就是12了呢？因为这里的局部的静态变量只会初始化一次，但你第二次调用的是它初始化的值是上一次调用的结果。所以这里就是6+6=12了。那要这样解决呢？这里我们只需要在第二次调用之前重新把size置为0就行了。

int size=0;
int TreeSize(BTNode* root)
{if (root == NULL){return 0;}size++;TreeSize(root->left);TreeSize(root->right);return size;
}
int main()
{BTNode *root= CreatBinaryTree();printf("节点的个数：%d\n",TreeSize(root));size = 0;printf("节点的个数：%d", TreeSize(root));printf("\n");
}

当然还有一种就是传一个形参，从外边传一个变量的形参过来。

int  TreeSaze(BTNode*root,int* k)
{if (root == NULL){return 0;}(*k)++;;TreeSaze(root->left,k);   TreeSaze(root->right,k);   return (*k);
}

这里的返回值其实要不要都无所谓的，返回也行，不返回也行。
这里呢以上的就是算二叉树节点的代码了，其实还有一种更简单的思路：分治递归
我们把二叉树的所有的节点都看成左子树+右子树+根

我们结合代码来看。

int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return  BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
int main()
{BTNode* root = CreatBinaryTree();printf("节点的个数是：");printf("%d\n", BinaryTreeSize(root));return 0;
}

这样子是不是就简单多了呀？只是这个比较难理解。不过只要你熟练掌握递归就可以很轻松的理解了。

2.二叉树叶子结点个数

二叉树的叶子是不是度为0的节点。叶子节点的个数=左子树+右子树。所以这里又要用到分治递归了。

int  TreeLeafSize(BTNode* root)//叶子节点
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return TreeLeafSize(root->left) + TreeLeafSize(root->right); 
}

这里要注意的是要考虑如果树是空树的情况

3.二叉树的高度

想要算出二叉树的高度，是不是要算出左右子树的高度呀？然后选择高度最高的来加上根的高度呀？
要是是一个空树的话，那就返回0。

int TreeHight(BTNode* root)//高度
{if (root == NULL){return 0;}return TreeHight(root->left)> TreeHight(root->right) ? TreeHight(root->left)+1: TreeHight(root->right)+1;
}
int main()
{BTNode* root = CreatBinaryTree();printf("节点的个数是：");printf("%d\n", TreeHight(root));return 0;
}

这样可不可以呢？由于我们这里给的数据太少了，所以代码就能跑过。但是这里存在一个效率问题。

int TreeHight(BTNode* root)//高度
{if (root == NULL){return 0;}int LeftHight = TreeHight(root->left);int RightHight = TreeHight(root->right);return  LeftHight > RightHight ? LeftHight + 1: RightHight+1;
}
int main()
{BTNode* root = CreatBinaryTree();printf("节点的个数是：");printf("%d\n", TreeHight(root));return 0;
}

像这样把访问的数据储存起来。

4.二叉树第k层结点个数

int TreeLeveKsize(BTNode* root,int k)
{if (root == NULL)return 0;if (k == 1)return 1;return TreeLeveKsize(root->left,k-1) + TreeLeveKsize(root->right,k-1);
}

5. 二叉树查找值为x的结点

查找x的节点其实是一个看似很简单。实则不简单的一个代码，思路好理解，但是要写出正确的代码就得要仔细思考了

BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL; if (root->data == x)return root ;TreeFind(root->left,x);TreeFind(root->right, x);
}

来看看这个代码是不是正确的。其实这里有两个问题，第一个就是如果我找到要找的数据。那我是不是要返回上一个栈帧呀，但是这里数据没有被接收呀。那我们返回的是什么？就不知道了是吧。第二呢就是。如果在左子树已经找到了，那是不是就不需要再找了呀？那万一右子树也有一个要找的数据怎么办？这时候直接返回第一次找到的数据就ok，原因就是函数返回值只能返回一个。不能返回多个数据。
那正确的代码就是：

BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;
if (root->data == x)return root;BTNode* ret1 = TreeFind(root->left, x);   if (ret1){return ret1;}BTNode* ret2 = TreeFind(root->right, x); { return ret2;}return NULL;
}
BTNode* TreeFind(BTNode* root, BTDataType x)//优化代码
{if (root == NULL)return NULL;if (root->data == x)return root;BTNode* ret1 = TreeFind(root->left, x);if (ret1){return ret1;}return  TreeFind(root->right, x);}

这两种代码都是可以的。

6.二叉树销毁

二叉树的销毁跟其他的销毁有点不一样哦。这里要用到后序遍历来销毁。那为什么要用后序遍历呢而不用前序遍历和中序遍历呢?这里其实都可以。但是这个时候我们就要一个变量来储存左孩子和有孩子（前序遍历销毁）。如果直接释放掉根节点，不然就找不到根的左右孩子了

void BinaryTreeDestory1(BTNode* root)//前序遍历销毁
{if (root == NULL)return;BTNode* newnode = root->left;BTNode* newnode1 = root->right;free(root);BinaryTreeDestory1(newnode);BinaryTreeDestory1(newnode1);//root=NULL;
}
void BinaryTreeDestory2(BTNode* root)//中序遍历销毁
{if (root == NULL)return;BTNode* newnode1 = root->right;BinaryTreeDestory2(root->left );free(root);BinaryTreeDestory2(newnode1);//root=NULL;
}
void BinaryTreeDestory(BTNode*root)//后序遍历销毁
{if (root == NULL)return;BinaryTreeDestory(root->left);BinaryTreeDestory(root->right );free(root);//root=NULL;
}
int main()
{BTNode* root = CreatBinaryTree();BinaryTreeDestory(root);root = NULL;return 0;
}

那我们这里在释放后要不要把root置为空呢？这里置不置空都行，因为传的是一级指针呀。形参的改变不会改变外边的实参。所以这里可以置可不置。正常使用呢是在主函数哪里当我要用的时候在置为空

---

总结

今天的分享就到这里吧。再见咯，各位！