下载文档原格式
二叉排序树1．二叉排序树定义二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值。
（2）左右子树也都是二叉排序树，如图6-2所示。
2．二叉排序树的查找过程由其定义可见，二叉排序树的查找过程为：（1）若查找树为空，查找失败。
（2）查找树非空，将给定值key与查找树的根结点关键码比较。
（3）若相等，查找成功，结束查找过程，否则：①当给值key小于根结点关键码，查找将在以左孩子为根的子树上继续进行，转（1）。
②当给值key大于根结点关键码，查找将在以右孩子为根的子树上继续进行，转（1）。
3．二叉排序树插入操作和构造一棵二叉排序树向二叉排序树中插入一个结点的过程：设待插入结点的关键码为key，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，该插入结点已存在，不用插入；查找不成功时，则插入之。
因此，新插入结点一定是作为叶子结点添加上去的。
构造一棵二叉排序树则是逐个插入结点的过程。
对于关键码序列为：｛63，90，70，55，67，42，98，83，10，45，58｝，则构造一棵二叉排序树的过程如图6-3所示。
4．二叉排序树删除操作从二叉排序树中删除一个结点之后，要求其仍能保持二叉排序树的特性。
设待删结点为*p（p为指向待删结点的指针），其双亲结点为*f，删除可以分三种情况，如图6-4所示。
（1）*p结点为叶结点，由于删去叶结点后不影响整棵树的特性，所以，只需将被删结点的双亲结点相应指针域改为空指针，如图6-4（a）所示。
（2）*p结点只有右子树或只有左子树，此时，只需将或替换*f结点的*p子树即可，如图6-4（b）、（c）所示。
（3）*p结点既有左子树又有右子树，可按中序遍历保持有序地进行调整，如图6-4（d）、（e）所示。
设删除*p结点前，中序遍历序列为：① P为F的左子女时有：…，Pi子树，P，Pj，S子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，F，…。
二叉排序树的实验报告二叉排序树的实验报告引言：二叉排序树（Binary Search Tree，简称BST）是一种常用的数据结构，它将数据按照一定的规则组织起来，便于快速的查找、插入和删除操作。
本次实验旨在深入了解二叉排序树的原理和实现，并通过实验验证其性能和效果。
一、实验背景二叉排序树是一种二叉树，其中每个节点的值大于其左子树的所有节点的值，小于其右子树的所有节点的值。
这种特性使得在二叉排序树中进行查找操作时，可以通过比较节点的值来确定查找的方向，从而提高查找效率。
二、实验目的1. 理解二叉排序树的基本原理和性质；2. 掌握二叉排序树的构建、插入和删除操作；3. 验证二叉排序树在查找、插入和删除等操作中的性能和效果。
三、实验过程1. 构建二叉排序树首先，我们需要构建一个空的二叉排序树。
在构建过程中，我们可以选择一个节点作为根节点，并将其他节点插入到树中。
插入节点时，根据节点的值与当前节点的值进行比较，如果小于当前节点的值，则将其插入到当前节点的左子树中；如果大于当前节点的值，则将其插入到当前节点的右子树中。
重复这个过程，直到所有节点都被插入到树中。
2. 插入节点在已有的二叉排序树中插入新的节点时，我们需要遵循一定的规则。
首先，从根节点开始，将新节点的值与当前节点的值进行比较。
如果小于当前节点的值，则将其插入到当前节点的左子树中；如果大于当前节点的值，则将其插入到当前节点的右子树中。
如果新节点的值与当前节点的值相等，则不进行插入操作。
3. 删除节点在二叉排序树中删除节点时，我们需要考虑不同的情况。
如果要删除的节点是叶子节点，即没有左右子树，我们可以直接删除该节点。
如果要删除的节点只有一个子树，我们可以将子树连接到要删除节点的父节点上。
如果要删除的节点有两个子树，我们可以选择将其右子树中的最小节点或左子树中的最大节点替代该节点，并删除相应的替代节点。
四、实验结果通过对二叉排序树的构建、插入和删除操作的实验，我们得到了以下结果：1. 二叉排序树可以高效地进行查找操作。
二叉排序树（Binary Search Tree，简称BST）是一种特殊的二叉树，它的每个节点的值满足以下性质：
1.左子树上所有节点的值均小于根节点的值。
2.右子树上所有节点的值均大于根节点的值。
3.左、右子树也分别为二叉排序树。
为了删除一个节点，我们首先需要找到需要删除的节点，然后按照一定的规则替换这个节点，以保持二叉排序树的性质。
以下是二叉排序树的删除算法：1.查找要删除的节点：从根节点开始，按照二叉排序树的性质查找要删除的
节点。
2.删除节点：
o如果要删除的节点是叶子节点（没有左右子节点），直接删除即可。
o如果要删除的节点只有一个子节点，用它的子节点替换它。
o如果要删除的节点有两个子节点，找到它的前驱节点或后继节点（根据二叉排序树的性质），用前驱节点或后继节点替换它，然后删除前
驱节点或后继节点。
3.调整树：根据需要，对树进行调整，以保持二叉排序树的性质。
需要注意的是，在删除节点时，需要小心处理左右子节点的边界情况。
如果一个节点的左子节点为空，那么它的左子节点就是它的前驱节点；如果它的右子节点为空，那么它的右子节点就是它的后继节点。
二叉排序树查找的递归算法介绍二叉排序树（Binary Search Tree），也称二叉查找树、有序二叉树或排序二叉树，是一种常用的数据结构。
它具有以下特点：•每个节点都包含一个键值和对应的数据。
•左子树中的所有节点的键值都小于根节点的键值。
•右子树中的所有节点的键值都大于根节点的键值。
•左右子树也分别是二叉排序树。
二叉排序树支持高效的查找、插入和删除操作，其中查找操作是利用递归实现的。
本文将详细介绍二叉排序树查找的递归算法。
二叉排序树的定义二叉排序树的定义如下：class TreeNode:def __init__(self, key, data):self.key = keyself.data = dataself.left = Noneself.right = Noneclass BinarySearchTree:def __init__(self):self.root = None在二叉排序树中，每个节点都是一个TreeNode对象，包含键值key和对应的数据data。
left和right分别指向左子树和右子树的根节点。
树的根节点由BinarySearchTree对象的root属性表示。
二叉排序树查找的递归算法二叉排序树的查找操作是利用递归实现的，其具体算法如下：1.如果待查找的键值等于当前节点的键值，返回当前节点的数据。
2.如果待查找的键值小于当前节点的键值，递归在左子树中查找。
3.如果待查找的键值大于当前节点的键值，递归在右子树中查找。
4.如果在左子树或右子树中找不到对应的键值，则返回空。
下面是二叉排序树查找的递归算法的代码实现：def search_recursive(node, key):if node is None or node.key == key:return node.dataelif key < node.key:return search_recursive(node.left, key)else:return search_recursive(node.right, key)在上述代码中，node表示当前节点，key表示待查找的键值。
以二叉树或树作为表的组织形式，称为树表，它是一类动态查找表，不仅适合于数据查找，也适合于表插入和删除操作。
常见的树表：二叉排序树平衡二叉树B-树B+树9.3.1 二叉排序树二叉排序树（简称BST）又称二叉查找（搜索）树，其定义为：二叉排序树或者是空树，或者是满足如下性质（BST性质）的二叉树：❶若它的左子树非空，则左子树上所有节点值（指关键字值）均小于根节点值；❷若它的右子树非空，则右子树上所有节点值均大于根节点值；❸左、右子树本身又各是一棵二叉排序树。
注意：二叉排序树中没有相同关键字的节点。
二叉树结构满足BST性质：节点值约束二叉排序树503080209010854035252388例如:是二叉排序树。
66不试一试二叉排序树的中序遍历序列有什么特点？二叉排序树的节点类型如下：typedef struct node{KeyType key;//关键字项InfoType data;//其他数据域struct node*lchild,*rchild;//左右孩子指针}BSTNode;二叉排序树可看做是一个有序表，所以在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。
1、二叉排序树上的查找Nk< bt->keybtk> bt->key 每一层只和一个节点进行关键字比较！∧∧p查找到p所指节点若k<p->data，并且p->lchild=NULL，查找失败。
若k>p->data，并且p->rchild=NULL，查找失败。
查找失败的情况加上外部节点一个外部节点对应某内部节点的一个NULL指针递归查找算法SearchBST()如下（在二叉排序树bt上查找关键字为k的记录，成功时返回该节点指针，否则返回NULL）：BSTNode*SearchBST(BSTNode*bt,KeyType k){if(bt==NULL||bt->key==k)//递归出口return bt;if(k<bt->key)return SearchBST(bt->lchild,k);//在左子树中递归查找elsereturn SearchBST(bt->rchild,k);//在右子树中递归查找}在二叉排序树中插入一个关键字为k的新节点，要保证插入后仍满足BST性质。
平衡树——特点：所有结点左右子树深度差≤1排序树——特点：所有结点―左小右大字典树——由字符串构成的二叉排序树判定树——特点：分支查找树（例如12个球如何只称3次便分出轻重）带权树——特点：路径带权值（例如长度）最优树——是带权路径长度最短的树，又称Huffman树，用途之一是通信中的压缩编码。
1.1 二叉排序树：或是一棵空树；或者是具有如下性质的非空二叉树：（1）若左子树不为空，左子树的所有结点的值均小于根的值；（2）若右子树不为空，右子树的所有结点均大于根的值；（3）它的左右子树也分别为二叉排序树。
例：二叉排序树如图9.7：二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。
中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。
搜索,插入,删除的复杂度等于树高，期望O(logn),最坏O(n)(数列有序,树退化成线性表).虽然二叉排序树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉排序树可以使树高为O(logn),如SBT,AVL,红黑树等.故不失为一种好的动态排序方法.2.2 二叉排序树b中查找在二叉排序树b中查找x的过程为：1. 若b是空树，则搜索失败，否则：2. 若x等于b的根节点的数据域之值，则查找成功；否则：3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：4. 查找右子树。
[cpp]view plaincopyprint?1.Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){2. //在根指针T所指二叉排序樹中递归地查找其关键字等于key的数据元素，若查找成功，3. //则指针p指向该数据元素节点，并返回TRUE，否则指针P指向查找路径上访问的4. //最好一个节点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL5. if(!T){ p=f; return FALSE;} //查找不成功6. else if EQ(key, T->data.key) {P=T; return TRUE;} //查找成功7. else if LT(key,T->data.key)8. return SearchBST(T->lchild, key, T, p); //在左子树继续查找9. else return SearchBST(T->rchild, key, T, p); //在右子树继续查找10.}2.3 在二叉排序树插入结点的算法向一个二叉排序树b中插入一个结点s的算法，过程为：1. 若b是空树，则将s所指结点作为根结点插入，否则：2. 若s->data等于b的根结点的数据域之值，则返回，否则：3. 若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中，否则：4. 把s所指结点插入到右子树中。
《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。
问题分析：二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。
由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。
处理本问题，我觉得应该：1、建立二叉树；2、通过递归方法来遍历（先序、中序和后序）二叉树；3、通过队列应用来实现对二叉树的层次遍历；4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等；5、运用广义表对二叉树进行广义表形式的打印。
算法规定：输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。
输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。
对二叉树的一些运算结果以整型输出。
程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。
计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。
对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。
测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E预测结果：先序遍历ABCDEGF中序遍历CBEGDFA后序遍历CGEFDBA层次遍历ABCDEFG广义表打印A（B（C,D（E（,G）,F）））叶子数3 深度5 宽度2 非空子孙数6 度为2的数目2 度为1的数目2查找5，成功，查找的元素为E删除E后，以广义表形式打印A（B（C,D（,F）））输入二：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B预测结果：先序遍历ABDEHCFG中序遍历DBHEAGFC后序遍历DHEBGFCA层次遍历ABCDEFHG广义表打印A（B(D,E(H)),C(F(,G))）叶子数3 深度4 宽度3 非空子孙数7 度为2的数目2 度为1的数目3查找10，失败。
算法（平衡⼆叉树）科普⼆叉树⼆叉树⼆叉数是每个节点最多有两个⼦树,或者是空树(n=0),或者是由⼀个根节点及两个互不相交的,分别称为左⼦树和右⼦树的⼆叉树组成满⼆叉树有两个⾮空⼦树(⼆叉树中的每个结点恰好有两个孩⼦结点切所有叶⼦结点都在同⼀层)也就是⼀个结点要么是叶结点，要么是有两个⼦结点的中间结点。
深度为k且含有2^k-1个结点的⼆叉树完全⼆叉树从左到右依次填充从根结点开始，依次从左到右填充树结点。
除最后⼀层外，每⼀层上的所有节点都有两个⼦节点，最后⼀层都是叶⼦节点。
平衡⼆叉树AVL树[3,1,2,5,9,7]⾸先科普下⼆叉排序树⼜称⼆叉查找树,议程⼆叉搜索树⼆叉排序树的规则⽐本⾝⼤放右边,⽐本⾝⼩放左边平衡⼆叉数⾸先是⼀个⼆叉排序树左右两个⼦树的⾼度差不⼤于1下⾯图中是平衡的情况下⾯是不平衡的情况引⼊公式(LL)右旋function toateRight(AvlNode){let node=AvlNode.left;//保存左节点 AvlNode.left=node.right;node.right=AvlNode;}(RR)左旋function roateLeft(AvlNode){let node=AvlNode.right;//保存右⼦节点AvlNode.right=node.left;node.left=AvlNode;return node;}左右旋⼤图判断⼆叉树是不是平衡树⼆叉树任意结点的左右⼦树的深度不超过1深度计算定义⼀个初始化的⼆叉树var nodes = {node: 6,left: {node: 5,left: {node: 4},right: {node: 3}},right: {node: 2,right: {node: 1}}}//计算⾼度const treeDepth = (root) => {if (root == null) {return 0;}let left = treeDepth(root.left)let right = treeDepth(root.right)return 1+(left>right?left:right)}//判断深度const isTree=(root)=>{if (root == null) {return true;}let left=treeDepth(root.left)let right=treeDepth(root.right)let diff=left-right;if (diff > 1 || diff < -1) {return false}return isTree(root.left)&&isTree(root.right) }console.log(isTree(nodes))判断⼆叉数是不是搜索⼆叉树//第⼀种 //中序遍历let last=-Infinity;const isValidBST=(root)=>{if (root == null) {return true;}//先从左节点开始if (isValidBST(root.left)) {if (last < root.node) {last=root.node;return isValidBST(root.right)}}return false}console.log(isValidBST(nodes))//第⼆种const isValidBST = root => {if (root == null) {return true}return dfs(root, -Infinity, Infinity)}const dfs = (root, min, max) => {if (root == null) {return true}if (root.node <= min || root.node >= max) {return false}return dfs(root.left, min, root.node) && dfs(root.right, root.node, max)}console.log(isValidBST(nodes))实现⼀个⼆叉树实现了⼆叉树的添加,删除,查找,排序//⼆叉树结点class TreeNode {constructor(n, left, right){this.n = n;this.left = left;this.right = right;}}//⼆叉树class BinaryTree {constructor(){this.length = 0;this.root = null;this.arr = [];}//添加对外⼊⼝，⾸个参数是数组，要求数组⾥都是数字，如果有不是数字则试图转成数字，如果有任何⼀个⽆法强制转成数字，则本操作⽆效 addNode(){let arr = arguments[0];if(arr.length == 0) return false;return this.judgeData('_addNode', arr)}//删除结点deleteNode(){let arr = arguments[0];if(arr.length == 0) return false;return this.judgeData('_deleteNode', arr)}//传值判断，如果全部正确，则全部加⼊叉树judgeData(func, arr){let flag = false;//任何⼀个⽆法转成数字，都会失败if(arr.every(n => !Number.isNaN(n))){let _this = this;arr.map(n => _this[func](n));flag = true;}return flag;}//添加的真实实现_addNode(n){n = Number(n);let current = this.root;let treeNode = new TreeNode(n, null, null);if(this.root === null){this.root = treeNode;}else {current = this.root;while(current){let parent = current;if(n < current.n){current = current.left;if(current === null){parent.left = treeNode;}}else {current = current.right;if(current === null){parent.right = treeNode;}}}}this.length++;return treeNode;}//删除节点的真实实现_deleteNode(n){n = Number(n);if(this.root === null){return;}//查找该节点，删除节点操作⽐较复杂，为排除找不到被删除的节点的情况，简化代码，先保证该节点是存在的，虽然这样做其实重复了⼀次查询了，但⼆叉树的查找效率很⾼，这是可接受的let deleteNode = this.findNode(n);if(!deleteNode){return;}//如果删除的是根节点if(deleteNode === this.root){if(this.root.left === null && this.root.right === null){this.root = null;}else if(this.root.left === null){this.root = this.root.right;}else if(this.root.right === null){this.root = this.root.left;}else {let [replaceNode, replacePNode, rp] = this.findLeftTreeMax(deleteNode);replacePNode[rp] = null;replaceNode.left = this.root.left;replaceNode.right = this.root.right;this.root = replaceNode;}}else {//被删除的⽗节点，⼦节点在⽗节点的位置p，有left,right两种可能let [deleteParent, p] = this.findParentNode(deleteNode);if(deleteNode.left === null && deleteNode.right === null){deleteParent[p] = null;}else if(deleteNode.left === null){deleteParent[p] = deleteNode.right;}else if(deleteNode.right === null){deleteParent[p] = deleteNode.left;}else {//⽤来替换被删除的节点，⽗节点，节点在⽗节点的位置let [replaceNode, replacePNode, rp] = this.findLeftTreeMax(deleteNode);if(replacePNode === deleteNode){deleteParent[p] = replaceNode;}else {deleteParent[p] = replaceNode;replacePNode.right = null;}replacePNode[rp] = null;replaceNode.left = deleteNode.left;replaceNode.right = deleteNode.right;}}this.length--;}//查找findNode(n){let result = null;let current = this.root;while(current){if(n === current.n){result = current;break;}else if(n < current.n){current = current.left;}else {current = current.right;}}return result;}//查找⽗节点findParentNode(node){let [parent, child, p] = [null, null, null];if(this.root !== node){parent = this.root;if(node.n < parent.n){child = parent.left;p = 'left';}else {child = parent.right;p = 'right';}while(child){if(node.n === child.n){break;}else if(node.n < child.n){parent = child;child = parent.left;p = 'left';}else {parent = child;child = parent.right;p = 'right';}}}return [parent, p];}//查找当前有左⼦树的节点的最⼤值的节点M，如有A个节点被删除，M是最接近A点之⼀（还有⼀个是右⼦树节点的最⼩值） findLeftTreeMax(topNode){let [node, parent, p] = [null, null, null];if(this.root === null || topNode.left === null){return [node, parent, p];}parent = topNode;node = topNode.left;p = 'left';while(node.right){parent = node;node = node.right;p = 'right';}return [node, parent, p];}//查找最⼤值maxValue(){if(this.root !== null){return this._findLimit('right');}}//查找最⼩值minValue(){if(this.root !== null){return this._findLimit('left');}}//实现查找特殊值_findLimit(pro){let n = this.root.n;let current = this.root;while(current[pro]){current = current[pro];n = current.n;}return n;}//中序排序,并⽤数组的形式显⽰sortMiddleToArr(){this._sortMiddleToArr(this.root);return this.arr;}//中序⽅法_sortMiddleToArr(node){if(node !== null){this._sortMiddleToArr(node.left);this.arr.push(node.n);this._sortMiddleToArr(node.right);}}//打印⼆叉树对象printNode(){console.log(JSON.parse(JSON.stringify(this.root)));}}//测试var binaryTree = new BinaryTree();binaryTree.addNode([50, 24, 18, 65, 4, 80, 75, 20, 37, 40, 60]);binaryTree.printNode();//{n: 50, left: {…}, right: {…}}console.log(binaryTree.maxValue());//80console.log(binaryTree.minValue());//4console.log(binaryTree.sortMiddleToArr());// [4, 18, 20, 24, 37, 40, 50, 60, 65, 75, 80] binaryTree.deleteNode([50]);binaryTree.printNode();//{n: 40, left: {…}, right: {…}}排序复习function ArrayList() {this.array = [];}ArrayList.prototype = {constructor: ArrayList,insert: function(item) {this.array.push(item);},toString: function() {return this.array.join();},swap: function(index1, index2) {var aux = this.array[index2];this.array[index2] = this.array[index1];this.array[index1] = aux;},//冒泡排序bubbleSort: function() {var length = this.array.length;for (var i = 0; i < length; i++) {for (var j = 0; j < length - 1 - i; j++) {if (this.array[j] > this.array[j + 1]) {this.swap(j, j + 1);}}}},//选择排序selectionSort: function() {var length = this.array.length;var indexMin;for (var i = 0; i < length - 1; i++) {indexMin = i;for (var j = i; j < length; j++) {if (this.array[indexMin] > this.array[j]) {indexMin = j;}}if (indexMin !== i) {this.swap(indexMin, i);}}},//插⼊排序insertionSort: function() {var length = this.array.length;var j;var temp;for (var i = 1; i < length; i++) {temp = this.array[i];j = i;while (j > 0 && this.array[j - 1] > temp) {this.array[j] = this.array[j - 1];j--;}this.array[j] = temp;}},//归并排序mergeSort: function() {function mergeSortRec(array) {var length = array.length;if (length === 1) {return array;}var mid = Math.floor(length / 2);var left = array.slice(0, mid);var right = array.slice(mid, length);return merge(mergeSortRec(left), mergeSortRec(right)); }function merge(left, right) {var result = [];var il = 0;var ir = 0;while (il < left.length && ir < right.length) {if (left[il] < right[ir]) {result.push(left[il++]);} else {result.push(right[ir++]);}}while (il < left.length) {result.push(left[il++]);}while (ir < right.length) {result.push(right[ir++]);}return result;}this.array = mergeSortRec(this.array);},//快速排序quickSort:function(){function sort(array){if (array.length <= 1) {return array;}var pivotIndex = Math.floor(array.length/2);var pivot = array.splice(pivotIndex,1)[0];var left = [];var right = [];for(var i = 0; i < array.length; i++){if (array[i] < pivot) {left.push(array[i]);}else{right.push(array[i]);}}return sort(left).concat([pivot],sort(right));}this.array = sort(this.array);}};...................................................................................................................############################################################################ ###################################################################################。
实验三二叉排序树的建立和查找一、实验目的1．掌握二叉排序树的建立算法2．掌握二叉排序树查找算法。
二、实验环境操作系统和C语言系统三、预习要求复习二叉排序树的生成及查找算法，编写完整的程序。
四、实验内容实现二叉排序树上的查找算法。
具体实现要求：用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。
五、参考算法#include <stdio.h>#include <stdlib.h>typedef int InfoType;typedef int KeyType; /*假定关键字类型为整数*/typedef struct node /*结点类型*/{KeyType key; /*关键字项*/InfoType otherinfo; /*其它数据域，InfoType视应用情况而定，下面不处理它*/struct node *lchild,*rchild; /*左右孩子指针*/}BSTNode;typedef BSTNode *BSTree; /*BSTree是二叉排序树的类型*/BSTNode *SearchBST(BSTree T,KeyType key){ /*在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返回NULL*/if(T==NULL||key==T->key) /*递归的终结条件*/return T; /*若T为空，查找失败；否则成功，返回找到的结点位置*/if(key<T->key)return SearchBST(T->lchild,key);elsereturn SearchBST(T->rchild,key); /*继续在右子树中查找*/}void InsertBST(BSTree *T,int key){ /*插入一个值为key的节点到二叉排序树中*/BSTNode *p,*q;if((*T)==NULL){ /*树为空树*/(*T)=(BSTree)malloc(sizeof(BSTNode));(*T)->key=key;(*T)->lchild=(*T)->rchild=NULL;}else{p=(*T);while(p){q=p;if(p->key>key)p=q->lchild;else if(p->key<key)p=q->rchild;else{printf("\n 该二叉排序树中含有关键字为%d的节点!\n",key);return;}}p=(BSTree)malloc(sizeof(BSTNode));p->key=key;p->lchild=p->rchild=NULL;if(q->key>key)q->lchild=p;elseq->rchild=p;}}BSTree CreateBST(void){ /*输入一个结点序列，建立一棵二叉排序树，将根结点指针返回*/BSTree T=NULL; /*初始时T为空树*/KeyType key;scanf("%d",&key); /*读入一个关键字*/while(key){ /*假设key=0是输入结束标志*/ InsertBST(&T,key); /*将key插入二叉排序树T*/scanf("%d",&key); /*读入下一关键字*/}return T; /*返回建立的二叉排序树的根指针*/ }void ListBinTree(BSTree T) /*用广义表示二叉树*/{if(T!=NULL){printf("%d",T->key);if(T->lchild!=NULL||T->rchild!=NULL){printf("(");ListBinTree(T->lchild);if(T->rchild!=NULL)printf(",");ListBinTree(T->rchild);printf(")");}}}void main(){BSTNode *SearchBST(BSTree T,KeyType key);void InsertBST(BSTree *Tptr,KeyType key);BSTree CreateBST();void ListBinTree(BSTree T);BSTree T;BSTNode *p;int key;printf("请输入关键字（输入0为结束标志）：\n");T=CreateBST();ListBinTree(T);printf("\n");printf("请输入欲查找关键字:");scanf("%d",&key);p=SearchBST(T,key);if(p==NULL)printf("没有找到%d！\n",key);elseprintf("找到%d！\n",key);ListBinTree(p);printf("\n");}实验中出现的问题及对问题的解决方案输入数据时，总是不能得到结果，原因是在建立二叉树函数定义中，是对指针的值进行了修改。
韩山师范学院
实验题目：
二叉排序树的算法实现
班级：2015级软工班作者：黄俊聪
#include<iostream>
using namespace std;
#define ENDFLAG 0
typedefintKeyType;
typedefintInfoType;
typedefstructBSTNode
{
KeyType data;//每个结点的数据域包括关键字项和其他数据项
structBSTNode *lchild,*rchild;//左右孩子指针
InfoTypeotherinfo;//其他数据项
}BSTNode,*BSTree;
voidInsertBST(BSTree&T,int key)
{//当二叉排序树T中不存在关键字等于e.key的数据元素，则插入该元素BSTree S;
if(!T)
{//找到插入位置，递归结束
S=new BSTNode;//生成新结点*S
S->data=key;//新结点*S的数据域为e
S->lchild=S->rchild=NULL;//新结点*S作为叶子结点
T=S;//把新结点*S链接到已找到的插入位置
}
else if(key<T->data)
InsertBST(T->lchild,key);//将*S插入左子树
else if(key>T->data)
InsertBST(T->rchild,key);//将*S插入右子树
}
voidCreatBST(BSTree& T)
{
int key;
T=NULL;//将二叉排序树T初始化为空树
cout<<"请输入元素："<<endl;
cin>>key;
while(key!=ENDFLAG)//ENDFLAG为自定义常亮，作为输入结束标志
{
InsertBST(T,key);//将此结点插入二叉排序树T中
cin>>key;
}
cout<<"创建成功："<<endl;
}
voidDeleteBST(BSTree&T,KeyType key)
{
BSTreep,f,q,s;
p=T;
f=NULL;//初始化
/*------下面的while循环从根开始查找关键字等于key的结点*p--------*/ while(p)
{
if(p->data==key)
break;//找到关键字等于key的结点*p,结束循环
f=p;//*f为*p的双亲结点
if(p->data>key)
p=p->lchild;//在*P的左子树中继续查找
else
p=p->rchild;//在*P的右子树中继续查找
}
if(!p)
return;
/*---考虑3中情况实现P所指向子树内部的处理：*P左右子树均不空、无右子树、无左子树---*/
q=p;
if((p->lchild)&&(p->rchild))//被删除结点*P左右子树均不空
{
s=p->lchild;
while(s->rchild)//在*P的左子树中据需查找其前驱结点，即最右下结点
{
q=s;
s=s->rchild;//向右到尽头
}
p->data=s->data;//S指向被删除结点的"前驱"
if(q!=p)
q->rchild=s->lchild;//重接*q的右子树
else
q->lchild=s->lchild;//重接*q的左子树
delete s;
return;
}
else if(!p->rchild)//被删除结点*P无右子树，只需重接其左子树
{
p=p->lchild;
}
else if(!p->lchild)//被删结点*P无左子树，只需重接其右子树
{
p=p->rchild;
}
/*-----将P所指的子树挂接到其双亲结点*f相应的位置---*/
if(!f)
T=p;//被删除结点为根结点
else if(q==f->lchild)
f->lchild=p;//挂接到*f的左子树位置
else
f->rchild=p;//挂接到*f的右子树位置
delete q;
}
BSTreeSearchBST(BSTreeT,KeyType key)
{//在跟指针T所指二叉排序树中递归地查找某关键字等于key的数据元素//若查找成功，则返回指向改数据元素结点的指针，否则返回空指针if(!T||key==T->data)
return T;//查找结束
else if(key<T->data)
return SearchBST(T->lchild,key);//在左子树中继续查找else
return SearchBST(T->lchild,key);//在右子树中继续查找
}
void Print(BSTree T)
{
if(T)
{
Print(T->lchild);
cout<<"此时树为："<<T->data<<" "<<endl;
Print(T->rchild);
}
}
int main()
{
BSTree T;
int n;
int key;
cout<<"****1.创建****"<<endl;
cout<<"* 2.查找*"<<endl;
cout<<"* 3.插入*"<<endl;
cout<<"* 4.删除*"<<endl;
cout<<"* 5.输出*"<<endl;
cout<<"****6.结束****"<<endl;
cout<<"请输入要操作的功能序号："<<endl;
cin>>n;
while(1)
{
switch(n)
{
case 1:
CreatBST( T);
break;
case 2:
cout<<"请输入要查找的元素："<<endl;
cin>>key;
SearchBST(T,key);
cout<<"查找成功"<<endl;
break;
case 3:
cout<<"请输入要插入的元素："<<endl;
cin>>key;
InsertBST(T,key);
cout<<"插入成功"<<endl;
break;
case 4:
cout<<"请输入要删除的元素："<<endl;
cin>>key;
DeleteBST(T,key);
cout<<"删除成功"<<endl;
break;
case 5:
Print(T);
break;
case 6:
exit(0);
default:
cout<<"输入有误，请重新输入："<<endl;
}
cout<<"请输入要操作的功能序号："<<endl;
cin>>n;
}
}。
