#include "BSTree.h" #include<iostream> using namespace std; //前序遍历二叉树 template<class T> void BSTree<T>::preOrder(BSTNode<T> *tree) const { if(tree!=nullptr) { cout<<tree->key<<" "; preOrder(tree->left); preOrder(tree->right); } } template<class T> void BSTree<T>::preOrder() { preOrder(mRoot); } //中序遍历二叉树 template<class T> void BSTree<T>::inOrder(BSTNode<T> *tree) const { if(tree!=nullptr) { inOrder(tree->left); cout<<tree->key<<" "; inOrder(tree->right); } } template<class T> void BSTree<T>::inOrder() { inOrder(mRoot); } //后序遍历二叉树 template<class T> void BSTree<T>::postOrder(BSTNode<T> *tree) const { if(tree!=nullptr) { postOrder(tree->left); postOrder(tree->right); cout<<tree->key<<" "; } } template<class T> void BSTree<T>::postOrder() { postOrder(mRoot); } //递归实现查找二叉树中键值为key的节点 template<class T> BSTNode<T>* BSTree<T>::search(BSTNode<T> *x, T key)const { if(x->key==key) return x; else if(x->key>key) return search(x->left,key); else return search(x->right,key); } template<class T> BSTNode<T>* BSTree<T>::search(T key) { return search(mRoot,key); } //非递归实现查找二叉树中键值为key的节点 template<class T> BSTNode<T>* BSTree<T>::iterativeSearch(BSTNode<T> *x, T key)const { while(x!=nullptr) { if(x->key==key) return x; else if(x->key>key) x=x->left; else x=x->right; } return x; } template<class T> BSTNode<T>* BSTree<T>::iterativeSearch(T key) { return iterativeSearch(mRoot,key); } //查找最小节点，返回最小节点 template<class T> BSTNode<T>* BSTree<T>::minimum(BSTNode<T> *tree) { while(tree->left!=nullptr) { tree=tree->left; } return tree; } template<class T> T BSTree<T>::minimum() { return minimum(mRoot)->key; } //查找最大节点，返回最大节点 template<class T> BSTNode<T>* BSTree<T>::maximum(BSTNode<T> *tree) { while(tree->right!=nullptr) { tree=tree->right; } return tree; } template<class T> T BSTree<T>::maximum() { return maximum(mRoot)->key; } //插入节点到二叉搜索树 template<class T> void BSTree<T>::insert(BSTNode<T> *&tree, BSTNode<T> *z) { if(tree==nullptr) { tree=z; return; } BSTNode<T>* p=nullptr; BSTNode<T>* tmp=tree; while(tmp) { if(tmp->key==z->key) return; p=tmp; if(tmp->key>z->key) { tmp=tmp->left; } else { tmp=tmp->right; } } if(p->key>z->key) p->left=z; else p->right=z; } template<class T> void BSTree<T>::insert(T key) { BSTNode<T>* node=new BSTNode<T>(key); insert(mRoot,node); } //删除节点 template<class T> BSTNode<T>* BSTree<T>::remove(BSTNode<T> *&tree, BSTNode<T> *z) { if(tree==nullptr) return; BSTNode<T>* pcur=tree; while(pcur!=nullptr && pcur->key!=z->key) { if(pcur->key>z->key) pcur=pcur->left; else pcur=pcur->right; } if(pcur==nullptr) return; if(!pcur->left && !pcur->right) { delete pcur; pcur=nullptr; return; } if(pcur->left && pcur->right) { BSTNode<T>* tmp=pcur->right; while(tmp->left) tmp=tmp->left; if(pcur->right=tmp) { pcur->right=tmp->right; delete tmp; tmp=nullptr; return; } BSTNode<T>* node=pcur; pcur=tmp; tmp=node; delete tmp; tmp=nullptr; return; } if(pcur->left) { BSTNode<T>* p=pcur->parent; if(p==nullptr) { tree=pcur->left; delete pcur; pcur=nullptr; return; } if(p->right==pcur) { p->right=pcur->left; } if(p->left==pcur) { p->left=pcur->left; } return; } if(pcur->right) { BSTNode<T>* p=pcur->parent; if(p==nullptr) { tree=pcur->right; delete pcur; pcur=nullptr; return; } if(p->right==pcur) { p->right=pcur->right; } if(p->left==pcur) { p->left=pcur->right; } return; } } template<class T> void BSTree<T>::remove(T key) { BSTNode<T>* node=new BSTNode<T>(key); remove(mRoot,node); } //销毁二叉树 template<class T> void BSTree<T>::destory(BSTNode<T> *&tree) { if(tree) { BSTNode<T>* l=tree->left; BSTNode<T>* r=tree->right; delete tree; destory(l); destory(r); } } template<class T> void BSTree<T>::destory() { destory(mRoot); } //查找节点x的后继节点 template<class T> BSTNode<T>* BSTree<T>::successor(BSTNode<T> *x) { if(x==nullptr || x->right==nullptr) return nullptr; BSTNode<T>* node=x->right; while(node->left) node=node->left; return node; } //查找节点x的前驱节点 template<class T> BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *x) { if(x==nullptr) return nullptr; if(x->left) { x=x->left; while(x->right) x=x->right; return x; } BSTNode<T>* p=x->parent; if(p==nullptr) return p; if(p->right==x) return p; if(p->left==x) { BSTNode<T>* q=p->parent; while(q->right!=p) { p=q; q=p->parent; } return q; } }