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; }