定义一个10个元素(25,12,10,15,55,60,45,70,11,13)的数组以二叉树结构存储,在排序过后删除其中任意元素,删除55的过程中出错,请大家帮忙看看问题,谢谢...
//Tree.h
#include<iostream>
using namespace std;
#ifndef TREE_H
#define TREE_H
template<class T>
class Tree
{
public:
Tree();
bool insert(const T& x);
bool search(const T& x) const;
bool deleteItem(const T& x);
void display() const;
private:
struct TreeNode
{
T item;
TreeNode* left;
TreeNode* right;
};
TreeNode* root;
bool insert(TreeNode*& aroot,const T& x);
bool search(TreeNode* aroot,const T& x) const;
bool deleteItem(TreeNode*& aroot,const T& x);
void display(TreeNode* aroot) const;
};
#endif
template<class T>
Tree<T>::Tree()
{
root = NULL;
}
template<class T>
bool Tree<T>::insert(const T& x)
{
return insert(root,x);
}
template<class T>
bool Tree<T>::search(const T& x) const
{
return search(root,x);
}
template<class T>
bool Tree<T>::deleteItem(const T& x)
{
return deleteItem(root,x);
}
template<class T>
void Tree<T>::display() const
{
display(root);
cout << endl;
}
template<class T>
bool Tree<T>::insert(TreeNode*& aroot, const T& x)
{
if(aroot == NULL)
{
aroot = new TreeNode;
aroot -> left = NULL;
aroot -> right = NULL;
aroot -> item = x;
return true;
}
else if(aroot -> item == x)
{
cout << "元素已存在!" << endl;
return false;
}
else if(aroot -> item > x)
return insert(aroot -> left,x);
else
return insert(aroot -> right,x);
}
template<class T>
bool Tree<T>::search(TreeNode* aroot, const T& x) const
{
if(aroot == NULL)
{
cout << "未找到" << endl;
return false;
}
else if(aroot -> item == x)
{
cout << "已找到!" << endl;
return true;
}
else if(aroot -> item > x)
return search(aroot -> left,x);
else
return search(aroot -> right,x);
}
template<class T>
bool Tree<T>::deleteItem(TreeNode*& aroot, const T& x)
{
if(aroot == NULL)
{
cout << "没有要删除的元素!" << endl;
return false;
}
else if(aroot != NULL && aroot -> item == x)
{
TreeNode* oldNode = aroot;
if(aroot -> left == NULL)
{
if(aroot -> right == NULL)
{
aroot = NULL;
oldNode = NULL;
delete aroot;
delete oldNode;
return true;
}
else
{
oldNode = NULL;
aroot = aroot -> right;
aroot -> right = aroot -> right;
delete oldNode;
return true;
}
}
else if(aroot -> right == NULL)
{
if(aroot -> left == NULL)
{
aroot = NULL;
oldNode = NULL;
delete oldNode;
delete aroot;
return true;
}
else
{
oldNode = NULL;
aroot = aroot -> left;
aroot -> left = aroot -> left;
delete oldNode;
return true;
}
}
else
{
TreeNode* newNode = aroot;
oldNode = NULL;
aroot = aroot -> left;
aroot -> left = aroot -> left;
aroot -> right = aroot -> right;
if(newNode -> right != NULL)
aroot -> right -> right = newNode -> right;
delete oldNode;
return true;
}
}
else if(aroot -> item > x)
return deleteItem(aroot -> left,x);
else
return deleteItem(aroot -> right,x);
}
template<class T>
void Tree<T>::display(TreeNode *aroot) const
{
if(aroot != NULL)
{
display(aroot -> left);
cout << aroot -> item << " ";
display(aroot -> right);
}
}
//Tree.cpp
#include<iostream>
#include"Tree.h"
using namespace std;
typedef Tree<int> Treelist;
int main()
{
Treelist tl;
int a[10] = {25,12,10,15,55,60,45,70,11,13};
for(int i = 0;i < 10;i++)
tl.insert(a[i]);
tl.display();
tl.deleteItem(12);
tl.display();
system("pause");
return 0;
}
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。
看不懂,cplusplus?######是的,就是声明一个模版类,然后插入数值,二叉树进行排序以后删除其他元素都行,就是删除55出错,或者你有什么好方法么?######删除之后仍然要保持有序么?######
25
12 60
10 15 45 70
或者
25
12 45
10 15 60
70
也可以。
因此当要删除节点55时应该有一个指针指在25上(注意这个25不一定就是root),这样才能完成将原来55下的节点挂到25下的操作。