做影视网站需要境外,个人网站模板,格力网站的建设情况,网站换空间wordpress文章目录 前言一、建堆和堆排序1.堆排序 二、二叉树链式结构的实现1.二叉树的遍历 三、链式二叉树的功能函数1.二叉树结点个数2.二叉树叶子结点个数3.二叉树的高度4.二叉树第k层结点个数5. 二叉树查找值为x的结点6.二叉树销毁 总结 前言
接着上一篇博客#xff0c;我们继续分… 文章目录 前言一、建堆和堆排序1.堆排序 二、二叉树链式结构的实现1.二叉树的遍历 三、链式二叉树的功能函数1.二叉树结点个数2.二叉树叶子结点个数3.二叉树的高度4.二叉树第k层结点个数5. 二叉树查找值为x的结点6.二叉树销毁 总结 前言
接着上一篇博客我们继续分享关于堆和二叉树的知识这里小编会跟大家分享关于如何建堆堆排序二叉树的链式结构以及相关知识。 一、建堆和堆排序
如果我们这里想要实现堆排序那么我们就需要一个堆在堆的基础之上实现排序。所以这里就需要建堆了。那这里就有一个问题了。 如果是升序的话我们该建大堆还是小堆呢降序又该建大堆还是小堆呢 这里我们可以得出结论了嘛降序建小堆升序建大堆
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/articleId142728291
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;
}大家可以看出我们我们这个代码则是一个建小堆的过程建小堆是不是降序呀我们来来看看这个代码的运行结果 那如果是升序的话只需要把向上和向下调整建堆哪里改一下就欧克了改成大堆就行了这回该知道为什么降序建小堆升序建大堆 以上就是关于建堆和堆排序的相关知识了。接下来我们来看看二叉树链式结构的实现
二、二叉树链式结构的实现
为了方便学习链式二叉树的知识那我们必须要有一棵树呀这里呢为了方便好理解我这里呢就直接手搓一颗树用来分享 这下面是他的代码实现
#includestdio.h
#includestdlib.h
#includeassert.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的右子树。右子树为空返回到22也访问完了返回到11的左子树全部访问完毕接下来就访问右子树44的左子树不为空所以访问5在访问5的左子树5的左子树为空返回到5在访问5的右子树右子树为空返回到55访问完了在返回到4在访问4的右子树右子树不位空所以访问6在访问6的左子树左子树为空返回到6在访问6的右子树右子树为空返回到66已经被访问完返回到44的已经被访问完在返回到11也被访问完了所以跳出。 注意不管怎样访问我们都把二叉树分为根左子树和右子树三部分。 一般的情况从逻辑的角度的方面来说逻辑上我们就是将一棵树的前序遍历分为根的访问和左右子树的遍历。左右子树的遍历我们又可以看成一棵树的前序遍历。所以这里要用到了递归。
代码实现我们现在已经了解前序遍历。那我们要怎样才能实现代码呢
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了呢因为这里的局部的静态变量只会初始化一次但你第二次调用的是它初始化的值是上一次调用的结果。所以这里就是6612了。那要这样解决呢这里我们只需要在第二次调用之前重新把size置为0就行了。
int size0;
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: RightHight1;
}
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);//rootNULL;
}
void BinaryTreeDestory2(BTNode* root)//中序遍历销毁
{if (root NULL)return;BTNode* newnode1 root-right;BinaryTreeDestory2(root-left );free(root);BinaryTreeDestory2(newnode1);//rootNULL;
}
void BinaryTreeDestory(BTNode*root)//后序遍历销毁
{if (root NULL)return;BinaryTreeDestory(root-left);BinaryTreeDestory(root-right );free(root);//rootNULL;
}
int main()
{BTNode* root CreatBinaryTree();BinaryTreeDestory(root);root NULL;return 0;
}那我们这里在释放后要不要把root置为空呢这里置不置空都行因为传的是一级指针呀。形参的改变不会改变外边的实参。所以这里可以置可不置。正常使用呢是在主函数哪里当我要用的时候在置为空 总结
今天的分享就到这里吧。再见咯各位
