foreword
- The author's level is limited, all the code is to learn from predecessors + some original
- Don't move the code, you must learn from it and do it yourself! ! !
train of thought
design thinking
- Creation of binary tree: Use the order of pre-order traversal to write the value of each non-empty node in turn. If there is no child node, replace it with the $ symbol. And implement it in a recursive way, creating the root node, all left subtrees, and right subtrees in turn
- Recursive traversal of the pre-, middle-, and post-order of the binary tree: the traversal order is essentially the same, but the timing of printing is different, and the timing of printing can be controlled.
The idea of non-recursive preorder traversal
- stack s initialization;
- Loop until p is empty and stack s is empty
- loop while p is not empty
- output p->data;
- Save the value of the pointer p to the stack;
- Continue to traverse the left subtree of p
- When p is empty and stack s is not empty, then
- Pop the top element of the stack to p;
- Prepare to traverse the right subtree of p;
- loop while p is not empty
The idea of non-recursive in-order traversal
- stack s initialization;
- Access the left child, the left child exists and continue to step 1;
- The left child does not have a pop-up function stack frame;
- Access the right child, the right child exists and continue to step 1;
- The right child does not have a pop-up function stack frame, visit this node;
- Pop the function stack frame and return to the upper level function stack frame.
The idea of non-recursive post-order traversal
- Start traversing from the current node:
- If the current node exists, store it in the stack, and set the node flag to 1 (the first visit), and then visit its left subtree;
- Until the current node does not exist, it needs to be rolled back. There are two situations:
- When the flag of the top node of the stack is 0, it indicates that it is going back from the left subtree. At this time, it is necessary to set the flag of the top node of the stack to 2 (the second visit), and then access its right subtree through the top node of the stack (taking the top of the stack For nodes, but not out of the stack)
- When the flag of the top node of the stack is 1, it indicates that it is going back from the right subtree. At this time, the stack needs to be popped, and the stack node is taken out for access output.
- Repeat 12 until the current node does not exist and the stack is empty.
The idea of layer order traversal
- From top to bottom, from left to right, the queue is used to store the pointers of each subtree node. Initially, the root node is enqueued. When the root node is dequeued, its left and right child nodes are enqueued (empty does not join the team), and when the left child leaves the team, its left and right child nodes join the team, ... thus the effect of hierarchical output can be produced.
full code
MyBinaryTree.h
#pragma once #include<iostream> using namespace std; typedef char E; typedef struct TreeNode { E element; struct TreeNode* left, * right; // In the post-order traversal, both the left and right subtrees need to be traversed. 0 means that the left subtree has been traversed, and 1 means that the right subtree has been traversed. int flag;//Status of flag traversal. }*Node; //the stack typedef Node T;//binary tree node pointer typedef struct StackNode { T element; struct StackNode* next; } *SNode; //queue typedef struct QueueNode { T element; struct QueueNode* next; }*QNode; typedef struct Queue { QNode front, rear; }*LinkedQueue; Node createBiTree(Node& root);//Create a binary tree in preorder order void preOrder(Node root);//Preorder traversal recursively void inOrder(Node root);//Inorder traversal recursively void postOrder(Node root);//Post-order traversal recursively //stack operation void initStack(SNode head);//Initialize the stack int pushStack(SNode head, T element);//stack int IsEmpty(SNode head);//Check if the stack is empty T peekStack(SNode head);//Get the value of the top element of the stack T popStack(SNode head);//pop out void preOrder2(Node root);//non-recursive preorder traversal void inOrder0(Node root);//Non-recursive inorder traversal low-level version void inOrder2(Node root);//Upgraded version of non-recursive inorder traversal void postOrder2(Node root);//non-recursive postorder traversal //queue operation int initQueue(LinkedQueue queue);//Initialize the queue int offerQueue(LinkedQueue queue, T element);//queue int isEmpty(LinkedQueue queue);//queue empty T pollQueue(LinkedQueue queue);//dequeue void levelOrder(Node root);//sequence traversal int getDepthTreeNode(Node root);//Find the depth of a binary tree
MyBinaryTree.cpp
#include"MyBinaryTree.h" //create binary tree //Pay attention to the use of references to avoid shallow copy errors //Program received signal SIGSEGV, Segmentation fault Node createBiTree(Node& root) { char ch; cin >> ch; if (ch == '$') { root = NULL; } else { root = (Node)malloc(sizeof(struct TreeNode)); root->element = ch; createBiTree(root->left);//build left subtree createBiTree(root->right);//build right subtree } return root; } //Preorder traversal recursively void preOrder(Node root) { if (root != NULL) { cout << root->element << " "; preOrder(root->left); preOrder(root->right); } } //Inorder traversal recursively void inOrder(Node root) { if (root == NULL) return; inOrder(root->left); cout << root->element << " "; inOrder(root->right); } //Post-order traversal recursively void postOrder(Node root) { if (root == NULL) return; postOrder(root->left); postOrder(root->right); cout << root->element << " "; } //Initialize the stack void initStack(SNode head) { head->next = NULL; } //stack int pushStack(SNode head, T element) { SNode node = (SNode)malloc(sizeof(struct StackNode)); if (node == NULL) return 0; node->next = head->next; node->element = element;//element is a node head->next = node; return true; } //Empty int IsEmpty(SNode head) { return head->next == NULL; } //Used to get the value of the top element of the stack, but not out of the stack, only the value is obtained T peekStack(SNode head) { return head->next->element;//Returns the address of the first node in the stack } //pop out T popStack(SNode head) { SNode top = head->next; head->next = head->next->next; T e = top->element; free(top); return e; } //Non-recursive implementation //preorder traversal void preOrder2(Node root) { struct StackNode stack; initStack(&stack); //Two conditions, only terminate the loop if the stack is empty and the node is NULL while (root || !IsEmpty(&stack)) { //Traverse the left subtree continuously until there is no more while (root) { cout << root->element << " ";//Then print the element value of the current node pushStack(&stack, root);//Every time a node is encountered, the node is pushed onto the stack root = root->left;//Continue to traverse the next left child node } Node node = popStack(&stack);//After the previous traversal, it is clear that all the left subtrees have been traversed, and then the right subtree is traversed //Get the right child, if there is a right child, the next round will repeat the above steps; if there is no right child, then the root here will become null, // At the beginning of the next round, the above while will be skipped directly, and the next node will be popped out of the stack, and then the right subtree will be found root = node->right; } } //Non-recursive algorithm for traversing a binary tree in order: no null pointer is pushed onto the stack void inOrder2(Node root) { struct StackNode stack; initStack(&stack); //Two conditions, only terminate the loop if the stack is empty and the node is NULL while (root || !IsEmpty(&stack)) { //Traverse the left subtree continuously until there is no more while (root) { pushStack(&stack, root);//Every time a node is encountered, the node is pushed onto the stack root = root->left;//Continue to traverse the next left child node } Node node = popStack(&stack);//After the previous traversal, it is clear that all the left subtrees have been traversed, and then the right subtree is traversed cout << node->element << " ";//Then print the element value of the current node //Get the right child, if there is a right child, the next round will repeat the above steps; if there is no right child, then the root here will become null, // At the beginning of the next round, the above while will be skipped directly, and the next node will be popped out of the stack, and then the right subtree will be found root = node->right; } } //Non-recursive algorithm for inorder traversal of binary trees: let the null pointer into the stack void inOrder0(Node root) { struct StackNode stack; initStack(&stack); T p; pushStack(&stack, root);//push the root pointer to the stack while (!IsEmpty(&stack)) { //There is the top element of the stack, and the node is not NULL while ((p = peekStack(&stack)) && p) { pushStack(&stack, p->left);//go left to the end } //Until the left child is NULL, at this time the top of the stack is the leftmost node of the whole tree, push NULL onto the stack, and the loop ends //Pop the empty node NULL at the top of the stack, because the child is NULL, there is no need to print the value p = popStack(&stack);//Null pointer unstack if (!IsEmpty(&stack)) {//The stack is not empty, visit the node, one step to the right //Pop up the top node, which is the first node in the logical inorder p = popStack(&stack); cout << p->element << " "; pushStack(&stack, p->right); //If there is a right child, the right child is pushed into the stack, and then the right child is used as the logical root node to perform in-order traversal to determine whether the right child has a left child and a right child.... //If there is no right child, push NULL onto the stack, and the next cycle will be popped and not printed } } } //post order traversal void postOrder2(Node root) { struct StackNode stack; initStack(&stack); while (root || !IsEmpty(&stack)) { while (root) { pushStack(&stack, root); root->flag = 0;//The first push to the stack can only represent the completion of the left subtree traversal, so set the flag to 0 root = root->left; } root = peekStack(&stack);//get node if (root->flag == 0) {//If only the left subtree is traversed, then flag is equal to 0 root->flag = 1;//At this time, the mark is 1, which means traversing the right subtree root = root->right; } else { cout << root->element << " ";//When the flag is 1, it means that the left and right traversal is completed, and then the value is printed out popStack(&stack);//At this time, the corresponding node is popped out of the stack, because the left and right have been traversed root = NULL;//Set NULL, skip the while in the next round, and then continue to fetch the remaining nodes in the stack, repeat the above operation } } } //Initialize the columns int initQueue(LinkedQueue queue) { //Set the head node, and point the head and tail of the team to the head node at the same time QNode node = (QNode)malloc(sizeof(struct QueueNode)); if (node == NULL) return 0; queue->front = queue->rear = node; return true; }; //enqueue int offerQueue(LinkedQueue queue, T element) { //Enter the team, put the new node into the team at the end of the team, and modify the direction of the rear QNode node = (QNode)malloc(sizeof(struct QueueNode)); if (node == NULL) return 0; node->element = element; queue->rear->next = node; queue->rear = node; return true; } //Empty int isEmpty(LinkedQueue queue) { //When the head and tail pointers point to the same node at the same time, the queue is an empty queue return queue->front == queue->rear; } //dequeue T pollQueue(LinkedQueue queue) { //queue->front —— head node //queue->front->next->element --The address of the node stored in the queue head node T e = queue->front->next->element; //queue->front->next -- the head of the queue QNode qNode = queue->front->next; //Update the head node of the chain queue queue->front->next = queue->front->next->next; //qNode=qNode->next; //If there is only one node in the queue, point the tail pointer to the set head node if (queue->rear == qNode) queue->rear = queue->front; free(qNode); //Returns the node address of the deleted old queue head node, and does not physically delete, but only releases the node space of the queue return e; } //sequence traversal void levelOrder(Node root) { struct Queue queue;//create queue initQueue(&queue); offerQueue(&queue, root);//First put the root node into the queue while (!isEmpty(&queue)) { Node node = pollQueue(&queue); cout << node->element << " "; if (node->left) //If the left and right children, enqueue the left and right children in turn offerQueue(&queue, node->left); if (node->right) offerQueue(&queue, node->right); } } //Find the depth of a binary tree int getDepthTreeNode(Node root) { if (root == NULL) { return 0; } else { int lLength = getDepthTreeNode(root->left); int rlength = getDepthTreeNode(root->right); int max = rlength > lLength ? (rlength + 1) : (lLength + 1); return max; } };
Main.cpp
#include"MyBinaryTree.h" int main() { cout << "1--create binary tree" << endl; cout << "2--Preorder traversal of a binary tree [recursive method]" << endl; cout << "3--Inorder traversal of a binary tree [recursive method]" << endl; cout << "4--Post-order traversal of a binary tree [recursive method]" << endl; cout << "5--Preorder traversal of a binary tree [non-recursive method]" << endl; cout << "6--Inorder traversal of a binary tree [non-recursive method 1]" << endl; cout << "7--Inorder traversal of a binary tree [non-recursive method 2]" << endl; cout << "8--Post-order traversal of a binary tree [non-recursive method]" << endl; cout << "9--Level order traversal of a binary tree" << endl; cout << "10--Find the depth of a binary tree" << endl; cout << "-1--quit" << endl; int option; Node t;//Define a Node pointer t = NULL;//If you don’t do the initial knowledge, you will report an error do { cout << "please enter selection:"; cin >> option; switch (option) { case 1: cout << "Please enter the values of the nodes in the binary tree in order(a character)$character represents an empty tree:"; t = createBiTree(t); if (t) { cout << "Successfully created binary tree!" << endl; } break; case 2: cout << "Preorder traversal [recursive implementation]:"; preOrder(t); cout << endl; break; case 3: cout << "Inorder traversal of a binary tree [recursive method]"; inOrder(t); cout << endl; break; case 4: cout << "Post-order traversal of a binary tree [recursive method]"; postOrder(t); cout << endl; break; case 5: cout << "Preorder traversal of a binary tree [non-recursive method]"; preOrder2(t); cout << endl; break; case 6: cout << "Inorder traversal of a binary tree [non-recursive method 1]"; inOrder0(t); cout << endl; break; case 7: cout << "Inorder traversal of a binary tree [non-recursive method 2]"; inOrder2(t); cout << endl; break; case 8: cout << "Post-order traversal of a binary tree [non-recursive method]"; postOrder2(t); cout << endl; break; case 9: cout << "Level order traversal of binary tree [non-recursive implementation]"; levelOrder(t); cout << endl; break; case 10: cout << "The depth of the binary tree is:"; cout << getDepthTreeNode(t) << endl; break; case -1: cout << "Thanks for using! goodbye!" << endl; return 0; default: cout << "Please enter the correct operation!"; break; } } while (option != -1); }
Show results