算是基本能实现你的功能让码了吧。
VC下测试通过。
#include <iostream>
#include <cstring>
using namespace std
class node
{
public:
node(int i):data(i),left(NULL),right(NULL){}
void inorder(node *&root) //中序遍历，符合升序输出
{
if(root!=NULL)
{
inorder(root->left)
cout<<root->data<<' '
inorder(root->right)
}
}
void insert(node *&ptr,int item) //在查找树中插入元素
{
if(ptr==NULL)
ptr=new node(item)
else if(item<ptr->data)
insert(ptr->left,item)
else insert(ptr->right,item)
}
node *find(node *&ptr,int item) //在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。
{
if(ptr==NULL)
return NULL
if(ptr->data==item)
return ptr
else if(item<ptr->data)
find(ptr->left,item)
else find(ptr->right,item)
}
node *&findy(node *&ptr,int item) //在雹滑手查找树中查找肯定存在的元素,并返回其引用
{
if(ptr->data==item)
return ptr
else if(item<ptr->data)
findy(ptr->left,item)
else findy(ptr->right,item)
}
void printfind(node *&ptr,int item) //在查找树中查找元素,并输出经过路径
{
if(ptr->data==item){
cout<<item<<endl
return
}
else if(item<ptr->data){
cout<<ptr->data<<'源嫌 '<<endl
printfind(ptr->left,item)
}
else
{
cout<<ptr->data<<' '<<endl
printfind(ptr->right,item)
}
}
node* rl(){return left}
node* rr(){return right}
void dele(node *&ptr) //删除值为item所在结点
{
if(ptr->rl()==NULL&&ptr->rr()==NULL)
ptr=NULL
else if(ptr->rr()==NULL)
ptr=ptr->rl()
else if(ptr->rl()==NULL)
ptr=ptr->rr()
else
{
node *temp=ptr->rl()
ptr=ptr->rr()
node *temp2=ptr
while(temp2->rl()!=NULL)
temp2=temp2->rl()
temp2->setl(temp)
}
}
void setl(node *l){left=l}
private:
int data
node *left //左孩子结点
node *right //右孩子结点
}
int main()
{
char a[10]
int t,i=0,j
cout<<"输入数字个数:"
cin>>t
cout<<"输入"<<t<<"个数字，数字之间用空格隔开:"
cin>>j
node *x=new node(j)
for(i<t-1i++)
{
cin>>j
x->insert(x,j)
}
cout<<"输入 *** 作(当输入串为(0 0)时结束程序):"<<endl
cin>>a>>j
while(strcmp(a,"0")!=0)
{
if(strcmp(a,"S")==0)
{
if(x->find(x,j)==NULL)
cout<<"-1"<<endl
else
x->printfind(x,j)
}
else if(strcmp(a,"D")==0)
{
node *t=x->find(x,j) //定位结点
if(t!=NULL)
{
node *&y=x->findy(x,j)
x->dele(y)
}
x->inorder(x)
}
cout<<"\n输入 *** 作(当输入串为0时结束程序):"<<endl
cin>>a>>j
}
return 0
}
附测试数据一组。
5
23 55 33 5 14
S 4
S 5
D 4
D 5
D 33
D 44
0 0
经测试均正确。
#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 // 每次查找结束，重新赋值为0
return 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)
else
Delete(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
}
int main(int argc, char const *argv[]){
for (int i = 0i <10++i)
{
TestAALock()
gCount = 0
gCountArray.clear()
}
return 0
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）