迭代方式遍歷二叉樹
1.前序遍歷（根左右）
/**
* 前序遍歷
* @tparam T
* @param root
* @param visit
*/
template<class T>
void startOrder(TreeNode<T> *root, void (visit)(T)) {
//循環(huán)到底的情況
if (root == NULL) {
return;
}
//輸出根節(jié)點(diǎn)
visit(root->data);
//遍歷左節(jié)點(diǎn)
startOrder(root->left, visit);
//遍歷右節(jié)點(diǎn)
startOrder(root->right, visit);
}
2.中序遍歷（左根右）
/**
* 中序遍歷
* @tparam T
* @param root
* @param visit
*/
template<class T>
void centerOrder(TreeNode<T> *root, void (visit)(T)) {
if (root == NULL) {
return;
}
//先遍歷左節(jié)點(diǎn)
centerOrder(root->left, visit);
visit(root->data);
centerOrder(root->right, visit);
}
3.后序遍歷（左右根）
/**
* 后序遍歷
* @tparam T
* @param root
* @param visit
*/
template<class T>
void endOrder(TreeNode<T> *root, void (visit)(T)) {
if (root == NULL) {
return;
}
endOrder(root->left, visit);
endOrder(root->right, visit);
visit(root->data);
}
4.層序遍歷
/**
* 層序遍歷
* @tparam T
* @param root
* @param visit
*/
template<class T>
void levelOrder(TreeNode<T> *root, void (visit)(T)) {
if (root == NULL) {
return;
}
//借助隊(duì)列實(shí)現(xiàn)層序遍歷
queue<TreeNode<T> *> q;
q.push(root);
while (!q.empty()) {
TreeNode<T> *node = q.front();
q.pop();
visit(node->data);
TreeNode<T> *left = NULL;
if ((left = node->left)) {
q.push(left);
}
TreeNode<T> *right = NULL;
if ((right = node->right)) {
q.push(right);
}
}
}
