二叉树的创建以及遍历方式

这里我用的是先序序列建立二叉树，'#'表示空树。

二叉树用的是链式储存结构。

其中非递归涉及到的栈，我是使用了C++的STL类库 。

加上头文件#include即可

#include
#include
using namespace std;

typedef char ElemType;
typedef int Status;
const int OK = 1;
const int ERROR = 0;

typedef struct BiTNode {
	ElemType data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;

Status CreateBiTree(BiTree& B) {
	char ch;
	cin >> ch;
	// '#' 表示空树
	if (ch=='#')
		B = NULL;
	else {
		if (!(B = (BiTNode*)malloc(sizeof(BiTNode))))
			exit(-1);
		B->data = ch;
		CreateBiTree(B->lchild);
		CreateBiTree(B->rchild);
	}
	return OK;
}

// 先序遍历（递归）
void PreOrderTraverse(BiTree B) {
	if (B) {
		cout << B->data << " ";
		PreOrderTraverse(B->lchild);
		PreOrderTraverse(B->rchild);
	}
}

// 先序遍历（非递归）
void PreOrderTraverse_f(BiTree B) {
	stack S;
	BiTNode* p = B;
	S.push(p);
	while (p && !empty(S)) {
		p = S.top();
		S.pop();
		cout << p->data << " ";
		if (p->rchild)
			S.push(p->rchild);
		if (p->lchild)
			S.push(p->lchild);
	}
}

// 中序遍历（递归）
void InOrderTraverse(BiTree B) {
	if (B) {
		InOrderTraverse(B->lchild);
		cout << B->data << " ";
		InOrderTraverse(B->rchild);
	}
}

// 中序遍历（非递归）
void InOrderTraverse_f(BiTree B) {
	stack S;
	BiTNode* p = B;
	while (p || !empty(S)) {
		if (p) {
			S.push(p);
			p = p->lchild;
		}
		else {
			p = S.top();	// 取栈顶元素
			S.pop();		// 栈顶出栈
			cout << p->data << " ";
			p = p->rchild;
		}
	}
}

// 后序遍历（递归）
void LastOrderTraverse(BiTree B) {
	if (B) {
		LastOrderTraverse(B->lchild);
		LastOrderTraverse(B->rchild);
		cout << B->data << " ";
	}
}

// 后序遍历（非递归）
void LastOrderTraverse_f(BiTree B) {
	stack S;
	BiTNode* p = B;
	BiTNode* last;
	int flag = 0;
	do {
		while (p != NULL) {
			S.push(p);
			p = p->lchild;
		}
		last = NULL;	// 上一个打印的结点
		flag = 1;
		while (flag && !empty(S)) {
			p = S.top();	// 取栈顶元素
			if (p->rchild == last) {
				S.pop();
				cout << p->data << " ";
				last = p;
			}
			else {
				p = p->rchild;
				flag = 0;
			}
		}

	} while (!empty(S));
}


int main() {
	BiTree B;
	cout << "请按先序序列输入每个结点，'#' 表示空树n";
	CreateBiTree(B);
	cout << "先序遍历为：tt";
	PreOrderTraverse(B);

	cout << "n先序遍历（非递归）为：t";
	PreOrderTraverse_f(B);

	cout << "nn中序遍历为：tt";
	InOrderTraverse(B);

	cout << "n中序遍历（非递归）为：t";
	InOrderTraverse_f(B);
	
	cout << "nn后序遍历为：tt";
	LastOrderTraverse(B);

	cout << "n后序遍历（非递归）为：t";
	LastOrderTraverse_f(B);
	return 0;
}

例如：

输入：A B C # # D E # G # # F # # # 

程序运行结果为：