Binary tree preorder traversal stack and recursive writing

See the code for specific implementation

The simulated binary tree is used here. The real binary tree needs to be created recursively or circularly.

Linked list stack and recursive writing

#include <iostream>
#include <cstdio>
#include <malloc.h>

using namespace std;
/*
 * Implementation logic of preorder traversal stack
 * The root left right node is pushed into the stack and output into the leaf node Popped the parent node traverses the right subtree
 * */

struct treeNode {
    int a; // data member
    struct treeNode *pFather; // parent node
    struct treeNode *pLeft; // left child
    struct treeNode *pRight; // right child
};

// The stack of the linked list structure, the tail is added and the tail is deleted, and the two-way linked list with an empty head
// stack node
struct stack {
    struct treeNode *node; // point to the node of the tree
    struct stack *pre; // point to the previous node
    struct stack *next; // point to the next node
};
struct stack head; // empty head
struct stack *stacktop = & amp;head; // stack top pointer

// Add to the end of the linked list
void push(struct treeNode *node) {
    // Apply for nodes and assign values to members
    struct stack *temp = (struct stack *)malloc(sizeof(struct stack));
    if (NULL == temp) {
        return;
    }
    // assign initial value
    temp->pre = NULL;
    temp->next = NULL;
    temp->node = node;
    // tail connection
    stacktop->next = temp;
    temp->pre = stacktop;
    // Move the stack top pointer back
    stacktop = stacktop->next;
}

// Pop the stack and delete the end of the doubly linked list
struct treeNode *pop(void) {
    if (stacktop == & head) {
        // stack is empty
        return NULL;
    }
    struct treeNode *temp = stacktop->node; // Get the tree node at the top of the stack

    stacktop = stacktop->pre; // move the node forward
    free(stacktop->next); // release the node
    stacktop->next = NULL; // new tail pointer points to NULL
    return temp;
}

// Preorder traversal recursive writing
void pre_look(struct treeNode *root) {
    if (root != NULL) {
        printf("%d ", root->a);
        pre_look(root->pLeft);
        pre_look(root->pRight);
    }
}

// Preorder traversal stack writing method
void preLookByStack(struct treeNode *root) {
    if (NULL == root)
        return;
    struct treeNode *tp = root;
    // Infinite loop inside break
    while (NULL != tp || stacktop != &head) {
        // The left subtree is pushed into the stack and output until the leaf
        while (tp != NULL) {
            printf("%d ", tp->a);
            push(tp);
            tp = tp->pLeft;
        }
        struct treeNode *t = pop(); // pop out
        tp = t->pRight;
       // if (NULL == tp & amp; & amp; stacktop == & amp;head) // stack is empty and last node has no children
         // break;
    }
}

