前序遍历 中序遍历 后序遍历是什么玩意

　　二叉树的遍历

　　基本上有4种遍历方法，先、中、后根，逐层。

　　1. 前序遍历

public:

void PreOrder(void (*visit)(T &data) = print) { PreOrder(root, visit); }

private:

void PreOrder(BTNode* p, void (*visit)(T &data))

{

if (p){ visit(p->data); PreOrder(p->left, visit); PreOrder(p->right, visit); }

}

　　2. 中序遍历

public:
void InOrder(void (*visit)(T &data) = print) { InOrder(root, visit); }
private:
void InOrder(BTNode* p, void (*visit)(T &data))
{
if (p){ InOrder(p->left, visit); visit(p->data); InOrder(p->right, visit); }
}

　　3. 后序遍历

public:
void PostOrder(void (*visit)(T &data) = print) { PostOrder(root, visit); }
private:
void PostOrder(BTNode* p, void (*visit)(T &data))
{
if (p){ PostOrder(p->left, visit); PostOrder(p->right, visit); visit(p->data); }
}

　　4. 层次遍历

void LevelOrder(void (*visit)(T &data) = print)
{
queue< BTNode* > a; BTNode* p = root;//记得#include
while (p)
{
visit(p->data);
if (p->left) a.push(p->left); if (p->right) a.push(p->right);
if (a.empty()) break; p = a.front(); a.pop();
}
}
　　附注：缺省的visit函数print如下
private:
static void print(T &data) { cout << data << ' ';｝