博客

一.前序非递归遍历

1.前序非递归遍历原理

二叉树的非递归遍历需要借助栈来实现，将根节点压栈，再出栈顶元素，再将这个元素的左右孩子压栈（次序，右孩子先进入，左孩子后进入），重复上述操作，直至遍历结束。

2.图解

3.代码实现

定义栈结构，操作：

//链栈结构
typedef struct SNode {
	struct TNode * node;
	struct SNode* next;
}*LinkStack,StackNode;

//初始化
bool initStack(LinkStack &S) {
	S = NULL;
	return true;
}

//进栈
bool Push(LinkStack& S,TNode* e) {

	StackNode* q=(StackNode*)malloc(sizeof(StackNode));
	if (q == NULL) {
		return false;
	}
	q->node = e;
	q->next = S;
	S = q;
	return true;
}

//出栈
bool Pop(LinkStack& S,TNode* &e) {
	//这里判空是防止传过来的栈是一个空栈
	if (S == NULL) {
		return false;
	}
	StackNode* p;
	p = S;
	e = S->node;
	S = S->next;
	free(p);
	return true;
}

//判断栈空
bool isEmpty(LinkStack S) {
	if (S == NULL) {
		return true;
	}
	else
		return false;
}

定义二叉树结构及操作：

//二叉树链式结构
typedef struct TNode {
	ElemType data;
	struct TNode* lchild, * rchild;
}*BitTree,TNode;


//创建二叉树
BitTree CreateTree(BitTree &T) {
	ElemType data;
	scanf("%c", &data);		//	输入数据
	ElemType bufCh;
	bufCh = getchar();			//	消除上面输入字符回车后，存在缓冲区的 '\n'

	if (data == '#') {			//	输入# 代表此节点下子树为NULL

		return NULL;

	}
	else {
		T = (BitTree)malloc(sizeof(TNode));			//		创建结点
		if (!T) {
			printf("%s\n", strerror(errno));
			return NULL;
		}
		T->data = data;
		printf("请输入%c的左子树: ", data);
		T->lchild = CreateTree(T->lchild);					//		递归创建左子树
		printf("请输入%c的右子树: ", data);
		T->rchild = CreateTree(T->rchild);					//		开始到上一级节点的右边递归创建左右子树
		return T;							//		返回根节点
	}
}

非递归前序遍历代码实现

：

bool PreOrderNoneRecusTraerse(BitTree &T) {
	LinkStack S;
	initStack(S);
	TNode* popEle;
	Push(S, T);
	int count = 0;
	//利用栈进行遍历
	while (!isEmpty(S)) {
		Pop(S, popEle);					//栈顶元素出栈
		printf("%c ", popEle->data);
		if (popEle->rchild != NULL) 
			Push(S, popEle->rchild);	//右孩子入栈
		if (popEle->lchild != NULL)
			Push(S, popEle->lchild);	//左孩子出栈
	}
	return true;
}

测试：