バイナリツリープロシージャ（バイナリ検索ツリーではない）のヘルプが必要

Question

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

• を：

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

Answer 1

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

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

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

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

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

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

3. 検索：O（n）検索を防ぐための効率的な方法はありますか？

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