二叉树的非递归遍历

二叉树同上一篇的递归遍历：
关于二叉树的非递归遍历，我们可以模拟堆栈：
先序遍历：先访问根节点，然后压入栈中，然后向左访问左子树节点，依次访问并压入栈中，当左子树为空时（如图所示），
获取栈顶元素并弹出栈顶，然后访问右子树（注意右子树不压入栈中），重复以上步骤，二叉树得以遍历。
以下是本人用自己写的栈接口实现的二叉树的非递归遍历（C语言实现）：

#include <stdio.h>
#include <stdlib.h>
#include "Linkstack.h"
struct Person
{
	struct LinkNode head;
	int age;
	struct Person* left;
	struct Person* right;
};
//中序遍历
void inorderTraversal(struct Person* root)
{
	if (NULL == root)
	{
		return;
	}
	struct Person* r = root;
	//创建初始化堆栈
	Stack stack = Init_LinkStack();
     //树非空或栈非空
	while (r || !isEmpty(stack))
	{
		//一直向左将节点压入栈中
		while (r)
		{
			Push_LinkStack(stack, r);
			r = r->left;
		}
		//如果栈非空，弹出栈顶，节点向右子树移动
		if (!isEmpty(stack))
		{
			r=Top_LinkStack(stack);
			Pop_LinkStack(stack);
			printf("%d  ", r->age);
			r = r->right;
		}
	}
}
//先序遍历
void preorderTraversal(struct Person* root)
{
	if (NULL == root)
	{
		return;
	}
	struct Person* r = root;
	//创建初始化堆栈
	Stack stack = Init_LinkStack();
	//树非空或栈非空
	while (r || !isEmpty(stack))
	{
		//一直向左将左子树压入栈中
		while (r)
		{
			printf("%d  ", r->age);
			Push_LinkStack(stack, r);
			r = r->left;
		}
		//如果栈非空，弹出栈顶，节点向右子树移动
		if (!isEmpty(stack))
		{
			r = Top_LinkStack(stack);
			Pop_LinkStack(stack);
			r = r->right;
		}
	}
}
//后序遍历
void postorderTraversal(struct Person* root)
{
	if (NULL == root)
	{
		return;
	}
	struct Person* r = root;
	//作为节点是否访问的标志
	struct Person* p = NULL;
	//创建初始化堆栈
	Stack stack = Init_LinkStack();
	//树非空或栈非空
	while (r || !isEmpty(stack))
	{
		//一直向左将左子树压入栈中
		while (r)
		{
			Push_LinkStack(stack, r);
			r = r->left;
		}
		//如果栈非空，获取栈顶
		r = Top_LinkStack(stack);
		if (r->right && r->right != p)//右子树存在，未被访问
		{
			r = r->right;
		}
		else 
		{
			Pop_LinkStack(stack);
			printf("%d  ", r->age);
			p = r;         //记录最近访问过的节点
			r = NULL;    //节点访问完后，重置r指针
		}
	}
}

下面是测试代码：

void test()
{
	struct Person p1 = { 0,1,NULL,NULL };
	struct Person p2 = { 0,2,NULL,NULL };
	struct Person p3 = { 0,3,NULL,NULL };
	struct Person p4 = { 0,4,NULL,NULL };
	struct Person p5 = { 0,5,NULL,NULL };
	struct Person p6 = { 0,6,NULL,NULL };
	struct Person p7 = { 0,7,NULL,NULL };
	struct Person p8 = { 0,8,NULL,NULL };
	struct Person p9 = { 0,9,NULL,NULL };
	struct Person p10 = { 0,10,NULL,NULL };
	struct Person p11 = { 0,11,NULL,NULL };
	struct Person p12 = { 0,12,NULL,NULL };
	struct Person p13 = { 0,13,NULL,NULL };
	p1.left = &p2;
	p1.right = &p3;
	p2.left = &p4;
	p2.right = &p5;
	p3.left = &p6;
	p3.right = &p7;
	p4.left = &p8;
	p4.right = &p9;
	p5.left = &p10;
	p5.right = &p11;
	p6.left = &p12;
	p6.right = &p13;
	printf("---------非递归先序遍历二叉树---------\n");
	preorderTraversal(&p1);
	printf("\n");
	printf("---------非递归中序遍历二叉树---------\n");
	inorderTraversal(&p1);
	printf("\n");
	printf("---------非递归后序遍历二叉树---------\n");
	postorderTraversal(&p1);
	printf("\n");
}
int main(int argc, char** argv)
{
	test();
	system("pause");
	return 0;
}

