Двоичное дерево поиска C++

Question

Im немного смущенный. Im задается вопросом, реализовано ли двоичное дерево поиска на основе массива таким образом?

void BST::insert(item &items, const data & aData) 
{//helper function. 
    Parent++; 
    data *new_data = new data(aData); 
    this->insert(*new_data); 
} 

// insert a new item into the BST 
void BST::insert(const data &aData) 
{ 
    if (items[Parent].empty) 
    { 
     items[Parent].theData = aData; 
     items[Parent].empty = false; 
    } 
    else if (aData < items[Parent].theData) 
    { 
       if (Parent >= maxSize) this->reallocate(); 
       this->insert(items[2*Parent+1], aData); 
    } 
    else 
    { 
      this->insert(items[2*Parent+2], aData); 
    } 
} 

// ctor, где я делаю свои intiailizations.

BST::BST(int capacity) : items(new item[capacity]), 
Parent(0), leftChild(0), rightChild(0), maxSize(capacity) 
{ 
} 

Answer 1

Я не уверен, что бинарное дерево на основе массива является лучшей идеей, как это:

1. предотвращает узел балансировки (оптимизация поиска для неуравновешенных деревьев)
2. пустое пространство - тонны его, особенно если дерево неуравновешенное.

Сказав, что это обоснованный подход, с незначительным изменением: Изменение

если (Родитель> = MaxSize) this-> перераспределить();

к

, если (2 * Родитель> = MaxSize) этом-> перераспределить();

Answer 2

Это довольно старый, но я написал это на своем втором году обучения в колледже, который был около 8 лет назад :). Это может помочь вам в каком-то так или иначе ...

//JHermiz 
//Implementation File with def's 
//tree.h 

#include<stdlib.h> 
#include"xcept.h" //file for exceptions that may be thrown 

//BinaryTreeNode class 
template<class T> 
class BinaryTreeNode { 
       public: 
          BinaryTreeNode() {LeftChild=RightChild=NULL;} 
          BinaryTreeNode(const T&e) 
           { 
           data=e; 
           LeftChild=RightChild=NULL; 
           } 
          BinaryTreeNode(const T&e, BinaryTreeNode *l, 
               BinaryTreeNode *r) 
           { 
           data=e; 
           LeftChild=l; 
           RightChild=r; 
           } 

          BinaryTreeNode<T> *LeftChild; //left subtree 
          BinaryTreeNode<T> *RightChild; //right subtree 
          T data; 
          }; 

//BinaryTree Class 
template<class T> 
class BinaryTree{ 
      public: 
         BinaryTree(){root=NULL;} 

         ~BinaryTree(){Delete();} 

         void Delete(){PostOrder(Free, root); root=0;} 

         static void Free(BinaryTreeNode<T>* t){delete t;} 

         int IsEmpty()const 
         {return ((root) ? 0 : 1);} 

         int Root(T& x)const; 

         void MakeTree(const T& element, BinaryTree<T>& left, 
             BinaryTree<T>& right); 

         void BreakTree(T& element, BinaryTree<T>& left, 
              BinaryTree<T>& right); 

         void PreOrder(void(*Visit)(BinaryTreeNode<T> *u)) 
          {PreOrder(Visit, root);} 

         void InOrder(void(*Visit)(BinaryTreeNode<T> *u)) 
          {InOrder(Visit, root);} 

         void PostOrder(void(*Visit)(BinaryTreeNode<T> *u)) 
          {PostOrder(Visit, root);} 

         BinaryTreeNode<T>* root; //root pointer 

        //traversal methods 
         void PreOrder(void(*Visit) 
          (BinaryTreeNode<T> *u), BinaryTreeNode<T> *t); 

         void InOrder(void(*Visit) 
          (BinaryTreeNode<T> *u), BinaryTreeNode<T> *t); 

         void PostOrder(void(*Visit) 
          (BinaryTreeNode<T> *u), BinaryTreeNode<T> *t); 

         static void Output(BinaryTreeNode<T> *t) 
          { 
           cout << t->data << " "; 
          } 

