如果给我一个二叉搜索树的数据，一定要从头开始找，另外我还学到了双指针或多个指针记录前面顺序等想法。毕竟没学过ACM，啥都不会，哈哈哈哈
#include <iostream> #include<queue> using namespace std; template<class T> class BinarySearchTreeNode { public: T data; BinarySearchTreeNode<T> * leftchild; BinarySearchTreeNode<T>* rightchild; BinarySearchTreeNode(T ele,BinarySearchTreeNode<T>* l=NULL,BinarySearchTreeNode<T>* r=NULL) { data=ele; leftchild=l; rightchild=r; } }; template<class T> class BinarySearchTree { public: BinarySearchTreeNode<T>* root; BinarySearchTreeNode<T>* search(T val); bool insert(T val); bool deletebyCopying(T val); void LevelOrder(BinarySearchTreeNode<T> *root); BinarySearchTree() { root=NULL; } }; template<class T> BinarySearchTreeNode<T>* BinarySearchTree<T>::search(T val) { if(root==NULL) { return NULL; } BinarySearchTreeNode<T> *p=root; while(p) { if(p->data<val) { p=p->rightchild; } else if(p->data>val) { p=p->leftchild; } else { break; } } if(!p) { return NULL; } else { return p; } } template<class T> bool BinarySearchTree<T>::insert(T val) { BinarySearchTreeNode<T> *pre=root; BinarySearchTreeNode<T> *p=root; if(root==NULL) { root=new BinarySearchTreeNode<T>(val,NULL,NULL); return true; } else { while(p) { if(p->data<val) { pre=p; p=p->rightchild; } else { pre=p; p=p->leftchild; } } if(pre->data<val) { pre->rightchild=new BinarySearchTreeNode<T>(val,NULL,NULL); } else { pre->leftchild=new BinarySearchTreeNode<T>(val,NULL,NULL); } } } template<class T> void visit(BinarySearchTreeNode<T>* p) { cout<<p->data<<endl; } template<class T> void BinarySearchTree<T>::LevelOrder(BinarySearchTreeNode<T> *root) { using std::queue; queue<BinarySearchTreeNode<T> *>nodeQueue; BinarySearchTreeNode<T> *pointer=root; if(pointer) { nodeQueue.push(pointer); } while(!nodeQueue.empty()) { pointer=nodeQueue.front(); visit(pointer); nodeQueue.pop(); if(pointer->leftchild) nodeQueue.push(pointer->leftchild); if(pointer->rightchild) nodeQueue.push(pointer->rightchild); } } template<class T> bool BinarySearchTree<T>::deletebyCopying(T val) { BinarySearchTreeNode<T> *q; BinarySearchTreeNode<T> *p=root; BinarySearchTreeNode<T> *preq; BinarySearchTreeNode<T> *pre; if(root==NULL) { return false; } while(p) { if(p->data==val) { break; } else if(p->data>val) { pre=p; p=p->leftchild; } else if(p->data<val) { pre=p; p=p->rightchild; } } if(p==NULL) { return false; } else { if(p->leftchild==NULL||p->rightchild==NULL) { q=p->leftchild?p->leftchild:p->rightchild; if(pre->leftchild==p) { pre->leftchild=q; } else if(pre->rightchild==p) { pre->rightchild=q; } delete p; } else { q=p->leftchild; preq=q; while(q->rightchild) { preq=q; q=q->rightchild; } p->data=q->data; preq->rightchild=NULL;//删除被替换的节点； } return true; } } int main() { BinarySearchTree<int> t; t.insert(5); t.insert(2); t.insert(3); t.insert(1); t.insert(7); t.insert(6); t.LevelOrder(t.root); t.deletebyCopying(3); t.LevelOrder(t.root); return 0; }