企业官网建设流程全解析

50个优秀网站,wordpress新建分类目录,百度的网址,网站建设伍金手指下拉3二叉排序树#xff08;Binary Search Tree, BST#xff09;是一种重要的数据结构#xff0c;具有良好的查找、插入和删除性能。以下是针对你提出的问题的详细解答#xff1a;1. 二叉排序树的查找算法#xff08;SearchBST#xff09; // 定义二叉树节点结构 typedef stru…二叉排序树Binary Search Tree, BST是一种重要的数据结构具有良好的查找、插入和删除性能。以下是针对你提出的问题的详细解答1. 二叉排序树的查找算法SearchBST// 定义二叉树节点结构typedefstructBSTNode{intdata;structBSTNode*left,*right;}BSTNode,*BSTree;/** * 在二叉排序树中查找关键字 key * param T: 当前树根节点 * param key: 要查找的关键字 * param father: 记录查找路径中的父节点用于插入时定位 * return: 找到返回该节点否则返回 NULL */BSTNode*SearchBST(BSTree T,intkey,BSTNode*father){if(TNULL)returnNULL;// 空树则未找到if(keyT-data)returnT;// 找到目标节点elseif(keyT-data)returnSearchBST(T-left,key,T);// 向左子树查找当前节点成为潜在父亲elsereturnSearchBST(T-right,key,T);// 向右子树查找当前节点成为潜在父亲}说明father参数通过递归传递记录最后访问的非空节点即插入位置的父节点便于后续插入操作。2. 二叉排序树的构造过程构造基于逐个插入元素的过程遵循以下规则若树为空则第一个节点为根对每个新元素从根开始比较小于当前节点 → 进入左子树大于当前节点 → 进入右子树直到遇到空指针位置进行插入。示例{46, 25, 54, 13, 29, 91}插入顺序操作46创建根节点2525 46 → 插入 46 的左子树5454 46 → 插入 46 的右子树1313 46 → 左13 25 → 插入 25 的左子树2929 46 → 左29 25 → 插入 25 的右子树9191 46 → 右91 54 → 插入 54 的右子树最终形成的树结构如下缩进表示层次46 / \ 25 54 / \ \ 13 29 913. 二叉排序树的插入算法InsertBST/** * 插入新关键字 newkey 到二叉排序树 * param root: 指向根节点的指针可能需要修改根 * param newkey: 新的关键字 * return: 成功返回 0已存在返回 -1 */intInsertBST(BSTree*root,intnewkey){BSTNode*parentNULL;BSTNode*foundSearchBST(*root,newkey,NULL);if(found!NULL)return-1;// 关键字已存在不允许重复// 创建新节点BSTNode*newNode(BSTNode*)malloc(sizeof(BSTNode));if(!newNode)return-1;// 内存分配失败newNode-datanewkey;newNode-leftnewNode-rightNULL;// 查找插入位置及其父节点BSTNode*current*root;parentNULL;while(current!NULL){parentcurrent;if(newkeycurrent-data)currentcurrent-left;elsecurrentcurrent-right;}// 插入新节点if(parentNULL){*rootnewNode;// 树为空新节点作为根}elseif(newkeyparent-data){parent-leftnewNode;}else{parent-rightnewNode;}return0;// 插入成功}注意使用双重指针BSTree* root是为了在根为空时能正确修改根节点。二叉排序树的特点总结特性说明有序性中序遍历可得有序序列支持高效查找平均时间复杂度查找/插入/删除O(log n)平衡情况下最坏情况当输入有序时退化为链表时间复杂度变为 O(n)结构依赖插入顺序不同插入顺序生成不同形状的树影响效率优化方向使用平衡二叉树如 AVL、红黑树避免退化要验证一棵二叉树是否为二叉排序树BST最有效的方法是利用其核心性质中序遍历的结果必须是一个严格递增的序列。✅ 验证方法基于中序遍历我们可以通过中序遍历二叉树并在访问节点时检查当前节点的值是否大于前一个访问的节点值。如果是则继续否则不是 BST。使用非递归或递归方式均可但关键是要维护“前驱节点”的值进行比较。 方法一递归 引用前驱值推荐#includestdio.h#includestdlib.h#includelimits.h// 二叉树节点定义typedefstructTreeNode{intval;structTreeNode*left;structTreeNode*right;}TreeNode;// 辅助函数判断是否为BSTboolisValidBSTHelper(TreeNode*root,long*prev){if(rootNULL)returntrue;// 左子树必须是BSTif(!isValidBSTHelper(root-left,prev))returnfalse;// 当前节点必须大于前一个节点值if(root-val*prev)returnfalse;*prevroot-val;// 更新前驱值// 右子树必须是BSTreturnisValidBSTHelper(root-right,prev);}/** * 判断是否为二叉排序树 * param root: 根节点 * return: 是返回 true否则返回 false */boolisValidBST(TreeNode*root){longprevLONG_MIN;// 初始化为最小长整型避免越界returnisValidBSTHelper(root,prev);}说明使用long类型防止int最小值被误判。prev记录中序遍历过程中上一个访问节点的值。所有节点必须满足当前值 prev即严格递增。 方法二中序遍历存数组后判断有序性简单直观voidinorder(TreeNode*root,int*arr,int*idx){if(rootNULL)return;inorder(root-left,arr,idx);arr[(*idx)]root-val;inorder(root-right,arr,idx);}boolisSorted(int*arr,intn){for(inti1;in;i)if(arr[i]arr[i-1])returnfalse;returntrue;}boolisValidBST_Array(TreeNode*root){intarr[10000],idx0;inorder(root,arr,idx);returnisSorted(arr,idx);}缺点需要额外 O(n) 空间效率较低适合教学理解。⚠️ 注意事项必须是“严格递增”不允许相等除非题目允许重复元素且规定右子树 ≥ 根。不能只比较父子关系例如5 / \ 3 8 / \ 2 6 / 4虽然每个父节点与子节点满足大小关系但左子树中的4 5却出现在右分支中 —— 实际上这棵树仍是合法的不此例需具体分析路径上下界 更高级写法可用带上下界的递归来处理跨层约束。 带上下界的递归验证法更严谨boolvalidate(TreeNode*node,longminVal,longmaxVal){if(nodeNULL)returntrue;if(node-valminVal||node-valmaxVal)returnfalse;returnvalidate(node-left,minVal,node-val)validate(node-right,node-val,maxVal);}boolisValidBST_Bound(TreeNode*root){returnvalidate(root,LONG_MIN,LONG_MAX);}此方法可防止某些“局部满足但全局违反”的情况。