网站前端设计要做什么做网站业务的怎么寻找客户

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

网站前端设计要做什么,做网站业务的怎么寻找客户,软件项目管理的内容,营销工具一、前置说明 在学习二叉树的基本操作前#xff0c;需先要创建一棵二叉树#xff0c;然后才能学习其相关的基本操作。为了降低大家学习成本#xff0c;此处手动快速创建一棵简单的二叉树#xff0c;快速进入二叉树操作学习。 typedef char BTDataType;typedef struct Binar…一、前置说明 在学习二叉树的基本操作前需先要创建一棵二叉树然后才能学习其相关的基本操作。为了降低大家学习成本此处手动快速创建一棵简单的二叉树快速进入二叉树操作学习。 typedef char BTDataType;typedef struct BinaryTreeNode {BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right; }BTNode;// 动态申请一个新节点 BTNode* BuyNode(BTDataType x) {BTNode* newnode (BTNode)malloc(sizeof(BTNode));assert(newnode);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; } 注意上述代码并不是创建二叉树的方式。 二、构建二叉树 // 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树 BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi) {if (*pi n){return NULL;}char ch a[*pi];(pi);if (ch #){return NULL;}BTNode newNode (BTNode)malloc(sizeof(BTNode));newNode-data ch;newNode-left BinaryTreeCreate(a, n, pi);newNode-right BinaryTreeCreate(a, n, pi);return newNode; } 三、二叉树的遍历 学习二叉树结构最简单的方式就是遍历。所谓二叉树遍历 (Traversal) 是按照某种特定的规则依次对二叉 树中的节点进行相应的操作并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。 二叉树的遍历方式主要有四种先介绍三种最后再介绍第四种。利用了分治的思想 前序遍历 (Preorder Traversal 亦称先序遍历)方式为先遍历根结点左子树右子树。中序遍历 (Inorder Traversal)方式为先遍历左子树根结点右子树。后序遍历 (Postorder Traversal)方式为先遍历左子树右子树根结点。 // 二叉树前序遍历 void PreOrder(BTNode root); // 二叉树中序遍历 void InOrder(BTNode* root); // 二叉树后序遍历 void PostOrder(BTNode* root); 其中这三种遍历方式一般都用递归进行实现。 由于被访问的结点必是某子树的根所以 N(Node、L(Left subtree和 R(Right subtree又可解释为 根、根的左子树和根的右子树。NLR、LNR 和 LRN分别又称为先根遍历、中根遍历和后根遍历。 注意 1️⃣ 深度优先遍厉前序遍厉、中序遍厉、后序遍厉注意有些说法只认同前序遍厉。 2️⃣ 广度优先遍厉层序遍厉。 1、前序遍历 按照前序遍历的方式我们应该先遍历根结点 A然后再去遍历左子树。当进入左子树后我们需要再执行前序遍历方式即遍历 A 的左子树中的根结点 B然后再遍历 B 的左子树。当我们再进入左子树又是先遍历根结点D然后又遍历左子树按照顺序遍历到 R此时终于完成根结点左子树接下来遍历右子树。进入右子树后又遍历根结点T… …所以这种遍历方式属于递归性质的。遍历顺序为A–B–D–R–T–E–Y–C–Q–U–W // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) // 根-左子树-右子树 {if (root NULL){printf(# ); // 用#代表NULLreturn;}printf(%c , root-data);BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right); } 【递归图解】 2、中序遍历 中序遍历方式为左子树根结点右子树。仍以上面的图为例遍历顺序为 R–D–T–B–E–Y–A–Q–U–C–W // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root)// 左子树-根-右子树 {if (root NULL){printf(# );return;}BinaryTreeInOrder(root-left);printf(%c , root-data);BinaryTreeInOrder(root-right); } 3、后序遍历 后序遍历方式为 左子树右子树根结点。仍以上面的图为例遍历顺序应该为 R–T–D–Y–E–B–U–Q–W–C–A // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) // 左子树-右子树-根 {if (root NULL){printf(# );return;}BinaryTreePostOrder(root-left);BinaryTreePostOrder(root-right);printf(%c , root-data); } 【总结】  前序遍历结果1-2-3-4-5-6 中序遍历结果3-2-1-5-4-6 后序遍历结果3-2-5-6-4-1 4、层序遍历 层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。 设二叉树的根节点所在层数为 1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第 2 层上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 // 层序遍历 void LevelOrder(BTNode* root); 注意层序遍历一般需要使用队列。 队列内容前面已经详细介绍过了 【思路】先让根入队列然后再让根出队列当左子树不为 NULL 时让左子树入队列当右子树不为NULL时让右子树入队列然后不断地迭代下去直至队列为空。记得出队列前要保存当前值来访问到该元素Pop 到队列当中的值是地址通过该地址来访问其中的 data。 层序遍历结果为 3-4-3-8-6-6-7 我们该如何利用队列实现呢 判断当前队列是否为空。队列为空结束队列非空取出队列第一个元素入队列。上一层出来后再入下一层即它的左右孩子节点。   ​ 由于前面已经对队列的各种操作进行了详解这里就不展开讲了。直接运用之前写的 Queue.c 和 Queue.h // 层序遍历 void BinaryTreeLevelOrder(BTNode* root) {Queue q;QueueInit(q);if (root) // 树的根节点root不为空 将根节点入队列{QueuePush(q, root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q); // 获取队列头部元素printf(%c , front-data); // 打印节点值QueuePop(q); // 出队列// 如果当前树根的左右孩子不为空 则分别入队列if (front-left){QueuePush(q, front-left);}if (front-right){QueuePush(q, front-right);}}printf(\n);QueueDestroy(q); } ​ 四、二叉树其它接口的实现 1、二叉树的节点个数 按照递归的思想计算二叉树的节点数量我们可以认为 二叉树的节点个数  左子树数量 右子树数量 1其中 1 是当前根节点数量前提条件是存在根节点。 ⚪【思想 1】 迭代使用栈来模拟递归的过程用全局变量 / 静态局部变量来记录节点个数遍历二叉树的所有节点并累加节点的个数。 ⚪【思想 2】 递归利用分治的思想函数使用带返回值的方式其内部的递归本质上是一个后序遍厉左子树-右子树-根节点。 // 二叉树节点个数 int BinaryTreeSize(BTNode* root) {return root NULL ? 0 : BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1; } ​ 2、二叉树叶子节点个数 按照递归的思想计算二叉树的叶子节点数量我们可以认为 叶子节点个数 左子树叶子节点个数 右子树叶子节点个数 00 是因为当前根结点有子树说明根结点不是叶子结点。 ⚪【思想】 以 left 和 right 为标志如果都为 NULL则说明该节点是叶子节点。 // 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root) {// 先判断当前访问的节点是否为空if (root NULL) {return 0;}// 当前节点不为空它的左右孩子都为空说明该节点是叶子节点if (root-left NULL root-right NULL){return 1;}// 当前节点不为空左右孩子不都为空则继续往下遍历return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right); } ​ 3、二叉树第k层节点个数 ⚪【思想】 求当前树的第 k 层节点个数 左子树的第 k-1 层节点个数 右子树的第 k-1 层节点个数 (当 k1 时说明此层就是目标层) ​ // 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k) {assert(k 1);if (root NULL) // 先判断当前访问的节点是否为空{return 0;}if (k 1) // 当前节点不为空而k已经减到1了说明遍历到了第k层说明该节点是第k层的{return 1;}// 还没有遍历到第k层我们就继续往下遍历return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1); } 如何知道这个节点是不是第 k 层的 求二叉树第 k 层的节点个数我们从根节点开始往下遍历按根-左-右的顺序每遍历一次 k 就减 1一次当 k1 时说明我们遍历到了第 k 层此时访问该层的节点。如果它不为空则二叉树第 k 层的节点个数就要 1。 4、二叉树查找值为x的节点 ⚪【思想】 按照递归思想先判断当前结点是否是目标节点然后查找左子树再查找右子树。 如果左右子树都没有找到就返回NULL。 // 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {if (root NULL) // 先判断当前访问的节点是否为空{return NULL;}if (root-data x) // 判断要找的x值节点是不是当前节点{return root;}// 不是当前节点则继续去该节点的左子树中找BTNode* ret1 BinaryTreeFind(root-left, x);if (ret1){return ret1;}// 还没找到再继续去该节点的右子树中找BTNode* ret2 BinaryTreeFind(root-right, x);if (ret2){return ret2;}return NULL; // 当前节点及其左右子树中都没找到返回NULL } 5、销毁二叉树 // 二叉树销毁 void BinaryTreeDestory(BTNode** root) {// 如果使用前中序遍历销毁节点会先被销毁变成随机值就不知道它的左右子树位置了 所以采用后序遍历销毁if (*root NULL){return;}BinaryTreeDestory(((*root)-left));BinaryTreeDestory(((*root)-right));free(*root);root NULL; // 将根节点设置为NULL 防止野指针 } 注意如果这里使用前序遍历或中序遍历进行销毁节点会先被销毁变成随机值就不知道它的左右子树位置了所以应该采用后序遍历来销毁二叉树。 如果这里传进来的是一级指针由于要在函数内改变形参的值无法改变外部实参的值所以我们需要在函数外置头节点指针为NULL。 6、判断二叉树是否是完全二叉树 ⚪【思想】 层序遍历时把空节点也入队列。 完全二叉树中非空节点是连续的则空节点是连续的。非完全二叉树中非空节点不是连续的则空节点不是连续的。 所以在出队时判断一下出到第一个空节点时跳出循环 在下面重新写一个循环继续出队并检查出队元素 如果第一个空节点后面的全是空节点说明是完全二叉树。如果第一个空节点后面的有非空节点说明是非完全二叉树。 ​ // 判断二叉树是否是完全二叉树利用层序遍历的思想来判断 int BinaryTreeComplete(BTNode root) {Queue q;QueueInit(q);if (root) // 树的根节点root不为空 将根节点入队列{QueuePush(q, root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q); // 获取队列头部元素QueuePop(q); //出队列if (front){// 不管当前树根的左右孩子是否为空都分别入队列QueuePush(q, front-left);QueuePush(q, front-right);}else{break; //遇到空后跳出层序遍历}}// 如果后面全是空则是完全二叉树否则不是完全二叉树while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front){QueueDestroy(q);return false;}}QueueDestroy(q);return true; // 出队的节点中如果没有出现非空节点说明是完全二叉树出队的节点中如果没有出现非空节点说明是完全二叉树 }五、代码整合 1、Queue.h // Queue.h #pragma once#include stdio.h #include stdlib.h #include assert.h #include stdbool.hstruct BinaryTreeNode;typedef struct BinaryTreeNode* QDataType;typedef struct QueueNode {struct QueueNode* next;QDataType data; }QNode;typedef struct Queue {QNode* head;QNode* tail; }Queue;void QueueInit(Queue* pq); void QueueDestroy(Queue* pq); void QueuePush(Queue* pq, QDataType x); void QueuePop(Queue* pq); QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); int QueueSize(Queue* pq); bool QueueEmpty(Queue* pq); 2、Queue.c // Queue.c #define _CRT_SECURE_NO_WARNINGS 1#include Queue.hvoid QueueInit(Queue* pq) {assert(pq);pq-head pq-tail NULL; }void QueueDestroy(Queue* pq) {assert(pq);QNode* cur pq-head;while (cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL; }void QueuePush(Queue* pq, QDataType x) {assert(pq);QNode* newnode (QNode)malloc(sizeof(QNode));newnode-data x;newnode-next NULL;if (pq-head NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;} }void QueuePop(Queue pq) {assert(pq);assert(!QueueEmpty(pq));QNode* next pq-head-next;free(pq-head);pq-head next;if (pq-head NULL){pq-tail NULL;} }QDataType QueueFront(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));return pq-head-data; }QDataType QueueBack(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));return pq-tail-data; }int QueueSize(Queue* pq) {assert(pq);int n 0;QNode* cur pq-head;while (cur){n;cur cur-next;}return n; }bool QueueEmpty(Queue* pq) {assert(pq);return pq-head NULL; } 3、test.c // test.c #define _CRT_SECURE_NO_WARNINGS 1#include Queue.htypedef char BTDataType; typedef struct BinaryTreeNode {BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right; }BTNode;//动态申请一个新节点 BTNode* BuyNode(BTDataType x) {BTNode* newnode (BTNode)malloc(sizeof(BTNode));assert(newnode);newnode-data x;newnode-left NULL;newnode-right NULL;return newnode; }// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树 BTNode BinaryTreeCreate(BTDataType* a, int n, int* pi) {if (*pi n){return NULL;}char ch a[*pi];(pi);if (ch #){return NULL;}BTNode newNode (BTNode)malloc(sizeof(BTNode));newNode-data ch;newNode-left BinaryTreeCreate(a, n, pi);newNode-right BinaryTreeCreate(a, n, pi);return newNode; }// 二叉树节点个数 int BinaryTreeSize(BTNode root) {return root NULL ? 0 : BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1; }// 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root) {// 先判断当前访问的节点是否为空if (root NULL) {return 0;}// 当前节点不为空它的左右孩子都为空说明该节点是叶子节点if (root-left NULL root-right NULL){return 1;}// 当前节点不为空左右孩子不都为空则继续往下遍历return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right); }// 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k) {assert(k 1);if (root NULL) // 先判断当前访问的节点是否为空{return 0;}if (k 1) // 当前节点不为空而k已经减到1了说明遍历到了第k层说明该节点是第k层的{return 1;}// 还没有遍历到第k层我们就继续往下遍历return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1); }// 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {if (root NULL) // 先判断当前访问的节点是否为空{return NULL;}if (root-data x) // 判断要找的x值节点是不是当前节点{return root;}// 不是当前节点则继续去该节点的左子树中找BTNode* ret1 BinaryTreeFind(root-left, x);if (ret1){return ret1;}// 还没找到再继续去该节点的右子树中找BTNode* ret2 BinaryTreeFind(root-right, x);if (ret2){return ret2;}return NULL; // 当前节点及其左右子树中都没找到返回NULL }// 二叉树销毁 void BinaryTreeDestory(BTNode** root) {// 如果使用前中序遍历销毁节点会先被销毁变成随机值就不知道它的左右子树位置了 所以采用后序遍历销毁if (*root NULL){return;}BinaryTreeDestory(((*root)-left));BinaryTreeDestory(((*root)-right));free(*root);root NULL; // 将根节点设置为NULL 防止野指针 }// 二叉树前序遍历 void BinaryTreePrevOrder(BTNode root) // 根-左子树-右子树 {if (root NULL){printf(# ); // 用#代表NULLreturn;}printf(%c , root-data);BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right); }// 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root)// 左子树-根-右子树 {if (root NULL){printf(# );return;}BinaryTreeInOrder(root-left);printf(%c , root-data);BinaryTreeInOrder(root-right); }// 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) // 左子树-右子树-根 {if (root NULL){printf(# );return;}BinaryTreePostOrder(root-left);BinaryTreePostOrder(root-right);printf(%c , root-data); }// 层序遍历 void BinaryTreeLevelOrder(BTNode* root) {Queue q;QueueInit(q);if (root) // 树的根节点root不为空 将根节点入队列{QueuePush(q, root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q); // 获取队列头部元素printf(%c , front-data); // 打印节点值QueuePop(q); // 出队列// 如果当前树根的左右孩子不为空 则分别入队列if (front-left){QueuePush(q, front-left);}if (front-right){QueuePush(q, front-right);}}printf(\n);QueueDestroy(q); }// 判断二叉树是否是完全二叉树利用层序遍历的思想来判断 int BinaryTreeComplete(BTNode* root) {Queue q;QueueInit(q);if (root) // 树的根节点root不为空 将根节点入队列{QueuePush(q, root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q); // 获取队列头部元素QueuePop(q); //出队列if (front){// 不管当前树根的左右孩子是否为空都分别入队列QueuePush(q, front-left);QueuePush(q, front-right);}else{break; //遇到空后跳出层序遍历}}// 如果后面全是空则是完全二叉树否则不是完全二叉树while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front){QueueDestroy(q);return false;}}QueueDestroy(q);return true; // 出队的节点中如果没有出现非空节点说明是完全二叉树出队的节点中如果没有出现非空节点说明是完全二叉树 }int main() {BTDataType a[] { A, B, D, #, #, E, #, H, #, #, C, F, #, #, G, #, # };int n sizeof(a) / sizeof(a[0]) - 1; // 减去末尾的\0int pos 0;BTNode* root BinaryTreeCreate(a, n, pos); // 构建二叉树printf(TreeSize:%d\n, BinaryTreeSize(root)); // 二叉树节点个数printf(TreeLeafSize:%d\n, BinaryTreeLeafSize(root)); // 二叉树叶子节点个数printf(Tree2LevelSize:%d\n, BinaryTreeLevelKSize(root, 2)); // 二叉树第k层节点个数printf(TreeFindB:%p\n, BinaryTreeFind(root, B)); // 二叉树查找值为x的节点// 前序遍历BinaryTreePrevOrder(root);printf(\n);// 中序遍历BinaryTreeInOrder(root);printf(\n);// 后序遍历BinaryTreePostOrder(root);printf(\n);BinaryTreeLevelOrder(root); // 层序遍历printf(TreeComplete:%d\n, BinaryTreeComplete(root)); // 判断二叉树是否是完全二叉树BinaryTreeDestory(root);// 二叉树销毁printf(二叉树已销毁\n);return 0; } 六、程序运行整体效果