二叉树的前、中、后序递归遍历及层次遍历

运行结果

• 二叉树采用二叉排序树生成法，所以中序输出递增序列
  

想描述的都在代码里了，这些都比较简单，直接看代码里的注释吧。

#include<iostream>

// 定义二叉树结点类型，以二叉链表作为存储二叉树的数据结构
typedef struct BTNode {
	int data;
	struct BTNode* lchild;
	struct BTNode* rchild;
	// 默认构造
	BTNode() :data(0), lchild(0), rchild(0) {}
	// 带参构造函数
	BTNode(int _data) : data(_data) {
		this->lchild = 0, this->rchild = 0;
	}
} BTNode;

// 二叉排序树的插入
int BSTInsert(BTNode*& bt, int key) {
	if (bt == 0) {
		bt = new BTNode;
		bt->lchild = bt->rchild = 0;
		bt->data = key;
		return 1;		// 插入成功标志
	}
	else {
		if (key == bt->data) return 0;		// 插入失败返回 0
		else if (key < bt->data)
			return BSTInsert(bt->lchild, key);    // 关键字小于根结点值，作为左孩子插入
		else
			return BSTInsert(bt->rchild, key);	  // 关键字大于根结点值，作为右孩子插入
	}
}

// 构造二叉排序树
void CreateBST(BTNode*& bt, int key[], int n) {
	bt = 0;			// 将树清空
	for (int i = 0; i < n; ++i) {
		BSTInsert(bt, key[i]);		// 依次将每个关键字插入到二叉排序树中
	}
}

void visit(BTNode* p) {
	std::cout << p->data << '\t';
}

// 先序遍历 （NLR）
void preOrder(BTNode* p) {
	if (!p) return;
	visit(p);
	preOrder(p->lchild);
	preOrder(p->rchild);
}

// 中序遍历 （LNR）
void inOrder(BTNode* p) {
	if (!p) return;
	inOrder(p->lchild);
	visit(p);
	inOrder(p->rchild);
}

// 后序遍历 （LRN）
void postOrder(BTNode* p) {
	if (!p) return;
	postOrder(p->lchild);
	postOrder(p->rchild);
	visit(p);
}

// 层次遍历
void level(BTNode* p) {
	int front, rear;
	const int maxSize = 20;
	BTNode* que[maxSize];  // 定义一个循环队列，用来记录将要访问的层次上的结点
	front = rear = 0;
	BTNode* q;
	if (p != 0) {
		rear = (rear + 1) % maxSize;	// 结点不为空，入队
		que[rear] = p;
		while (front != rear) {
			front = (front + 1) % maxSize;
			q = que[front];		// 队头出队
			visit(q);			// 访问、打印队头结点
			if (q->lchild != 0) {	// 如果左子树不空，则左子树的根结点入队
				rear = (rear + 1) % maxSize;
				que[rear] = q->lchild;
			}
			if (q->rchild != 0) {	// 如果右子树不空，则右子树的根结点入队
				rear = (rear + 1) % maxSize;
				que[rear] = q->rchild;
			}
		}
	}
}

int main() {
	int key[]{ 5,2,7,1,4,6,8,3 };  // 测试数组
	std::cout << "打印测试数组：\n";
	for (auto& i : key) {
		std::cout << i << '\t';
	}
	BTNode* root = new BTNode;
	// 构造二叉排序树
	CreateBST(root, key, sizeof(key) / sizeof(key[0]));

	std::cout << "\n前序输出：\n";
	preOrder(root);
	std::cout << '\n';

	std::cout << "中序输出：\n";
	inOrder(root);
	std::cout << '\n';

	std::cout << "后序输出：\n";
	postOrder(root);
	std::cout << '\n';

	std::cout << "层次输出：\n";
	level(root);
	std::cout << '\n';

	system("pause");
	return 0;
}