c ++ функция вставки для бинарного дерева поиска с предварительным заказом - PullRequest
Новая
       44

c ++ функция вставки для бинарного дерева поиска с предварительным заказом

0 голосов
/ 28 сентября 2019

Я пытаюсь создать функцию добавления, которая будет полностью обрабатывать все узлы для обхода предварительного заказа.Я могу добраться до нужного места в дереве, чтобы добавить новый узел, и именно здесь я не могу точно перемещать указатели.Мне дали функцию, которая выполняет обход предзаказа для дерева с предзаказом.

Любая помощь, указатели или идеи будут с благодарностью.Большое спасибо!

q - родитель узла, который я добавляю

p - узел, который я добавляю

parentq - родитель родительского элемента q

p-> leftThread = true;p-> rightThread = true; 

if (left)
{
    if (parentq->rightChild)
    {
        p->leftChild = static_cast<threadBinNode<BaseData>*>(q);
        p->rightChild = static_cast<threadBinNode<BaseData>*> (q->rightChild);
        q->leftChild = static_cast<threadBinNode<BaseData>*>(p);
        q->leftThread = false;
    }

    else
    {
        p->leftChild = static_cast<threadBinNode<BaseData>*>(q);
        p->rightChild = BinThreadTree<BaseData>::root;
        q->leftChild = static_cast<threadBinNode<BaseData>*>(p);
        q->leftThread = false;


    }
}

else
{
    if (parentq->rightChild)
    {
        p->rightChild = static_cast<threadBinNode<BaseData>*>(parentq->rightChild);
        p->leftChild = static_cast<threadBinNode<BaseData>*>(q);
        q->rightChild = static_cast<threadBinNode<BaseData>*>(p);
        q->rightThread = false;
    }

    else
    {
        p->rightChild = BinThreadTree<BaseData>::root;
        p->leftChild = BinThreadTree<BaseData>::root;
    }
}

Это функция обхода, которую мне дали: 

template <class BaseData>
void BinThreadTree<BaseData>::preorder(void (*processNode)(BaseData &item))
{

  threadBinNode<BaseData>  *p;
  p =    static_cast< threadBinNode<BaseData>*  >
         ( BinThreadTree<BaseData>::root ->  leftChild ) ;


  do
    {
      if ( p !=   BinThreadTree<BaseData>::root )
        processNode( p->info );
      if  (!p -> leftThread )
        p =  static_cast< threadBinNode<BaseData>*  >(p -> leftChild);
      else
        p = static_cast< threadBinNode<BaseData>*  >(p->rightChild);

    }
  while (p !=   BinThreadTree<BaseData>::root );


}
...