3. Preorder-traversal in a tree

Preorder-traversal in a tree

  • ?

    Hi,

    Im coding a preorder traversal for a Binary tree. The problem is here: if (temp->right) ... if a right node is existing i push it on the stack again and if(n) gets active and prints the same node again...how can i fix it?

    void pre_order_traversal(Node *n) {
		static stack<Node*> nodes;

		if (n) {
			nodes.push(n);

			cout << n->value << endl;

			pre_order_traversal(n->left);
		}

		if(!nodes.empty()) {
			Node *temp = nodes.top();
			nodes.pop();

			if (temp->right) {
				cout << temp->right->value << endl;

				pre_order_traversal(temp->right);
			}
		}
	}

    The tree looks like this:

    10
  5     15
 4 6      16
3   7
     8

    My preorder traversal output:

    10
5
4
3
6
6
7
7
8
8
15
15
16
16
0
    0
  • S

    Why do you want to use a list (in this the stack data structure) ?

    Just do the following:

    void pre_order_traversal(Node *n)
{
    if ( !n )
        return;

    cout << n->value << endl; // your operation

    pre_order_traversal(n->left); // left subtree traversal
    pre_order_traversal(n->right); // right subtree traversal
}

    (untested)

    0
  • ?

    ok, that makes sense...but i want to implement a non recursive solution...thats why i used the stack...i should not call it recursive.

    0
  • V

    James1 schrieb:

    ok, that makes sense...but i want to implement a non recursive solution...thats why i used the stack...i should not call it recursive.

    void pre_order_traversal(Node *n) {
        stack<Node*> to_do;
        //assert(n);
        to_do.push(n);

        do {
            Node* parent = to_do.top();
            nodes.pop();

            cout << current->value << '\n';//nicht endl bitte
            if(current->left) to_do.push(current->left);
            if(current->right) to_do.push(current->right);
        } while(!to_do.empty());
    }
}

    ungetestet

    0
  • ?

    Ich denke, das müsste

    void pre_order_traversal(Node *n) {
    if(!n) return;

    stack<Node*> to_do;
    to_do.push(n);

    do {
        Node* current = to_do.top();
        nodes.pop();

        cout << current->value << '\n';//nicht endl bitte

        /* rechte Seite nach unten, damit sie nach der linken behandelt wird. */
        if(current->right) to_do.push(current->right);
        if(current->left ) to_do.push(current->left );
    } while(!to_do.empty());
}

    heißen. Ebenfalls ungetestet.

    0
  • V

    seldon schrieb:

    Ich denke, das müsste

    if(!n) return;

...

        /* rechte Seite nach unten, damit sie nach der linken behandelt wird. */

    heißen. Ebenfalls ungetestet.

    Jo, was die Reihenfolge angeht, haste recht.

    Gegen n==NULL zu testen, davon halte ich wenig. Den NULL-Aufruf erlaubt man nur gewohnheitsmäßig, um in der rekursiven Variante sich ein wenig Tipparbeit zu sparen.

    0
  • S

    Remember OP is english... 🕶

    0
  • V

    Skym0sh0 schrieb:

    Remember OP is english... 🕶

    Die automatischen Übersetzer sind inzwischen gut genug.

    0
  • B

    Jo, about the order, hurry right.

    To test against n == NULL, which I consider low. NULL is allowed to call only habit to save the recursive variant is a little typing.

    0
Anmelden zum Antworten