先序遍历

根->左子树->右子树

1
2
3
4
5
6
7
void BiTree::PreOrder(BiNode* B) {
	if (B) {
		cout << B->data << endl;
		PreOrder(B->left);
		PreOrder(B->right);
	}
}

中序遍历

左子树->根->右子树

1
2
3
4
5
6
7
void BiTree::InOrder(BiNode* B) {
	if (B) {
		PreOrder(B->left);
		cout << B->data << endl;
		PreOrder(B->right);
	}
}

后序遍历

左子树->右子树->根

1
2
3
4
5
6
7
void BiTree::PostOrder(BiNode* B) {
	if (B) {
		PreOrder(B->left);
		PreOrder(B->right);
		cout << B->data << endl;
	}
}

层序遍历

第一层->第二层->…->最后一层

通常的遍历，结点在访问后便被丢弃

要想做到层序的效果，我们需要在访问一个结点时，要注意存下其左右结点（注意判空）

1
2
3
4
5
6
7
8
9
10
11
12
13
void BiTree::LevelOrder(BiNode* B) {
	BiNode* BQ[100]; 	//队列，用于存放结点
	BiNode* p;			//取出的当前队列最前方结点
	int l = 0, r = 0;
	if(B) BQ[r++] = B;	//判空

	while (l != r) {	//跳出循环的条件是队列为空（左右相遇即为空）
		p = BQ[l++];
		cout << p->data << endl;
		if (p->left)BQ[r++] = p->left;		//存入左结点
		if (p->right)BQ[r++] = p->right;	//存入右结点
	}
}