二叉查找树算法

发布网友发布时间：2022-04-30 03:24

共1个回答

热心网友时间：2023-10-09 14:24

#include <iostream>using namespace std;typedef struct _node{int data;struct _node *pLeftPtr;struct _node *pRightPtr;}BTreeNode;class BinarySearchTree{public:BinarySearchTree();~BinarySearchTree();bool Create(int* pIntArray,int arrLength);bool Insert(int data);// 查找节点，searchLength为搜索长度，返回值为true表示指定的数据存在，否则不存在bool Find(int data, int* searchLength);// 中序输出二叉树void MidOutput();// 释放内存void Destroy();void Delete(int data);protected:bool Insert(BTreeNode* pRoot, int data);bool Find(BTreeNode* pRoot,int data, int *searchLength);void Delete(BTreeNode* &pRoot, int data);void MidOutput(BTreeNode* pRoot);void Destroy(BTreeNode* pRoot);private:BTreeNode* m_pRoot; //二叉搜索树根节点};BinarySearchTree::BinarySearchTree(){m_pRoot = NULL;}BinarySearchTree::~BinarySearchTree(){Destroy();}bool BinarySearchTree::Create(int* pIntArray,int arrLength){for(int i=0; i<arrLength; i++){if(!Insert(*(pIntArray+i)))return false;}return true;}bool BinarySearchTree::Insert(BTreeNode* pRoot, int data){BTreeNode* pNewNode = new BTreeNode;if(pNewNode == NULL)return false;pNewNode->data = data;pNewNode->pLeftPtr = NULL;pNewNode->pRightPtr = NULL;BTreeNode* pCurrentNode = pRoot;BTreeNode* pParentNode = pCurrentNode;// 保存父节点的指针int flag = 0;// 标记插入节点的位置if(pCurrentNode == NULL){m_pRoot = pNewNode;}else{while(pCurrentNode){if(data < pCurrentNode->data){pParentNode = pCurrentNode;pCurrentNode = pCurrentNode->pLeftPtr;flag = 0;}else if(data > pCurrentNode->data){pParentNode = pCurrentNode;pCurrentNode = pCurrentNode->pRightPtr;flag = 1;}}if(flag == 0){pParentNode->pLeftPtr = pNewNode;}else{pParentNode->pRightPtr = pNewNode;}}return true;}bool BinarySearchTree::Insert(int data){return Insert(m_pRoot,data);}bool BinarySearchTree::Find(BTreeNode* pRoot,int data, int *searchLength){if(pRoot == NULL){*searchLength = 0;return false;}BTreeNode* pCurrentNode = pRoot;static int length = 0; while(pCurrentNode != NULL){if(data == pCurrentNode->data){*searchLength = length;cout<<"数字"<<data<<"存在二叉树中,查找长度为: "<<endl<<length<<endl;return true;}else if(data < pCurrentNode->data){length ++;pCurrentNode = pCurrentNode->pLeftPtr;}else{length ++;pCurrentNode = pCurrentNode->pRightPtr;}}*searchLength = length;cout<<"数字"<<data<<"不在二叉树中,查找长度为: "<<endl<<length<<endl;length = 0; // 每次查找结束，重新赋值为0return false;}bool BinarySearchTree::Find(int data, int* searchLength){return Find(m_pRoot,data,searchLength);}void BinarySearchTree::Destroy(BTreeNode* pRoot){BTreeNode* pCurrentNode = pRoot;if(pCurrentNode == NULL)return;Destroy(pCurrentNode->pLeftPtr);Destroy(pCurrentNode->pRightPtr);delete pCurrentNode;m_pRoot = NULL;}void BinarySearchTree::Destroy(){Destroy(m_pRoot);}void BinarySearchTree::MidOutput(BTreeNode* pRoot){if(pRoot){MidOutput(pRoot->pLeftPtr);cout<<pRoot->data <<" ";MidOutput(pRoot->pRightPtr);}}void BinarySearchTree::MidOutput(){MidOutput(m_pRoot);}void BinarySearchTree::Delete(int data){Delete(m_pRoot,data);}void BinarySearchTree::Delete(BTreeNode* &pRoot, int data){if(!pRoot)return;else if(data == pRoot->data){if(pRoot->pLeftPtr == NULL && pRoot->pRightPtr == NULL) // 叶子节点{delete pRoot;pRoot = NULL;}else if(pRoot->pLeftPtr != NULL && pRoot->pRightPtr == NULL){ // 只有左子树 BTreeNode* pNode = pRoot->pLeftPtr;delete pRoot;pRoot = pNode;}else if(pRoot->pLeftPtr == NULL && pRoot->pRightPtr != NULL){ // 只有右子树BTreeNode* pNode = pRoot->pRightPtr;delete pRoot;pRoot = pNode;}else{ // 有左右子树// 找到左子树的最大节点BTreeNode* pCurrentNode = pRoot->pLeftPtr;BTreeNode* pParentNode = NULL;while(pCurrentNode->pRightPtr != NULL){pParentNode = pCurrentNode;pCurrentNode = pCurrentNode->pRightPtr;}pRoot->data = pCurrentNode->data;if(pParentNode){pParentNode->pRightPtr = pCurrentNode->pLeftPtr;}else{pRoot->pLeftPtr= pCurrentNode->pLeftPtr;}delete pCurrentNode;}}else if(data < pRoot->data)Delete(pRoot->pLeftPtr, data);elseDelete(pRoot->pRightPtr, data);}void main(){int data[8]; cout<<"请输入整形数据, 数据用空格隔开, 回车键结束输入"<<endl; for(int i=0; i<8; i++) cin>>data[i];// int data[8] = {13,15,6,20,14,5,7,18};BinarySearchTree tree;tree.Create(data,sizeof(data)/sizeof(data[0]));cout<<"插入数据后的二叉树为: "<<endl;tree.MidOutput();cout<<endl;int len_1=0;int len_2=0;tree.Find(14,&len_1);tree.Find(21,&len_2);tree.Delete(20);cout<<"删除数字20后的二叉树结果: "<<endl;tree.MidOutput();cout<<endl;tree.Delete(15);cout<<"删除数字15后的二叉树结果: "<<endl;tree.MidOutput();cout<<endl;}追问怎么那么多，我怎么一点都看不懂，还有我们正在做上机实验，拜托能不能弄简单一点，拜托了，大恩不言谢