wordpress构建企业网站免费申请qq号码免费申请注册

当前位置： 首页 > news >正文

wordpress构建企业网站,免费申请qq号码免费申请注册,中国的科技成就,做消防哪些网站找工作博客主页#xff1a;【夜泉_ly】 本文专栏#xff1a;【数据结构】 欢迎点赞#x1f44d;收藏⭐关注❤️ 数据结构-链式二叉树-四种遍历 1.前言2.前、中、后序遍历2.1前序遍历2.1中、后序遍历 3.层序遍历3.1递归实现3.2队列实现关于在Pop之后为什么还能用tmp访问节点#x… 博客主页【夜泉_ly】 本文专栏【数据结构】 欢迎点赞收藏⭐关注❤️ 数据结构-链式二叉树-四种遍历 1.前言2.前、中、后序遍历2.1前序遍历2.1中、后序遍历 3.层序遍历3.1递归实现3.2队列实现关于在Pop之后为什么还能用tmp访问节点关于都已经把队列Pop为空了为什么还要QueueDestroy 4.浅谈DFS与BFS 1.前言 在我之前的文章数据结构-堆-详解中我对堆这种特殊的完全二叉树做了详细介绍。 完全二叉树非常适合用数组存储但一般的二叉树呢如下图所示 可以发现普通二叉树若使用数组存储会浪费大量空间这时链式存储结构成为更好的选择。 在这种结构中每个节点应包含自身所存储的数据以及指向左右子树的指针。 可以通过以下结构体定义二叉树节点 typedef char BTDataType;typedef struct TreeNode {BTDataType val;struct TreeNode* left;struct TreeNode* right; }TreeNode;为了便于理解我手搓了一个简单的二叉树 代码如下 TreeNode* BuyTreeNode(BTDataType x) {TreeNode* tmp (TreeNode)malloc(sizeof(TreeNode));if (!tmp){perror(BuyTreeNode::malloc);return NULL;}tmp-val x;tmp-left NULL;tmp-right NULL;return tmp; } TreeNode CreatBinaryTree() {TreeNode* root BuyTreeNode(a);TreeNode* n1 BuyTreeNode(b);TreeNode* n2 BuyTreeNode©;TreeNode* n3 BuyTreeNode(d);TreeNode* n4 BuyTreeNode(e);TreeNode* n5 BuyTreeNode(f);TreeNode* n6 BuyTreeNode(g);root-left n1;root-right n2;n1-left n3;n1-right n4;n2-left n5;n2-right n6;return root; }注意这并不是二叉树真正的创建方法等对于二叉树的结构有更深入的了解后再讲创建。 在对二叉树进行各项操作时应对其结构有明确的认识 对任意一个二叉树都由 根 、左子树 、右子树 组成。 而左右子树也是二叉树也有对应的 根 、左子树 、右子树。 因此二叉树的定义是递归的在对二叉树进行处理时也常常使用递归。 而对二叉树的递归操作也应以 根 、左子树 、右子树 为基础展开。 2.前、中、后序遍历 2.1前序遍历 二叉树的前序遍历先访问根再遍历左子树最后遍历右子树。 void BinaryTreePrevOrder(TreeNode* root) {if (!root){printf(NULL );return;}printf(%c , root-val);BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right); }先判断根如果为空就打印NULL并返回 若不为空则先打印根的值再遍历左子树最后遍历右子树。 在二叉树这块可以先画画逻辑结构图 虽然画的不全但大概就是这么个意思。 如果难以理解时可以再画画递归展开图把代码是怎么一行行执行的给画出来。 经过分析可知打印结果应该是a b d NULL NULL e NULL NULL c f NULL NULL g NULL NULL。
也可以选择不打印空结果是a b d e c f g。 在画过图后应对二叉树的遍历有更清楚的认识 在打印d后为什么直接打印e? 并非是从d的节点直接到e的节点 而是先访问d的两个空的左右子树d结束了左右子树的遍历返回到b。 此时b结束了它的左子树的遍历于是开始遍历右子树然后才到了e处。 2.1中、后序遍历 二叉树的中序遍历先遍历左子树再访问根最后遍历右子树。 void BinaryTreeInOrder(TreeNode* root) {if (!root){printf(NULL );return;}BinaryTreeInOrder(root-left);printf(%c , root-val);BinaryTreeInOrder(root-right); }二叉树的后序遍历先遍历左子树再遍历右子树最后访问根。 void BinaryTreePostOrder(TreeNode* root) {if (!root){printf(NULL );return;}BinaryTreePostOrder(root-left);BinaryTreePostOrder(root-right);printf(%c , root-val); }此时可以写个代码测试一下 int main() {TreeNode* root CreatBinaryTree();printf(BinaryTreePrevOrder:);BinaryTreePrevOrder(root);printf(\nBinaryTreeInOrder:);BinaryTreeInOrder(root);printf(\nBinaryTreePostOrder:);BinaryTreePostOrder(root);return 0; }运行结果 也可以不打印NULL
3.层序遍历 就是从上至下从左至右的遍历
3.1递归实现 此实现方法并不重要所以略讲。 先求个高度 int TreeHeight(TreeNode* root) {if (!root)return 0;int leftheight TreeHeight(root-left);int rightheight TreeHeight(root-right);return leftheight rightheight ? 1 leftheight : 1 rightheight; }再写个打印第k层元素的函数 void BinaryTreeLevelPrint(TreeNode* root, int level) {if (!root)return;if (level 1)printf(%c , root-val);else{BinaryTreeLevelPrint(root-left, level - 1);BinaryTreeLevelPrint(root-right, level - 1);} }最后组合起来即一层一层的打印 void BinaryTreeLevelOrder(TreeNode* root) {int level TreeHeight(root);for (int i 1; i level; i){BinaryTreeLevelPrint(root, i);} }测试一下 int main() {TreeNode* root CreatBinaryTree();printf(BinaryTreeLevelOrder:);BinaryTreeLevelOrder(root);return 0; }结果
3.2队列实现 二叉树层序遍历使用递归比较麻烦且不太直观因此通常使用另一种方法即队列 先将根节点入队列 将队首的节点出队列并带入当前节点的两个非空子节点 重复 再重复 队列为空停止
其中有关队列的函数可直接CV – 数据结构-栈、队列-详解。 需注意的是存入队列的是指向节点的指针因此需改变一下队列存储的数据类型 //typedef int QDatatype; typedef TreeNode* QDatatype;代码实现 void BinaryTreeLevelOrder(TreeNode* root) {Queue q;QueueInit(q);if (!root);QueuePush(q, root);while (!QueueEmpty(q)){TreeNode* tmp QueueFront(q);QueuePop(q);printf(%c , tmp-val);if (tmp-left)QueuePush(q, tmp-left);if (tmp-right)QueuePush(q, tmp-right);}printf(\n);QueueDestroy(q); }常见疑问解答: 关于在Pop之后为什么还能用tmp访问节点 因为Pop的是队列的节点tmp为局部变量保存了队首元素的值作为指针指向树中的节点。 因此在Pop之后还能用tmp访问节点。 关于都已经把队列Pop为空了为什么还要QueueDestroy 我所写的队列是不带哨兵位头结点的所以把队列Pop空了后用不用QueueDestroy都无所谓但如果其他人写的队列带了哨兵位头结点不Destroy就会造成内存泄漏。 这里有个词叫耦合还有个词叫解耦 耦合是指两个或两个以上的体系或两种运动形式间通过相互作用而彼此影响以至联合起来的现象。 解耦就是用数学方法将两种运动分离开来处理问题常用解耦方法就是忽略或简化对所研究问题影响较小的一种运动只分析主要的运动。 在使用队列时不管是怎样操作的在最后都加上QueueDestroy这也算是一种解耦因为这样无论队列是如何实现的无论实现者用的数组还是链表、单链还是双链、带不带哨兵位的头结点都可以避免问题的产生。 4.浅谈DFS与BFS DFS即Depth First Search深度优先搜索。 二叉树的DFS就是前序遍历放宽一点就是前、中、后序遍历。 特点是一条路走到底再返回并走其他的路。多用递归实现。 BFS即Breadth First Search,广度优先搜索。 二叉树的BFS就是层序遍历。 特点是一点点扩大搜索范围类似于地毯式搜索。多用队列实现。 希望本篇文章对你有所帮助并激发你进一步探索数据结构的兴趣 本人仅是个C语言初学者如果你有任何疑问或建议欢迎随时留言讨论让我们一起学习共同进步 #mermaid-svg-zmIcpX5KDA3eGEn5 {font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-zmIcpX5KDA3eGEn5 .error-icon{fill:#552222;}#mermaid-svg-zmIcpX5KDA3eGEn5 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-zmIcpX5KDA3eGEn5 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-zmIcpX5KDA3eGEn5 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-zmIcpX5KDA3eGEn5 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-zmIcpX5KDA3eGEn5 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-zmIcpX5KDA3eGEn5 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-zmIcpX5KDA3eGEn5 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-zmIcpX5KDA3eGEn5 .marker.cross{stroke:#333333;}#mermaid-svg-zmIcpX5KDA3eGEn5 svg{font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-zmIcpX5KDA3eGEn5 .label{font-family:“trebuchet ms”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-zmIcpX5KDA3eGEn5 .cluster-label text{fill:#333;}#mermaid-svg-zmIcpX5KDA3eGEn5 .cluster-label span{color:#333;}#mermaid-svg-zmIcpX5KDA3eGEn5 .label text,#mermaid-svg-zmIcpX5KDA3eGEn5 span{fill:#333;color:#333;}#mermaid-svg-zmIcpX5KDA3eGEn5 .node rect,#mermaid-svg-zmIcpX5KDA3eGEn5 .node circle,#mermaid-svg-zmIcpX5KDA3eGEn5 .node ellipse,#mermaid-svg-zmIcpX5KDA3eGEn5 .node polygon,#mermaid-svg-zmIcpX5KDA3eGEn5 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-zmIcpX5KDA3eGEn5 .node .label{text-align:center;}#mermaid-svg-zmIcpX5KDA3eGEn5 .node.clickable{cursor:pointer;}#mermaid-svg-zmIcpX5KDA3eGEn5 .arrowheadPath{fill:#333333;}#mermaid-svg-zmIcpX5KDA3eGEn5 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-zmIcpX5KDA3eGEn5 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-zmIcpX5KDA3eGEn5 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-zmIcpX5KDA3eGEn5 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-zmIcpX5KDA3eGEn5 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-zmIcpX5KDA3eGEn5 .cluster text{fill:#333;}#mermaid-svg-zmIcpX5KDA3eGEn5 .cluster span{color:#333;}#mermaid-svg-zmIcpX5KDA3eGEn5 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-zmIcpX5KDA3eGEn5 :root{–mermaid-font-family:“trebuchet ms”,verdana,arial,sans-serif;} #mermaid-svg-jSqaBO053TXsaXg6 {font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-jSqaBO053TXsaXg6 .error-icon{fill:#552222;}#mermaid-svg-jSqaBO053TXsaXg6 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-jSqaBO053TXsaXg6 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-jSqaBO053TXsaXg6 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-jSqaBO053TXsaXg6 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-jSqaBO053TXsaXg6 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-jSqaBO053TXsaXg6 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-jSqaBO053TXsaXg6 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-jSqaBO053TXsaXg6 .marker.cross{stroke:#333333;}#mermaid-svg-jSqaBO053TXsaXg6 svg{font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-jSqaBO053TXsaXg6 .label{font-family:“trebuchet ms”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-jSqaBO053TXsaXg6 .cluster-label text{fill:#333;}#mermaid-svg-jSqaBO053TXsaXg6 .cluster-label span{color:#333;}#mermaid-svg-jSqaBO053TXsaXg6 .label text,#mermaid-svg-jSqaBO053TXsaXg6 span{fill:#333;color:#333;}#mermaid-svg-jSqaBO053TXsaXg6 .node rect,#mermaid-svg-jSqaBO053TXsaXg6 .node circle,#mermaid-svg-jSqaBO053TXsaXg6 .node ellipse,#mermaid-svg-jSqaBO053TXsaXg6 .node polygon,#mermaid-svg-jSqaBO053TXsaXg6 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-jSqaBO053TXsaXg6 .node .label{text-align:center;}#mermaid-svg-jSqaBO053TXsaXg6 .node.clickable{cursor:pointer;}#mermaid-svg-jSqaBO053TXsaXg6 .arrowheadPath{fill:#333333;}#mermaid-svg-jSqaBO053TXsaXg6 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-jSqaBO053TXsaXg6 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-jSqaBO053TXsaXg6 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-jSqaBO053TXsaXg6 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-jSqaBO053TXsaXg6 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-jSqaBO053TXsaXg6 .cluster text{fill:#333;}#mermaid-svg-jSqaBO053TXsaXg6 .cluster span{color:#333;}#mermaid-svg-jSqaBO053TXsaXg6 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-jSqaBO053TXsaXg6 :root{–mermaid-font-family:“trebuchet ms”,verdana,arial,sans-serif;} #mermaid-svg-BxkT4sAhCu3f7WIl {font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-BxkT4sAhCu3f7WIl .error-icon{fill:#552222;}#mermaid-svg-BxkT4sAhCu3f7WIl .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-BxkT4sAhCu3f7WIl .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-BxkT4sAhCu3f7WIl .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-BxkT4sAhCu3f7WIl .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-BxkT4sAhCu3f7WIl .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-BxkT4sAhCu3f7WIl .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-BxkT4sAhCu3f7WIl .marker{fill:#333333;stroke:#333333;}#mermaid-svg-BxkT4sAhCu3f7WIl .marker.cross{stroke:#333333;}#mermaid-svg-BxkT4sAhCu3f7WIl svg{font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-BxkT4sAhCu3f7WIl .label{font-family:“trebuchet ms”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-BxkT4sAhCu3f7WIl .cluster-label text{fill:#333;}#mermaid-svg-BxkT4sAhCu3f7WIl .cluster-label span{color:#333;}#mermaid-svg-BxkT4sAhCu3f7WIl .label text,#mermaid-svg-BxkT4sAhCu3f7WIl span{fill:#333;color:#333;}#mermaid-svg-BxkT4sAhCu3f7WIl .node rect,#mermaid-svg-BxkT4sAhCu3f7WIl .node circle,#mermaid-svg-BxkT4sAhCu3f7WIl .node ellipse,#mermaid-svg-BxkT4sAhCu3f7WIl .node polygon,#mermaid-svg-BxkT4sAhCu3f7WIl .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-BxkT4sAhCu3f7WIl .node .label{text-align:center;}#mermaid-svg-BxkT4sAhCu3f7WIl .node.clickable{cursor:pointer;}#mermaid-svg-BxkT4sAhCu3f7WIl .arrowheadPath{fill:#333333;}#mermaid-svg-BxkT4sAhCu3f7WIl .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-BxkT4sAhCu3f7WIl .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-BxkT4sAhCu3f7WIl .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-BxkT4sAhCu3f7WIl .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-BxkT4sAhCu3f7WIl .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-BxkT4sAhCu3f7WIl .cluster text{fill:#333;}#mermaid-svg-BxkT4sAhCu3f7WIl .cluster span{color:#333;}#mermaid-svg-BxkT4sAhCu3f7WIl div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-BxkT4sAhCu3f7WIl :root{–mermaid-font-family:“trebuchet ms”,verdana,arial,sans-serif;}