四种常用的遍历二叉树的算法：
- DLR先序遍历
- LDR中序遍历
- LRD后序遍历
- 层次遍历
以下是简单的C++实现
#include <iostream>
#include <queue>
using namespace std;
typedef char ElemType;
typedef struct BNode {
ElemType data;
struct BNode *lchild, *rchild;
}BNode, *BTree;
void func(BTree &T) {
cout << T->data << endl;
}
void createByNote(BTree &T) {
char ch;
cin >> ch;
if (ch == '#')
T = NULL;
else {
T = new BNode;
T->data = ch;
createByNote(T->lchild);
createByNote(T->rchild);
}
}
void preOrder(BTree T) {
if (T) {
func(T);
preOrder(T->lchild);
preOrder(T->rchild);
}
}
void inOrder(BTree T) {
if (T) {
inOrder(T->lchild);
func(T);
inOrder(T->rchild);
}
}
void posOrder(BTree T) {
if (T) {
posOrder(T->lchild);
posOrder(T->rchild);
func(T);
}
}
void a(BTree T) {
cout << "preOrder:" << endl;
preOrder(T);
cout << "inOrder:" << endl;
inOrder(T);
cout << "posOrder:" << endl;
posOrder(T);
}
bool levelTraverse(BTree T) {
if (!T) return false;
BTree p;
queue<BTree> Q;
Q.push(T);
while (!Q.empty()) {
p = Q.front();
Q.pop();
func(T);
if (p->lchild != NULL)
Q.push(p->lchild);
if (p->rchild != NULL)
Q.push(p->rchild);
}
return true;
}
int main() {
BTree T1;
createByNote(T1);
levelTraverse(T1);
return 0;
}
