バイナリツリー(バイナリ検索ツリーではありません)を実装しようとしています。これは主に、挿入/削除/検索&の明確な手順で構成されるクラステンプレートになります。ノードに保持されるデータは何でもかまいません。何か以下のように:バイナリツリープロシージャ(バイナリ検索ツリーではない)のヘルプが必要
- を:
template<class T> class BinaryTree { public: BinaryTree(int size); ~BinaryTree(); virtual bool insert(T data); virtual bool remove(T data); virtual void clear(); virtual bool search(T data); virtual void display(std::string str, ETravType type); virtual unsigned int getSize(); //friend void swapWithLastNode(Node *root, Node **nodeToRemove); protected: virtual void inorder(Node<T>* root); virtual void preorder(Node<T>* root); virtual void postorder(Node<T>* root); virtual void removeAll(Node<T>* root); Node<T>* root; int max; unsigned int curSize; };
私はアルゴリズムのいくつかの助けを必要とし、は、好ましくは、反復削除、挿入のために使用&を検索するために、(サイズ制限を積み重ねることにより、再帰を避けたいです)
挿入:ツリーが左右に歪まないようにする方法を教えてください。
削除:ノードに両方の子がある場合、削除を行う最良の方法は何ですか(例:BSTではinorderの後継で置き換えます)。
検索:O(n)検索を防ぐための効率的な方法はありますか?
は(主に再帰的)BSTの手続きのためのウェブ上の資源の豊富ありますが、バイナリツリーのどれも(あるいは、少なくとも私は何かを見つけることができませんでした)。それで、ここに投稿することを考えました。
挿入に関するご質問や、あなたがツリー内のノードの位置については、私はあなたも、代わりにバイナリツリーを使用している理由を依頼する必要があり、その点では気にしないことを私に示しているように見える削除単なるリンクリストのリスト? – PeterT