欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

基础实验4-2.3-二叉树的非递归遍历-函数题

程序员文章站 2022-03-13 15:57:12
...

基础实验4-2.3-二叉树的非递归遍历-函数题

解题代码

void InorderTraversal(BinTree BT) {
	Stack S = CreateStack();
	while (BT || !IsEmpty(S)) {
		while (BT) 	if (Push(S, BT)) BT = BT->Left;
		BT = Pop(S);
		printf(" %c", BT->Data);
		BT = BT->Right;
	}
}
void PreorderTraversal(BinTree BT) {
	Stack S = CreateStack();
	while (BT || !IsEmpty(S)) {
		while (BT) {
			if (Push(S, BT)) {
				printf(" %c", BT->Data);
				BT = BT->Left;
			}
		}
		BT = Pop(S);
		BT = BT->Right;
	}
}
void PostorderTraversal(BinTree BT) {
	Stack S = CreateStack();
	while (BT || !IsEmpty(S)) {
		while (BT) {
			if (Push(S, BT)) BT = BT->Left;
		}
		BT = Peek(S);
		if (BT->flag != 1) {
			BT->flag = 1;
			BT = BT->Right;
		}
		else {
			BT = Pop(S);
			printf(" %c",BT->Data);
			BT = NULL;
		}
	}
}

测试结果

基础实验4-2.3-二叉树的非递归遍历-函数题

问题整理

1.注意postorder的逻辑