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

1. stack s initialization;
2. 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;
       

The idea of ​​​​non-recursive in-order traversal

1. stack s initialization;
2. Access the left child, the left child exists and continue to step 1;
3. The left child does not have a pop-up function stack frame;
4. Access the right child, the right child exists and continue to step 1;
5. The right child does not have a pop-up function stack frame, visit this node;
6. 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:
  1. 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;
  2. 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.
  3. 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