定义一个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下的操作。
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。