对于二叉排序树的实现的实践成果报告

1对于二叉排序树的实现的实践成果报告一、二叉树序数算法的内容二叉排序树的实现，用顺序和二叉链表作存储结构。首先，以回车（’\n’）为输入结束标志，输入数列L，生成一棵二叉排序树T；然后，对二叉排序树T作中序遍历，输出结果；最后，输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历(执行操作2)；否则输出信息“无x”；二、算法流程1.用C++实现二叉排序树的源代码2.建立一个二叉树3.在一棵二叉排序树中插入一个数4.在一个二叉排序树查找一个数是否存在5.在一个二叉排序树删除一个给定的值6.显示一个二叉排序树7.删除一棵整二叉排序树8.进行对二叉树的基本操作三、算法的应用领域和作用1.基于二叉排序树的缓冲机制在污染源监控系统中的研究传统意义上的污染源在线自动监控系统的数据查询采用顺序查找法，由于其时间复杂度高，导致在数据量巨大的场合下效率低下。本文研究与实现基于二叉排序树的数据缓冲机制的污染源在线自动监控系统，提高监测污染物的效率，降低查询时间复杂度。树形目录的存储结构比线性表结构的组织形式更灵活，所以对于数据量大的信息通常采用树形结构存储。污染物数据存储于关系数据库中，查询时需要频繁地访问数据库。从数据库中获得一个数据项所需要的计算机指令数往往比从服务器中获得一个文件要大一到两个数量级，影响系统运行的整体性能。在多数系统中对某一对象重复访问，通常将生成数据进行缓冲处理，有利于系统性能的提高。2.缓冲实例的产生2.1系统缓冲机制2缓冲机制主要是基于被访问数据以减少网络传输、提高检索效率为目的。动态的缓冲是客户端通过网络访问服务器动态生成的，广域网环境中客户端请求的响应时间与请求传输时间、协议处理时间、数据装载时间、数据传输时间、数据表示时间有关。在这种环境中，缓冲主要是为了减少请求时间和数据的传输时间。缓冲数据主要分为两部分，主要存储在服务器端。数据对象的集合较为巨大，仅仅存放于硬盘上会直接影响访问速度。缓冲区位于服务器的内存中，顺序存储临时存放生成的数据，通常使用简单的有限空间管理机制来限制缓冲数据所占用的空间，采用二叉排序树手段存放数据，可以提高检索速率，缩短查询时间。2.2系统缓冲实例污染源附近现场机负责采集污染物数据，通过传输网络传送到上位机（即服务器），服务器接受数据并进行分析入库，在其他客户端上可以随时查询这些已入库的数据。多台监控设备定时将数据传输给数据采集器，再由数据采集器发送给服务器，将数据包从数据采集器到上位机的传输采用GPRS无线网络，使用TCP／IP协议。服务器端将数据包进行解包分析，解析出各个监控设备的参数值，并将其存入动态缓冲区，然后将它们对应入库。客户端通过B／S系统对数据库中的信息进行查询，根据不同的设置条件相应生成表格形式和曲线图形式的图像，查询条件的设置包括时间、名称、参数等。服务器根据访问对象的查找，被访问对象根据各种因素生成预期的数据集合，若符合要求，结束查询并反馈给客户，不符合要求则继续添加查询，直至符合客户端要求。3.二叉排序树应用于缓冲实例3.1建立二叉排序树二叉排序树的构造方法是根据客户端提交的查询条件建立包含子树的数据结构，以水污染物浓度为关键字建立二叉排序树。在污水中主要有八种污染物：铅、锰、铜、锌、铁、汞、银、铍，构造一个线性表（Pb、Mn、Cu、Zn、Fe、Hg、Ag、Be），以铅为根结点构造二叉排序树，其他的结点参照各种污染物的污染浓度的大小，若小于父结点的value值则将其作为左子树，反之将其作为右子树，使新的叶子结点找到合适的位置插入，这样生成的二叉排序树左右子树仍然满足二叉排序树的要求。PId污染物编号是int型数据作为结点的唯一标识，PNa污染物名称是text型数据，Cm化学符号是char型数据，Con污染物浓度是float数据类型，Fi记录父结点信息，Chi记录子节点信息。四、算法应用的结果、时间分析和空间分析3完成的二叉树很可能存在某个结点左、右子树的高度之差的绝对值大于1，某结点左、右子树的深度之差叫平衡因子，即平衡因子大于1，这样的二叉树就不是平衡二叉树，时间复杂度就不是最低的，效率也不是最高的。将构造好的二叉树进行旋转调整，使其平衡因子不大于1。传统的旋转算法包括顺时针旋转、逆时针旋转、先顺时针后逆时针旋转、先逆时针后顺时针旋转四种方法。若有结点进行插入或删除，二叉树就会变得不平衡，需要从插入位置沿通向根的路径回溯，检查各结点左、右子树的高度差。如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。如果这三个结点处于一条直线上，则采用单旋转进行平衡化；如果这三个结点处于一条折线上，则采用双旋转进行平衡化。通过对其进行旋转调整，使其再次成为平衡二叉树。当插入新的结点时，先从根结点进行比较，找到插入位置，并记录访问路径。从访问路径倒数第二个结点开始遍历该子树，并计算每个结点的平衡因子，选择相应的调整函数。当删除某个结点的时候，需要对删除结点位置进行处理，如果该结点是叶子结点，可以直接删除，如果是单枝结点，叶子结点取代该结点后删除，若是双枝结点则需进一步判断其平衡因子。Mn结点平衡因子的绝对值大于1，对该结点进行旋转，使其成为平衡二叉树。用户对污染物信息查询时，输入污染物的名字转换为对应的化学符号，快速与数据库信息比对后，若不存在该污染物，将查询结果反馈给用户，并将这条信息存储到数据表中。针对数据表中存在的污染物，系统会自动提取的化学符号，并按照已经建好的平衡二叉树对其动态查找，查找到该化学元素后，再根据用户输入的其他查询条件建立二叉排序树，平衡化处理该树的某些结点，将其存储于系统缓冲区中。采样的时间已经事先规定，每隔一定时间都会接受数据包，将其自动解析存入数据库后，系统取出所需的数据项，插入已经建好的二叉树中，并对其进行删除操作，去掉冗余的结点。当用户退出操作时，自动对二叉树进行解构，释放掉其所消耗的所有空间。五、算法的代码/*以下是用c++实现的二叉排序树的源代码*/#includeiostream.htypedefstructTreeNode{intkey;structTreeNode*left;4structTreeNode*right;}treeNode;classBiSortTree{public:BiSortTree(void);voiddesplayTree(void);//显示这个树voidinsertTree(intkey);//在树中插入一个值deleteTree(intkey);//在树中删除一个值treeNode*searchTree(intkey);//在树中查找一个值～BiSortTree();private:treeNode*buildTree(treeNode*head,intnumber);//建立一个树treeNode*search(treeNode*head,intkey);//查找treeNode*BiSortTree::searchParent(treeNode*head,treeNode*p);//查找出p的父亲节点的指针treeNode*BiSortTree::searchMinRight(treeNode*head);//找到右子树中最小的节点voidshowTree(treeNode*head);//显示voiddestroyTree(treeNode*head);//删除treeNode*Head;};/**************以下是建立一个二叉排序树****************/BiSortTree::BiSortTree()5{cout建立一棵二叉排序树,请输入你要建树的所有数(以-1作为结束标志!):endl;Head=NULL;intnumber;cinnumber;while(number!=-1){Head=buildTree(Head,number);cinnumber;}}treeNode*BiSortTree::buildTree(treeNode*head,intnumber){treeNode*p;p=newtreeNode;p-key=number;p-left=p-right=NULL;if(head==NULL){returnp;}else{6if(p-keyhead-key)head-left=buildTree(head-left,number);elsehead-right=buildTree(head-right,number);returnhead;}}/*****************以下是在一棵二叉排序树插入一个数***********************************/voidBiSortTree::insertTree(intkey){Head=buildTree(Head,key);}/*****************以下是在一个二叉排序树查找一个数是否存在*************************/treeNode*BiSortTree::searchTree(intkey){returnsearch(Head,key);}treeNode*BiSortTree::search(treeNode*head,intkey){if(head==NULL)returnNULL;if(head-key==key)7returnhead;else{if(keyhead-key)returnsearch(head-left,key);elsereturnsearch(head-right,key);}}/************以下是在一个二叉排序树删除一个给定的值*********************************/BiSortTree::deleteTree(intkey){treeNode*p;p=NULL;p=search(Head,key);if(p==NULL){coutDon'tfindthekey;}if(p==Head){Head=NULL;}8else{treeNode*parent;parent=searchParent(Head,p);if(p-left==NULL&&p-right==NULL)//叶子节点{if(parent-left==p){parent-left=NULL;}else{parent-right=NULL;}}else//非叶子节点{if(p-right==NULL)//该节点没有右孩子{if(parent-left==p){parent-left=p-left;}9else{parent-right=p-left;}}else//该点有左右孩子{treeNode*rightMinSon,*secondParent;//secondParent为右子树中的最小节点的父亲rightMinSon=searchMinRight(p-right);secondParent=searchParent(p-right,rightMinSon);secondParent-left=rightMinSon-right;if(p-right==rightMinSon)//右子树中的最小节点的父亲为p{p-right=rightMinSon-right;}p-key=rightMinSon-key;}}}}treeNode*BiSortTree::searchParent(treeNode*head,treeNode*p){if(head-left==p||head-right==p||head==p||head==NULL)10returnhead;else{if(p-keyhead-key)returnsearchParent(head-left,p);elsereturnsearchParent(head-