Tree Traversal

Tree traversal is a process of visiting each node in the tree exactly once in some order.

树的遍历有2种方式，Breadth-first（广度优先）和Depth-first（深度优先）。

Breadth-first（广度优先）

按照广度优先，对二叉树的遍历方式主要是Level-order（层序遍历）。

Level-order（层序遍历）

层序遍历即对一个二叉树每层从上到下，从左到右进行遍历。

上图层序遍历顺序即为F D J B E G K A C I H.

实现

用队列可以实现层序遍历。因为队列有First-In-First-Out(FIFO)原则，我们可以先让root进入队列，在访问节点时，让其左右节点进入队列。

实现层序遍历的代码如下：

代码

#include<queue>//可以直接调用库函数使用队列，其基本语法与Stack类似
void LevelOrder(BstNode* root) {
	if (root == NULL)return;
	queue<BstNode*> Q;
	Q.push(root);
	while (!Q.empty()) {
		BstNode* current = Q.front();
		cout << current->data << " ";
		if (current->left != NULL)Q.push(current->left);
		if (current->right != NULL)Q.push(current->right);
		Q.pop();
	}
}

Depth-first（深度优先）

深度优先有三个排序方法，Preorder（前序）、Inorder（中序）和Postorder（后序）。

类型 Order
Preorder <root><left><right>(DLR)
Inorder <left><root><right>(LDR)
Postorder <left><right><root>(LRD)

上图三种不同方式的排列顺序分别为：

Preorder: F D B A C E J G I H K

Inorder: A B C D E F G H I J K

Postorder: A C B E D H I G K J F

实现

三种顺序都可以用递归来简洁地写出，代码如下：

代码

void Preorder(BstNode* root) {
	if (root == NULL)return;
	printf("%d ", root->data);
	Preorder(root->left);
	Preorder(root->right);
}
void Inorder(BstNode* root) {
	if (root == NULL)return;
	Inorder(root->left);
	printf("%d ", root->data);
	Inorder(root->right);
}
void Postorder(BstNode* root) {
	if (root == NULL)return;
	Postorder(root->left);
	Postorder(root->right);
	printf("%d ", root->data);
}

最后附上完整代码，输出树的高度，层序遍历，前序，中序，后序

#include<iostream>
#include<queue>
using namespace std;
struct BstNode {
	int data;
	BstNode* left;
	BstNode* right;
};
void LevelOrder(BstNode* root) {
	if (root == NULL)return;
	queue<BstNode*> Q;
	Q.push(root);
	while (!Q.empty()) {
		BstNode* current = Q.front();
		cout << current->data << " ";
		if (current->left != NULL)Q.push(current->left);
		if (current->right != NULL)Q.push(current->right);
		Q.pop();
	}
	printf("\n");
}
void Preorder(BstNode* root) {
	if (root == NULL)return;
	printf("%d ", root->data);
	Preorder(root->left);
	Preorder(root->right);
}
void Inorder(BstNode* root) {
	if (root == NULL)return;
	Inorder(root->left);
	printf("%d ", root->data);
	Inorder(root->right);
}
void Postorder(BstNode* root) {
	if (root == NULL)return;
	Postorder(root->left);
	Postorder(root->right);
	printf("%d ", root->data);
}
BstNode* GetNewNode(int data) {
	BstNode* NewNode = new BstNode();
	NewNode->data = data;
	NewNode->left = NewNode->right = NULL;
	return NewNode;
}
BstNode* Insert(BstNode* root,int data) {
	if (root == NULL)
		root = GetNewNode(data);
	else if (data <= root->data) {
		root->left = Insert(root->left, data);
	}
	else
		root->right = Insert(root->right, data);
	return root;
}
int max(int a, int b) {
	if (a > b)return a;
	else return b;
}
int FindHeight(BstNode* root) {
	if (root == NULL) {
		return -1;
	}
	return max(FindHeight(root->left), FindHeight(root->right)) + 1;
}
int main() {
	BstNode* root = NULL;
	root = Insert(root,3);
	root = Insert(root, 6);
	root = Insert(root, 2);
	root = Insert(root, 1);
	root = Insert(root, 7);
	root = Insert(root, 5);
	root = Insert(root, 8);
	root = Insert(root, 4);
	printf("Height of tree is %d\n", FindHeight(root));
	cout << "LevelOrder:"; LevelOrder(root);
	cout << "Preorder:"; Preorder(root); cout << endl;
	cout << "Inorder:"; Inorder(root); cout << endl;
	cout << "Postorder:"; Postorder(root);
	return 0;
}