2016-11-02 9 views
1

バイナリツリー(バイナリ検索ツリーではありません)を実装しようとしています。これは主に、挿入/削除/検索&の明確な手順で構成されるクラステンプレートになります。ノードに保持されるデータは何でもかまいません。何か以下のように:バイナリツリープロシージャ(バイナリ検索ツリーではない)のヘルプが必要

  • を:

    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の手続きのためのウェブ上の資源の豊富ありますが、バイナリツリーのどれも(あるいは、少なくとも私は何かを見つけることができませんでした)。それで、ここに投稿することを考えました。

+0

挿入に関するご質問や、あなたがツリー内のノードの位置については、私はあなたも、代わりにバイナリツリーを使用している理由を依頼する必要があり、その点では気にしないことを私に示しているように見える削除単なるリンクリストのリスト? – PeterT

答えて

4

BTよりもBSTを優先させる本当の理由があります。

BSTは挿入、削除、検索のためにlog(N)ですが、BTはO(N)のコストで完全なトラバーサルを実現する可能性があります。

  1. 挿入:ツリーが左右に歪まないようにする方法を教えてください。

    私は怖いことはツリーの全体的なパフォーマンスに任意の違いはありませでしょう。それでもやりたい場合は、self-balancing treeについて学んでください。

  2. 削除:ノードに両方の子がある場合、削除を行う最良の方法は何ですか(例:BSTではinorderの後継で置き換えます)。

    削除するには、ツリーの任意の葉ノードを選択し、その位置に置き換えます。バイナリツリーにはパターンがないため、ランダムノードを選択しても何の違いもありません。だから、リーフノードをピックアップするのに問題はありません。

  3. 検索:O(n)検索を防ぐための効率的な方法はありますか?

    いいえ、O(n)の検索を防ぐより良い方法はありません。あなたは完全なツリーを横断する必要があります。効率的にナビゲートするためのBTのノードのパターン/順序はありません。

関連する問題