`在VS2017中代码正确执行：
二叉树的非递归遍历
下面是栈的接口声明：

#pragma once
#ifdef __cplusplus
extern"C" {
#endif // __cplusplus
#include<stdlib.h>
	//链表节点
	struct LinkNode
	{
		struct LinkNode* next;
	};
	//头节点
	struct LinkStack
	{
		struct LinkNode head;
		int size;
	};
	typedef void* Stack;
	//初始化栈
	Stack Init_LinkStack();
	//入栈
	void Push_LinkStack(Stack stack,void* data);
	//出栈
	void Pop_LinkStack(Stack stack);
	//获取栈顶
	void* Top_LinkStack(Stack stack);
	//获取栈的大小
	int Size_LinkStack(Stack stack);
	//销毁栈
	void Destroy_LinkStack(Stack stack);
	//是否为空
	int isEmpty(Stack stack);

#ifdef __cplusplus
}
#endif // __cplusplus

栈接口的具体实现：

  #include"LinkStack.h"
    typedef void* Stack;
    //初始化栈
    Stack Init_LinkStack()
    {
    	struct LinkStack* stack = malloc(sizeof(struct LinkStack));
    	if (NULL == stack)
    	{
    		return NULL;
    	}
    	stack->head.next= NULL;
    	stack->size = 0;
    	return stack;
    }
    //入栈
    void Push_LinkStack(Stack stack, void* data)
    {
    	if (NULL == stack)
    	{
    		return;
    	}
    	if (NULL == data)
    	{
    		return;
    	}
    	struct LinkStack* pstack = (struct LinkStack*)stack;
    	struct LinkNode* p = (struct LinkNode*)data;
    
    	p->next = pstack->head.next;
    	pstack->head.next = p;
    	//p->next = NULL;
    
    	++(pstack->size);
    }
    //出栈
    void Pop_LinkStack(Stack stack)
    {
    	if (NULL == stack)
    	{
    		return;
    	}
    	struct LinkStack* pstack = (struct LinkStack*)stack;
    	if (pstack->size == 0)
    	{
    		return;
    	}
    	struct LinkNode* node = pstack->head.next;
    	pstack->head.next = node->next;
    	--(pstack->size);
    }
    //获取栈顶
    void* Top_LinkStack(Stack stack)
    {
    	if (NULL == stack)
    	{
    		return NULL;
    	}
    	struct LinkStack* pstack = (struct LinkStack*)stack;
    	if (pstack->size == 0)
    	{
    		return NULL;
    	}
    	return pstack->head.next;
    }
    int Size_Link(Stack stack)
    {
    	if (NULL == stack)
    	{
    		return -1;
    	}
    	struct LinkStack* pstack = (struct LinkStack*)stack;
    	return pstack->size;
    }
    //销毁栈
    void Destroy_LinkStack(Stack stack)
    {
    	if (NULL == stack)
    	{
    		return;
    	}
    	free(stack);
    	stack = NULL;
    }
    //栈是否为空
    int isEmpty(Stack stack)
    {
    	if (NULL == stack)
    	{
    		return 0;
    	}
    	struct LinkStack* st = (struct LinkStack*)stack;
    	//if(st->size==0)
    	//    return 1;
    	return st->size==0;
    }
    //获取栈的大小
    int Size_LinkStack(Stack stack)
    {
    	if (NULL == stack)
    	{
    		return -1;
    	}
    	struct LinkStack* st = (struct LinkStack*)stack;
    	return st->size;
    }

二叉树的非递归遍历

相关推荐