Good day! There is a non-recursive function that performs a symmetric tree walk. Instead of a stack used deck.

struct BinaryTree { int Data; BinaryTree* Left; BinaryTree* Right; }; //создание бинарного дерева void Make_Binary_Tree(BinaryTree** Node, int n) { BinaryTree** ptr; //вспомогательный указатель srand(time(NULL) * 1000); while (n > 0) { ptr = Node; while (*ptr != NULL) { if ((double)rand() / RAND_MAX < 0.5) ptr = &((*ptr)->Left); else ptr = &((*ptr)->Right); } (*ptr) = new BinaryTree(); cout << "Введите значение "; cin >> (*ptr)->Data; n--; } } // функция нерекурсивного обхода void SymmetricOrder_BinaryTree_Loop(BinaryTree* Node) { deque <BinaryTree> stack; do { while (Node != NULL) { stack.push_back(*Node); Node = Node->Left; } if (stack.size() > 0) { *Node = stack.back(); stack.pop_back(); printf("%3ld", Node->Data); Node = Node->Right; } } while (stack.size() > 0); } int main() { struct BinaryTree *nodes = { 0 } ; struct BinaryTree *root = nodes; Make_Binary_Tree(&root, 8); SymmetricOrder_BinaryTree_Loop(root); system("pause"); return 0; }

The problem is that it gives an error:

"Caused an exception: write access violation. Node was nullptr."

That is, the loop goes outside the tree and points to an empty cell. According to the algorithm, this is how it should be, but apparently somehow implemented in a different way. How can I fix it to work?

  • "Alexander Kagalchuk What is the meaning of this declaration struct BinaryTree * nodes = {0}; if the variable nodes is not used? - Vlad from Moscow
  • @Vlad from Moscow, perhaps, no. Used before, I forgot to remove. - Alexander Kagalchuk

1 answer 1

This cycle

  while (Node != NULL) { stack.push_back(*Node); Node = Node->Left; }

completes its work when Node becomes NULL .

However, in a subsequent sentence code block with if

  if (stack.size() > 0) { *Node = stack.back(); ^^^^^

you dereference this pointer, which is NULL .

As a result, the program has an undefined behavior.

In addition, there is also a logical error. Imagine that the root node of a tree has only the right child. Then only this root node will be initially added to the stack. In the if this node will be removed from the stack.

  if (stack.size() > 0) { *Node = stack.back(); stack.pop_back(); ^^^^^^^^^^^^^^^^

As a result, the stack will be empty. And this will complete the entire outer cycle.

 do { //... } while (stack.size() > 0); ^^^^^^^^^^^^^^^^

despite the fact that the root node has a right descendant.

It is also not clear why you are using the standard container std::deque while the adapter for the container std::stack already defined in the C ++ standard.

Also, there is no need to keep the nodes themselves on the stack. Enough to keep pointers to them.

Below is a demo program that shows how the tree output function can be implemented.

 #include <iostream> #include <stack> #include <cstdlib> #include <ctime> struct BinaryTree { int Data; BinaryTree *Left; BinaryTree *Right; }; void Make_Binary_Tree( BinaryTree **Node, size_t n ) { std::srand( ( unsigned int )std::time( nullptr ) ); for ( ; n != 0; n--) { while ( *Node != nullptr ) { if ( std::rand() % 2 == 0 ) { Node = &( *Node )->Left; } else { Node = &( *Node )->Right; } } *Node = new BinaryTree(); std::cout << "Введите значение узла: "; std::cin >> ( *Node )->Data; } } // функция нерекурсивного обхода void SymmetricOrder_BinaryTree_Loop( const BinaryTree *Node ) { std::stack<const BinaryTree *> stack; while ( Node != nullptr || !stack.empty() ) { while ( Node != nullptr ) { stack.push( Node ); Node = Node->Left; } std::cout << stack.top()->Data << ' '; Node = stack.top()->Right; stack.pop(); } } int main() { BinaryTree *root = nullptr; Make_Binary_Tree( &root, 5 ); SymmetricOrder_BinaryTree_Loop( root ); }

The output of the program to the console may look as follows.

 Введите значение узла: 1 Введите значение узла: 2 Введите значение узла: 3 Введите значение узла: 4 Введите значение узла: 5 1 2 5 4 3

This output corresponds to the following tree view.

 1 \ \ 2 \ \ 3 / / 4 / / 5
  • Thank you very much for your answer! Tell me, what is the difference between the work of your function of creating a tree from mine? In other words, why do you always have a tree lined up with one descendant from each vertex, except the root? I can not see myself ... - Alexander Kagalchuk