         void PreOutput() 
         { 
          PreOrder(Output, root); 
          cout << endl; 
         } 

         void InOutput() 
         { 
          InOrder(Output, root); 
          cout << endl; 
         } 

         void PostOutput() 
         { 
          PostOrder(Output, root); 
          cout << endl; 
         } 
        }; 

//base class is BinaryTree - BSTree is the derived class 
template<class E, class K> 
class BSTree : public BinaryTree<E>{ 
     public: 
        int Search(const K& k, E& e)const; 
        BSTree<E,K>& Insert(const E& e); 
        BSTree<E,K>& Delete(const K& k, E& e); 
        //stores the maximum element of the tree in e 
        void MaxNode(E& e)const; 
     }; 


/*---------------------BinaryTree Methods()-------------------------*/ 
template<class T> 
int BinaryTree<T>::Root(T& x) const 
    { //Set x to root->data 
    //return false if no root 
    if(root) 
     { 
     x=root->data; 
     return 1; 
     } 
    else return 0; //no root 
    } 

template<class T> 
void BinaryTree<T>::MakeTree(const T& element, 
         BinaryTree<T>& left, BinaryTree<T>& right) 
    {//Combine left, right, and element to make new tree. 
    //left, right, and this must be different trees. 
    //create combined tree 

    root=new BinaryTreeNode<T>(element, left.root, right.root); 

    //deny access from trees left and right 
    left.root=right.root=0; 
    } 

template<class T> 
void BinaryTree<T>::BreakTree(T& element, 
         BinaryTree<T>& left, BinaryTree<T>& right) 
    {//left, right, and this must be of different trees. 
    //check if empty 

    if(!root) //empty tree 
     throw BadInput(); 

    //break the tree 
    element=root->data; 
    left.root=root->LeftChild; 
    right.root=root->RightChild; 

    delete root; 
    root=0; 
    } 

template<class T> 
void BinaryTree<T>::PreOrder(void(*Visit) 
         (BinaryTreeNode<T>* u), BinaryTreeNode<T>* t) 
    {//preorder traversal 

    if(t) 
     { 
     Visit(t); 
     PreOrder(Visit, t->LeftChild); 
     PreOrder(Visit, t->RightChild); 
     } 
    } 

template<class T> 
void BinaryTree<T>::InOrder(void(*Visit)(BinaryTreeNode<T>* u), 
            BinaryTreeNode<T>* t) 
    {//inorder traversal 

     if(t) 
     { 
      InOrder(Visit, t->LeftChild); 
      Visit(t); 
      InOrder(Visit, t->RightChild); 
     } 
    } 

template<class T> 
void BinaryTree<T>::PostOrder(void(*Visit)(BinaryTreeNode<T>* u), 
             BinaryTreeNode<T>* t) 
    {//postorder traversal 

    if(t) 
     { 
     PostOrder(Visit, t->LeftChild); 
     PostOrder(Visit, t->RightChild); 
     Visit(t); 
     } 
    } 
/*----------------------End of BinaryTree Methods()------------------*/ 

/*------------------------BSTree Methods()---------------------------*/ 

template<class E, class K> 
int BSTree<E,K>::Search(const K& k, E& e) const 
{//Search for element that matches k. 
    //Pointer p starts at the root and moves through 
    //the tree looking for an element with key k. 

    BinaryTreeNode<E> *p=root; 

    while(p) //examine p if >, <, or == 
     { 
     if(k<p->data) 
      p=p->LeftChild; 
     else if(k>p->data) 
      p=p->RightChild; 
     else{ //element is found 
       e=p->data; 
       return 1; 
      } 
     } 
    return 0; 
    } 

