Структуры данных бинарное упорядоченное несбалансированное дерево — страница 4

  • Просмотров 1934
  • Скачиваний 380
  • Размер файла 16
    Кб

добавить к нему элемент InRight (P, X); //и конец OK = true; } else //посмотреть налево if (P->Left != NULL) //левый узел не NULL P = P->Left; //обход слева else { //левый узел -лист и надо добавить к нему элемент Iendleft(P, X); //и конец OK = true; } } //цикла while } void TTree::Add(TInfo Key) { if (Root == NULL) IniTree(Root, Key); else Tree_Add(Root, Key); } //-------------------------------------------------------------static void delete_ (PItem& P, TInfo X); static void Del(PItem& R, PItem& Q) //процедура удаляет узел имеющий двух потомков, заменяя его на самый правый //узел

левого поддерева { if (R->Right != NULL) //обойти дерево справа Del(R->Right, Q); else { //дошли до самого правого узла //заменить этим узлом удаляемый Q->Key = R->Key; Q = R; R = R->Left; } } //Del static void delete_ (PItem& P, TInfo X) { PItem Q; //Delete if (P != NULL) //искать удаляемый узел if (X < P->Key) delete_(P->Left, X); else if (X > P->Key) delete_(P->Right, X); //искать в правом поддереве else { //узел найден, надо его удалить //сохранить ссылку на удаленный узел Q = P; if (Q->Right == NULL) //справа NULL //и ссылку на узел надо

заменить ссылкой на этого потомка P = Q->Left; else if (Q->Left == NULL) //слева NULL //и ссылку на узел надо заменить ссылкой на этого потомка P = P->Right; else //узел имеет двух потомков Del(Q->Left, Q); delete Q; } else cout << "Такого элемента в дереве нет" << endl; } void TTree::Del(TInfo Key) { delete_(Root, Key); } //------------------------------------------------------------- static void PrintTree(PItem R, TInfo L) { int i; if (R != NULL) { PrintTree(R->Right, L + 3); for( i = 1; i <= L; i ++) cout << ' '; cout << R->Key << endl; PrintTree(R->Left, L + 3); } } void TTree::View() {

PrintTree (Root, 1); } //------------------------------------------------------------- static void Search(PItem& P, TInfo X) { if (P == NULL) { cout << "Такого элемента нет" << endl; } else if (X > P-> Key) //ищется в правом поддереве Search (P-> Right, X); else if (X < P-> Key) Search (P-> Left, X); else cout << "Есть такой элемент" << endl; } void TTree::Exist(TInfo Key) { Search(Root, Key); } //------------------------------------------------------------- static void Node_Dispose(PItem P) //Удаление узла и всех его потомков в дереве { if (P != NULL) { if (P->Left != NULL) Node_Dispose (P->Left); if (P->Right !=

NULL) Node_Dispose (P->Right); delete P; } } TTree::~TTree() { Node_Dispose(Root); } //------------------------------------------------------------- void inputKey(string S, TInfo& Key) { cout << S << endl; cin >> Key; } TTree *Tree = new TTree; int N; TInfo Key; int main(int argc, const char* argv[]) { do { cout << "1-Добавить элемент в дерево" << endl; cout << "2-Удалить элемент" << endl; cout << "3-Вывести узлы дерева" << endl; cout << "4-Проверить существование узла" << endl; cout << "5-Выход" << endl; cin >> N; { switch (N) { case 1: {

inputKey("Введите значение добавляемого элемента", Key); Tree->Add(Key); } break; case 2: { inputKey("Введите значение удаляемого элемента", Key); Tree->Del(Key); } break; case 3: Tree->View(); break; case 4: { inputKey("Введите элемент, существование которого вы хотите проверить", Key); Tree->Exist(Key); } break; } } } while (!(N==5)); return EXIT_SUCCESS; }