Traversal before, during and after binary tree

- Preface

Tree is a common data structure , It is used to simulate the data set with tree structure . Every node in the tree （ Structure ） There is a value and a list of all child nodes . Binary tree is a more typical tree structure , Each node has at most two child nodes . Next, record three traversal methods of binary tree .

- In the sequence traversal

What is the middle order traversal of binary tree ： Visit according to The left subtree —— The root node —— Right subtree The way to traverse the tree , And when you visit the left or right subtree , We traverse in the same way , Until you walk through the whole tree . First, let's talk about medium order sorting , It is because the iterative method of middle order sorting and post order sorting is similar , It's relatively easy to understand , The preorder traversal is different , Put it at the end .

- For the tree in the above figure , The result of middle order traversal should be DBEAFCG-

Recursive method

The traversal idea of the tree can obviously be realized by recursion . The exit of recursion is empty , First record the data of the current node , Then traverse first root->left After traversal root->right that will do . Recursion is easier to understand

void inorder(struct TreeNode* root, int* res, int* returnSize){
	if(root == NULL){
		return;
	}
	inorder(root->left, res, returnSize);
	res[(*returnSize)++] = root->val;
	inorder(root->right, res, returnSize);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
	int* res = (int*)malloc(sizeof(int) * 2000);
	*returnSize = 0;
	inorder(root, res, returnSize);
	return res;
}

Iterative method

The principle of iteration is very similar to recursion , They all use the idea of stack （ In the stack out of the stack ）, Recursive stack is implicit , Iteration is to use a stack directly to help traverse . Iteration method is difficult to understand , When learning, it's best to simulate the process on paper by yourself .

int* inorderTraversal(struct TreeNode* root, int* returnSize){
	int* res = (int*)malloc(sizeof(int) * 2000);
	*returnSize = 0;
	if(root == NULL){
		return res;
	}
	struct TreeNode** Node = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 501);
	//struct TreeNode* Node[500];
	int top;
	while(root != NULL || top != 0){
		while(root != NULL){
			Node[top++] = root;
			root = root->left;
		}
		root = Node[--top];
		res[(*returnSize)++] = root->val;
		root = root->right;
	}
	return res;
}

​

- After the sequence traversal

What is post order traversal of binary tree ： Visit according to The left subtree —— Right subtree —— The root node The way to traverse the tree .

- above ​​​​​​​ For this tree , The result of post order traversal should be DEBFGCA-

Recursive method

Most of the code of recursive method is the same as that of middle order , The only difference is the order in which data is recorded in recursive functions

    postorder(root->left, res, returnSize);
	postorder(root->right, res, returnSize);
	res[(*returnSize)++] = root->val;

Iterative method

The iterative method of post order traversal is roughly the same as the iterative method of middle order , The difference is that you have to Consider whether the right subtree is empty , If it is not empty, you need Put the value out of the stack into the stack again , Do not record data , And continue to traverse from the right subtree until the right subtree is empty . Set up prev The purpose of nodes is to start Mark the recorded nodes when recording the data of the right subtree , Help the subsequent stack .

int* postorderTraversal(struct TreeNode* root, int* returnSize){
	int* res = (int*)malloc(sizeof(int) * 2000);
	*returnSize = 0;
	if(root == NULL){
		return res;
	}
	struct TreeNode* Node[500];
	struct TreeNode* prev = NULL;
	int top = 0;
	while(root != NULL || top != 0){
		while(root != NULL){
			Node[top++] = root;
			root = root->left;
		}
		root = Node[--top];
		if(root->right == NULL || root->right == prev){
			res[(*returnSize)++] = root->val;
			prev = root;
			root = NULL;
		}
		else{
			Node[top++] = root;
			root = root->right;
		}
	}
	return res;
}

- The former sequence traversal

What is the preorder traversal of a binary tree ： Visit according to The root node —— The left subtree —— Right subtree The way to traverse the tree .

- above ​​​​​​​ For this tree , The result of preorder traversal should be ABDECFG-

Recursive method

The code is mostly the same as the middle order , The difference is ：

    res[(*returnSize)++] = root->val;
	preorder(root->left, res, returnSize);
	preorder(root->right, res, returnSize);

Iterative method

The difference between the iterative method of preorder sorting is that the data is stored when it is put on the stack , The specific code is as follows .

int* preorderTraversal(struct TreeNode* root, int* returnSize){
	int* res = (int*)malloc(sizeof(int) * 2000);
	*returnSize = 0;
	if(root == NULL){
		return res;
	}
	struct TreeNode* Node[500];
	int top = 0;
	while(root != NULL || top != 0){
		while(root != NULL){
			res[(*returnSize)++] = root->val;
			Node[top++] = root;
			root = root->left;
		}
		root = Node[--top];
		root = root->right;
	}
	retuen res;
}