template<class E, class K> 
BSTree<E,K>& BSTree<E,K>::Insert(const E& e) 
{ //Insert e if not duplicate 

    BinaryTreeNode<E> *p=NULL; //search pointer 
    BinaryTreeNode<E> *pp=NULL;  //parent of p 

    //find place to insert throw BadInput if a duplicate element 
    p=root;  //p is now the root 

    while(p) 
    { 
    pp=p; 
    //move p to a child depending if p is > or < 

    if(e<p->data) 
     p=p->LeftChild; 

    else if(e>p->data) 
     p=p->RightChild; 

    else 
     throw BadInput(); //a duplicate element 
    } 

    //Get a node (memory) for e and attach to pp 
    BinaryTreeNode<E> *r=new BinaryTreeNode<E>(e); 

    if(root) 
     {//tree not empty 

     if(e<pp->data) 
     pp->LeftChild=r; 

     else if(e>pp->data) 
     pp->RightChild=r; 
     } 

    else //we need a root first! 
     root=r; 

    return *this; 
    } 

template<class E, class K> 
BSTree<E,K>& BSTree<E,K>:: Delete(const K& k, E& e) 
{//Delete element with key k and put it in e. 
    //set p to point to node with key k 

    BinaryTreeNode<E> *p=NULL; //a search pointer 
    BinaryTreeNode<E> *pp=NULL; //parent of p 

    p=root; 

    while(p && p->data != k) 
    {//move to a child of p 

    pp=p; 

     if(k < p->data) 
     p=p->LeftChild; 

     else 
     p=p->RightChild; 
    } 

    if(!p)    //no element with key k 
    throw NoElement(); 

    e=p->data; //save element to delete 

    //restructure the tree so it remains a BSTree 
    if(p->LeftChild && p->RightChild) //handle the node with 2 children if any 
     {//convert it to point to NULL or one child case 
     //find largest element in left subtree of p 

     BinaryTreeNode<E> *s=p->LeftChild; 
     BinaryTreeNode<E> *ps=p; //parent of s which is actually p 

     while(s->RightChild) 
     {//move to the larger element 
      ps=s; 
      s=s->RightChild; 
     }//end while 

     //move largest from s to p 
     p->data=s->data; 
     p=s; 
     pp=ps; 
     }//end all if 

    //p only had one child 
    //save child pointer in c 
    BinaryTreeNode<E> *c; 

    if(p->LeftChild) 
    c=p->LeftChild; 

    else 
    c=p->RightChild; 
    //delete p 

    if(p==root) 
     root=c; 

    else{ 
      //is p left or right child of pp? 
      if(p==pp->LeftChild) 
       pp->LeftChild=c; 

      else 
       pp->RightChild=c; 
     }//end else 
    delete p; 
    return *this; 
} 

template<class E, class K> 
void BSTree<E,K>::MaxNode(E &e)const 
{//function returns max. value of tree (rightmost value) 

    BinaryTreeNode<E>* p=NULL; //root node 
    BinaryTreeNode<E>* pp=NULL; //parent of p 

    p=root; 

    while(p) 
    { 
    pp=p; 
    p=p->RightChild; 
    } 
    //p points to NULL, pp points to node before NULL 
e=pp->data; //max. value stored 
} 

char Menu() 
{ 
    char choice; 

    //a menu 
    cout << "\n\t\tBST TREE MENU\n"; 
    cout << "\t********************************\n"; 
    cout << "\t* 1)Type 1 to insert an element*\n"; 
    cout << "\t* 2)Type 2 to delete an element*\n"; 
    cout << "\t* 3)Type 3 to output pre-order *\n"; 
    cout << "\t* 4)Type 4 to output in-order *\n"; 
    cout << "\t* 5)Type 5 to output post-order*\n"; 
    cout << "\t* 6)Type 6 for maximum element *\n"; 
    cout << "\t* 7)Type 7 to output root  *\n"; 
    cout << "\t* 8)Type 8 to search for a # *\n"; 
    cout << "\t* 9)Type 9 to exit program. *\n"; 
    cout << "\t********************************\n"; 

    cout << "Input your choice: "; 
    cin >> choice; 

    while(choice!='1' && choice!='2' && choice!='3' 
      && choice!='4' && choice!='5' && choice!='6' 
      && choice!='7' && choice!='8' && choice!='9') 
     {//user typed in wrong key 
      cout << "\nType choice as 1-9: "; 
      cin >> choice; 
     } 
    return choice; 
}