Actually, I have prescribed a binary tree class (although it is crooked, this is not the case). But the insertion method does not fit the task. Namely: An array is supplied to the program input (for example: 1 4 6 10 0 0 0 7 ...), where each zero is a leaflet, after which nothing can be added, and all numbers are added from left to right (hard to explain, in the screenshot example)
An example of an array and how it should look in the tree

Here is my tree class: h:

#pragma once class binTree { struct Node { int Value; Node * pLeft; Node * pRight; Node * pParent; Node(int x) :Value(x), pLeft(NULL), pRight(NULL), pParent(NULL) {} }; Node * m_pRoot; void InoderTreeWalk(Node * x); Node * TreeSuccessor(Node *x); Node * TreeMin(Node * x); public: binTree(); ~binTree(); void TreeInsert(int k); Node * TreeSearch(Node * X, int k); void ShowTree(); int Root(); };

cpp:

 #include "stdafx.h" #include "binTree.h" binTree::binTree() { m_pRoot = NULL; cout << " binTree::binTree() " << this << endl; } binTree::~binTree() { cout << " binTree::~binTree() " << this << endl; } int binTree::Root() { return m_pRoot->Value; } /*Нормальная функция вставки*/ void binTree::TreeInsert(int k) { Node * z = new Node(k); Node * y = NULL; Node * x = m_pRoot; while (x != NULL) { y = x; if (z->Value < x->Value) x = x->pLeft; else x = x->pRight; } z->pParent = y; if (y == NULL) m_pRoot = z; else if (z->Value < y->Value) y->pLeft = z; else y->pRight = z; } binTree::Node * binTree::TreeSearch(binTree::Node * X, int k) { if (X == NULL || k == X->Value) return X; if (k < X->Value) return TreeSearch(X->pLeft, k); else return TreeSearch(X->pRight, k); } void binTree::InoderTreeWalk(Node * x) { if (x != NULL) { InoderTreeWalk(x->pLeft); cout << ' ' << x->Value; if (x->pParent != NULL) cout << " Parent = " << x->pParent->Value << endl; else cout << endl; InoderTreeWalk(x->pRight); } } binTree::Node * binTree::TreeSuccessor(Node * x) // поиск следующего элемента { if (x->pRight != NULL) return TreeMin(x->pRight); Node * y = x->pParent; while (y != NULL && x == y->pRight) { x = y; y = y->pParent; } return y; } binTree::Node * binTree::TreeMin(Node * x) { while (x->pLeft != NULL) x = x->pLeft; return x; } void binTree::ShowTree() { cout << "\n Tree: \n"; InoderTreeWalk(m_pRoot); cout << "\n\n"; }

The TreeInsert function inserts new values ​​as they should in the normal search tree.

And I need a function that will insert new elements as shown in the example (as in the screenshot) .

  • Too many letters? - Andrey
  • There are a normal number of letters , but the class is superfluous, one insert function is enough - Cerbo
  • Show what you did yourself - Cerbo
  • He did everything himself. - Andrey
  • Well, and answer your question - Cerbo

1 answer 1

By the way, I solved this problem with the help of the “clumsy method”, but it still works.

 void binTree::AddNum(int x) { if (m_pCurrNode == m_pRoot && m_left == true) { m_pRoot->pLeft = new Node(x); m_pCurrNode = m_pRoot->pLeft; m_pCurrNode->pParent = m_pRoot; } else { if (m_left) { if (x) { m_pCurrNode->pLeft = new Node(x); Node * tmp = m_pCurrNode; m_pCurrNode = m_pCurrNode->pLeft; m_pCurrNode->pParent = tmp; } else { m_left = false; } } else // to right { if (x) { m_pCurrNode->pRight = new Node(x); Node * tmp = m_pCurrNode; m_pCurrNode = m_pCurrNode->pRight; m_pCurrNode->pParent = tmp; m_left = true; } else { m_right = false; Node * pTMPstart = m_pCurrNode; m_pCurrNode = m_pCurrNode->pParent; // дойти до следующего узла по значению... if (m_pCurrNode->pRight == NULL) { m_right = true; } else if(m_pCurrNode->pRight != pTMPstart) { // если правая ветка не пустая m_pCurrNode = TreeMin(m_pCurrNode->pRight); m_left = m_right = true; } else { while (m_pCurrNode->pRight == pTMPstart) { pTMPstart = m_pCurrNode; m_pCurrNode = m_pCurrNode->pParent; if (m_pCurrNode == m_pRoot) break; } m_right = true; } } } } }

ps Thanks for the help =))))