int main() {
    struct treeNode t1 = { 1 };
    struct treeNode t2 = { 2 };
    struct treeNode t3 = { 3 };
    struct treeNode t4 = { 4 };
    struct treeNode t5 = { 5 };
    struct treeNode t6 = { 6 };
    struct treeNode t7 = { 7 };
    struct treeNode t8 = { 8 };
    struct treeNode t9 = { 9 };
    struct treeNode t10 = { 10 };

    // Link
    t1.pLeft = &t2;
    t1.pRight = &t3;
    t1.pFather = NULL;

    t2.pLeft = &t4;
    t2.pRight = &t5;
    t2.pFather = &t1;

    t3.pRight = &t6;
    t3.pLeft = NULL;
    t3.pFather = &t1;

    t4.pLeft = NULL;
    t4.pRight = NULL;
    t4.pFather = &t2;

    t5.pLeft = &t7;
    t5.pRight = &t8;
    t5.pFather = &t2;

    t6.pLeft = &t9;
    t6.pRight = &t10;
    t6.pFather = &t3;

    t7.pLeft = NULL;
    t7.pRight = NULL;
    t7.pFather = &t5;

    t8.pLeft = NULL;
    t8.pRight = NULL;
    t8.pFather = &t5;

    t9.pLeft = NULL;
    t9.pRight = NULL;
    t9.pFather = &t6;

    t10.pLeft = NULL;
    t10.pRight = NULL;
    t10.pFather = &t6;
    printf("Recursive preorder traversal:\\
");
    pre_look( & t1);
    printf("\\
Preorder traversal of stack writing method (two-way linked list with empty head):\\
");
    preLookByStack( & t1);

    return 0;
}

Pre-order traversal array stack writing method

//
// Created by Cauchyshy on 5/23/2023.
//

#include <iostream>
#include <cstdio>
using namespace std;

// The depth of the tree is 4. Here our example is 4, which is the same as the number of layers
#define TREE_DEEP 5

struct treeNode {
    int a; // data member
    struct treeNode *pFather; // parent node
    struct treeNode *pLeft; // left child
    struct treeNode *pRight; // right child
};

// Since there is no need for front and rear pointers, you can directly use the leaf pointer type to install the address of the tree
struct treeNode *stack[TREE_DEEP] = {0};

// Use the subscript to indicate the top of the stack Top of the stack
int stacktop = -1; // -1 means an empty stack because the subscript starts from 0, and the 0 element is an element in the stack

// push
void push(struct treeNode *node) {
    if (NULL == node)
        return;
    stacktop + + ; // The top of the stack is first incremented by 1
    stack[stacktop] = node; // then assign a value to the top of the stack
}

// pop out
struct treeNode * pop(void) {
    if (stacktop == -1)
        return NULL;
    int pre = stacktop;
    stacktop--;
    return stack[pre];
}

// Preorder traversal recursive writing
void pre_look(struct treeNode *root) {
    if (root != NULL) {
        printf("%d ", root->a);
        pre_look(root->pLeft);
        pre_look(root->pRight);
    }
}

// Preorder traversal array stack writing method
void preLookByArray(struct treeNode *root) {
    if (NULL == root)
        return;
    struct treeNode *tp = root;
    while (1) {
        // The left subtree is pushed onto the stack until the leaf
        while (tp != NULL) {
            printf("%d " , tp->a);
            push(tp);
            tp = tp->pLeft;
        }
        if (stacktop == -1)
            break;
        struct treeNode *t = pop();
        tp = t->pRight;
    }
}

int main() {
    struct treeNode t1 = { 1 };
    struct treeNode t2 = { 2 };
    struct treeNode t3 = { 3 };
    struct treeNode t4 = { 4 };
    struct treeNode t5 = { 5 };
    struct treeNode t6 = { 6 };
    struct treeNode t7 = { 7 };
    struct treeNode t8 = { 8 };
    struct treeNode t9 = { 9 };
    struct treeNode t10 = { 10 };

    // Link
    t1.pLeft = &t2;
    t1.pRight = &t3;
    t1.pFather = NULL;

    t2.pLeft = &t4;
    t2.pRight = &t5;
    t2.pFather = &t1;

    t3.pRight = &t6;
    t3.pLeft = NULL;
    t3.pFather = &t1;

    t4.pLeft = NULL;
    t4.pRight = NULL;
    t4.pFather = &t2;

    t5.pLeft = &t7;
    t5.pRight = &t8;
    t5.pFather = &t2;

    t6.pLeft = &t9;
    t6.pRight = &t10;
    t6.pFather = &t3;

    t7.pLeft = NULL;
    t7.pRight = NULL;
    t7.pFather = &t5;

    t8.pLeft = NULL;
    t8.pRight = NULL;
    t8.pFather = &t5;

    t9.pLeft = NULL;
    t9.pRight = NULL;
    t9.pFather = &t6;

    t10.pLeft = NULL;
    t10.pRight = NULL;
    t10.pFather = &t6;
    printf("Recursive preorder traversal:\\
");
    pre_look( & t1);
    printf("\\
Array stack preorder traversal:\\
");
    preLookByArray( & t1);


    return 0;
}