做网站收费 知乎个体工商户备案网站备案

做网站收费 知乎,个体工商户备案网站备案,微信小程序投票怎么做,wordpress发帖时间二叉树是一种非线性数据结构#xff0c;二叉树的基本单元是节点#xff0c;每个节点包含值、左子节点引用和右子节点引用。在二叉树中#xff0c;除叶节点外#xff0c;其他所有节点都包含子节点和非空子树。二叉树的常见术语包括一下几个#xff1a; 根节点#xff1a;位…二叉树是一种非线性数据结构二叉树的基本单元是节点每个节点包含值、左子节点引用和右子节点引用。在二叉树中除叶节点外其他所有节点都包含子节点和非空子树。二叉树的常见术语包括一下几个根节点位于二叉树顶层的节点没有父节点。叶节点没有子节点的节点其两个指针均指向 None 。边连接两个节点的线段即节点引用指针。节点所在的层从顶至底递增根节点所在层为 1 。节点的度节点的子节点的数量。在二叉树中度的取值范围是 0、1、2 。二叉树的高度从根节点到最远叶节点所经过的边的数量。节点的深度从根节点到该节点所经过的边的数量。节点的高度从距离该节点最远的叶节点到该节点所经过的边的数量。二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。1层次遍历从顶部到底部逐层遍历二叉树并在每一层按照从左到右的顺序访问节点。层序遍历本质上属于广度优先搜索BFS它体现了一种“一圈一圈向外扩展”的逐层遍历方式。广度优先搜索通常借助“队列”来实现/* 层序遍历 */ListIntegerlevelOrder(TreeNoderoot){// 初始化队列加入根节点QueueTreeNodequeuenewLinkedList();queue.add(root);// 初始化一个列表用于保存遍历序列ListIntegerlistnewArrayList();while(!queue.isEmpty()){TreeNodenodequeue.poll();// 队列出队list.add(node.val);// 保存节点值if(node.left!null)queue.offer(node.left);// 左子节点入队if(node.right!null)queue.offer(node.right);// 右子节点入队}returnlist;}前序、中序和后序遍历都属于深度优先搜索DFS它体现了一种“先走到尽头再回溯继续”的遍历方式。深度优先搜索通常基于递归实现/* 前序遍历 */voidpreOrder(TreeNoderoot){if(rootnull)return;// 访问优先级根节点 - 左子树 - 右子树list.add(root.val);preOrder(root.left);preOrder(root.right);}/* 中序遍历 */voidinOrder(TreeNoderoot){if(rootnull)return;// 访问优先级左子树 - 根节点 - 右子树inOrder(root.left);list.add(root.val);inOrder(root.right);}/* 后序遍历 */voidpostOrder(TreeNoderoot){if(rootnull)return;// 访问优先级左子树 - 右子树 - 根节点postOrder(root.left);postOrder(root.right);list.add(root.val);}二叉树不仅可以用链表实现数组同样可以实现。若某节点的索引为 i 则该节点的左子节点索引为 2I1右子节点索引为 2I2。二叉搜索树基于二叉树同时要满足对于根节点左子树中所有节点的值小于根节点的值 小于右子树中所有节点的值并且任意节点的左右子树也满足这个条件。1二叉搜索树的查找和二分查找算法原理一致都是每轮排除一半情况循环次数最多为二叉树的高度二叉树的中序遍历遵循“左 根 右”的遍历顺序而二叉搜索树满足“左子节点 小于 根节点 小于右子节点”的大小关系因此二叉搜索树的中序遍历序列是升序的。利用中序遍历升序的性质我们在二叉搜索树中获取有序数据仅需 On时间无须进行额外的排序操作非常高效。/* 查找节点 */TreeNodesearch(intnum){TreeNodecurroot;// 循环查找越过叶节点后跳出while(cur!null){// 目标节点在 cur 的右子树中if(cur.valnum)curcur.right;// 目标节点在 cur 的左子树中elseif(cur.valnum)curcur.left;// 找到目标节点跳出循环elsebreak;}// 返回目标节点returncur;}2插入节点给定一个待插入元素 num 为了保持二叉搜索树“左子树 根节点 右子树”的性质与查找操作相似从根节点出发根据当前节点值和 num 的大小关系循环向下搜索直到越过叶节点遍历至 None 时跳出循环。在该位置插入节点初始化节点 num 将该节点置于 None 的位置。二叉搜索树不允许存在重复节点否则将违反其定义。因此若待插入节点在树中已存在则不执行插入直接返回。为了实现插入节点我们需要借助节点 pre 保存上一轮循环的节点。这样在遍历至 None 时我们可以获取到其父节点从而完成节点插入操作。/* 插入节点 */voidinsert(intnum){// 若树为空则初始化根节点if(rootnull){rootnewTreeNode(num);return;}TreeNodecurroot,prenull;// 循环查找越过叶节点后跳出while(cur!null){// 找到重复节点直接返回if(cur.valnum)return;precur;// 插入位置在 cur 的右子树中if(cur.valnum)curcur.right;// 插入位置在 cur 的左子树中elsecurcur.left;}// 插入节点TreeNodenodenewTreeNode(num);if(pre.valnum)pre.rightnode;elsepre.leftnode;}删除节点先在二叉树中查找到目标节点再将其删除。与插入节点类似我们需要保证在删除操作完成后二叉搜索树的“左子树 根节点 右子树”的性质仍然满足。因此我们根据目标节点的子节点数量分 0、1 和 2 三种情况执行对应的删除节点操作。当待删除节点的度为 0时表示该节点是叶节点可以直接删除。当待删除节点的度为 1时将待删除节点替换为其子节点即可。当待删除节点的度为 2 时我们无法直接删除它而需要使用一个节点替换该节点。由于要保持二叉搜索树“左子树 小于根节点 小于右子树”的性质因此这个节点可以是右子树的最小节点或左子树的最大节点。/* 删除节点 */voidremove(intnum){// 若树为空直接提前返回if(rootnull)return;TreeNodecurroot,prenull;// 循环查找越过叶节点后跳出while(cur!null){// 找到待删除节点跳出循环if(cur.valnum)break;precur;// 待删除节点在 cur 的右子树中if(cur.valnum)curcur.right;// 待删除节点在 cur 的左子树中elsecurcur.left;}// 若无待删除节点则直接返回if(curnull)return;// 子节点数量 0 or 1if(cur.leftnull||cur.rightnull){// 当子节点数量 0 / 1 时 child null / 该子节点TreeNodechildcur.left!null?cur.left:cur.right;// 删除节点 curif(cur!root){if(pre.leftcur)pre.leftchild;elsepre.rightchild;}else{// 若删除节点为根节点则重新指定根节点rootchild;}}// 子节点数量 2else{// 获取中序遍历中 cur 的下一个节点TreeNodetmpcur.right;while(tmp.left!null){tmptmp.left;}// 递归删除节点 tmpremove(tmp.val);// 用 tmp 覆盖 curcur.valtmp.val;}}