看数据结构写代码(24) 二叉链表的递归遍历和非递归遍历算法总结

时间：2015-03-24 11:09:37 阅读：227 评论：0 收藏：0 [点我收藏+]

二叉链表的遍历是二叉链表各种操作的基础，例如：创建二叉树;求树的长度；求树的叶子节点数；求节点的层数；求树的深度，宽度等等。

总之不掌握遍历，就没有掌握二叉树；

二叉链表的遍历根据根节点的访问顺序有：先（根节点）序，中（根节点）序，后（根节点）序，和层序；

算法思路有两类：

1. 递归算法，算法清晰，容易证明算法的正确性，但是效率较低和受系统栈区大小的限制，不能递归太多层次

2.非递归算法，算法较复杂一些，但是效率高，又不受栈区大小的限制

下面讲解这两种算法：

1.递归算法，递归没什么说的，比较简单

//递归算法 先序
void preOrderTraverse(Tree tree){
	if (tree != NULL)
	{
		printf("%d\t",tree->data);
		preOrderTraverse(tree->leftChild);
		preOrderTraverse(tree->rightChild);
	}
}
//递归算法 中序
void inOrderTraverse(Tree tree){
	if (tree != NULL)
	{
		inOrderTraverse(tree->leftChild);
		printf("%d\t",tree->data);
		inOrderTraverse(tree->rightChild);
	}
}
//递归算法 后序
void postOrderTraverse(Tree tree){
	if (tree != NULL)
	{
		postOrderTraverse(tree->leftChild);
		postOrderTraverse(tree->rightChild);
		printf("%d\t",tree->data);
	}
}

2.重点讲解非递归算法，非递归算法需要借助栈（先，中，后序）或者队列（层序）来进行遍历。

2.1 非递归先序算法总共有三种方法：

下面的两种算法思路一致，都是找左子树最左下角节点的同时访问节点，然后将节点的右子树入栈。然后重复寻找..

void preOrderTraverse1(Tree t){
	linkStack stack;
	stackInit(&stack);
	stackPush(&stack,t);
	while (!stackEmpty(stack))
	{
		while (stackGetTop(stack,&t) && t)
		{
			printf("%d\t",t->data);
			stackPush(&stack,t->leftChild);
		}
		stackPop(&stack,&t);//NULL 出栈
		if (!stackEmpty(stack))
		{
			stackPop(&stack,&t);
			stackPush(&stack,t->rightChild);
		}
	}
	stackDestory(&stack);
}

void preOrderTraverse2(Tree tree){
	linkStack stack;
	stackInit(&stack);
	while (tree || !stackEmpty(stack))
	{
		if (tree)
		{
			printf("%d\t",tree->data);
			stackPush(&stack,tree);
			tree = tree->leftChild;
		}
		else
		{
			stackPop(&stack,&tree);
			tree = tree->rightChild;
		}
	}
	stackDestory(&stack);
}

第三种思路较前两种清晰，更加易懂

1.空树不操作 2.将树根入栈 3.访问根节点 4. 右子树不为空，将右子树入栈 5. 左子树不为空，将左子树入栈 6.重复 3~ 5 步

比较奇思妙想的是先将右子树入栈，再将左子树入栈，这样每次都先访问栈顶的左子树。

void preOrderTraverse3(Tree tree){
	if (tree != NULL)
	{
		linkStack stack;
		stackInit(&stack);
		stackPush(&stack,tree);
		while (!stackEmpty(stack))
		{
			stackPop(&stack,&tree);
			printf("%d\t",tree->data);
			if (tree->rightChild != NULL)
			{
				stackPush(&stack,tree->rightChild);
			}
			if (tree->leftChild != NULL)
			{
				stackPush(&stack,tree->leftChild);
			}
		}
	}
}

2.2 非递归中序有两种算法

算法思路同先序前两种算法的思路一致，只是先序是在在找左子树的时候访问，而终须是在退栈的时候访问

//中序非递归
void inOrderTraverse1(Tree tree){
	linkStack stack;
	stackInit(&stack);
	stackPush(&stack,tree);
	while (!stackEmpty(stack))
	{
		while (stackGetTop(stack,&tree) && tree) stackPush(&stack,tree->leftChild);
		stackPop(&stack,&tree);
		if (!stackEmpty(stack))
		{
			stackPop(&stack,&tree);
			printf("%d\t",tree->data);
			stackPush(&stack,tree->rightChild);
		}
	}
	stackDestory(&stack);
}

void inOrderTraverse2(Tree tree){
	linkStack stack;
	stackInit(&stack);
	while (tree || !stackEmpty(stack))
	{
		if (tree)
		{
			stackPush(&stack,tree);
			tree = tree->leftChild;
		}
		else
		{
			stackPop(&stack,&tree);
			printf("%d\t",tree->data);
			tree = tree->rightChild;
		}
	}
	stackDestory(&stack);
}

2.3 后序遍历是所有遍历中最难的一种
我在网上研究了一番，发现了一种思路比较清晰的算法。

大致的思路是：只有底下三种情况的时候访问根节点。

1. 节点的左子树为空并且右子树为空，2. 刚访问过右子树 3. 刚访问过左子树并且右子树为空的时候

这个算法需要记住上一个访问的节点和利用先右子树入栈后左子树入栈，始终先访问左子树。

void postOrderTraverse1(Tree tree){
	if (tree != NULL)
	{
		linkStack stack;
		stackInit(&stack);
		stackPush(&stack,tree);
		Tree pre = NULL;
		while (!stackEmpty(stack))
		{
			stackGetTop(stack,&tree);
			//左右子树都为空，或者 左子树刚访问过，并且 右子树为空，或者 刚访问过 右子树. 可以直接访问
			if ((tree->leftChild == NULL && tree->rightChild == NULL) || (pre != NULL && (tree->leftChild == pre || tree->rightChild == pre)))
			{
				printf("%d\t",tree->data);
				stackPop(&stack,&tree);
				pre = tree;
			}
			else
			{
				if (tree->rightChild != NULL)
				{
					stackPush(&stack,tree->rightChild);
				}
			        if(tree->leftChild != NULL)
				{
					stackPush(&stack,tree->leftChild);
				}
			}
		}
	}
}

2.4 层序访问，是按从上到下，从左到右的顺序访问树。这时候我们需要借助队列。

这个算法有一个特点，左子树一定在右子树前访问，左子树的孩子一定在右子树的孩子前访问。

大概的思路：1. 将根节点入队列，访问根节点 2. 将左子树入队列， 3.将右子树入队列 4.重复 1~3

//层序
//利用队列
void levelOrderTraverse(Tree tree){
	if (tree != NULL)
	{
		LinkQueue queue;
		queueInit(&queue);
		enqueue(&queue,tree);
		while (dequeue(&queue,&tree) && tree)
		{
			printf("%d\t",tree->data);
			if (tree->leftChild != NULL)
			{
				enqueue(&queue,tree->leftChild);
			}
			if (tree->rightChild != NULL)
			{
				enqueue(&queue,tree->rightChild);
			}
		}
		queueDestory(&queue);
	}
}

下面给出完整代码，其中栈和队列的部分代码没有贴出，可以从我以前的代码中摘取。

// binaryTree.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <cstdlib>
#include "stack.h"
#include "queue.h"

typedef int ElementType;

typedef  struct TreeNode
{
	ElementType data;
	TreeNode * leftChild;
	TreeNode * rightChild;
} * Tree;

void treeInit(Tree * tree){
	*tree = NULL;
}
//其实 自己 不懂 这个 函数 初始化...
E_State treeCreate(Tree *tree){
	ElementType data;
	scanf("%d",&data);
	if (data == 0)
	{
		*tree = NULL;
	}else
	{
		*tree = (Tree)malloc(sizeof(TreeNode));
		(*tree)->data = data;
		treeCreate(&(*tree)->leftChild);
		treeCreate(&(*tree)->rightChild);
	}
	return E_State_Ok;
}


//后序遍历
void treeClear(Tree * tree){
	if (tree != NULL)
	{
		if ((*tree)->leftChild != NULL)
		{
			treeClear(&(*tree)->leftChild);
		}
		else if((*tree)->rightChild != NULL)
		{
			treeClear(&(*tree)->rightChild);
		}
		free(*tree);
		*tree = NULL;
	}
}

void treeDestory(Tree * tree){
	treeClear(tree);
}
//递归算法 先序
void preOrderTraverse(Tree tree){
	if (tree != NULL)
	{
		printf("%d\t",tree->data);
		preOrderTraverse(tree->leftChild);
		preOrderTraverse(tree->rightChild);
	}
}
//递归算法 中序
void inOrderTraverse(Tree tree){
	if (tree != NULL)
	{
		inOrderTraverse(tree->leftChild);
		printf("%d\t",tree->data);
		inOrderTraverse(tree->rightChild);
	}
}
//递归算法 后序
void postOrderTraverse(Tree tree){
	if (tree != NULL)
	{
		postOrderTraverse(tree->leftChild);
		postOrderTraverse(tree->rightChild);
		printf("%d\t",tree->data);
	}
}

//非递归 算法

void preOrderTraverse1(Tree t){
	linkStack stack;
	stackInit(&stack);
	stackPush(&stack,t);
	while (!stackEmpty(stack))
	{
		while (stackGetTop(stack,&t) && t)
		{
			printf("%d\t",t->data);
			stackPush(&stack,t->leftChild);
		}
		stackPop(&stack,&t);//NULL 出栈
		if (!stackEmpty(stack))
		{
			stackPop(&stack,&t);
			stackPush(&stack,t->rightChild);
		}
	}
	stackDestory(&stack);
}

void preOrderTraverse2(Tree tree){
	linkStack stack;
	stackInit(&stack);
	while (tree || !stackEmpty(stack))
	{
		if (tree)
		{
			printf("%d\t",tree->data);
			stackPush(&stack,tree);
			tree = tree->leftChild;
		}
		else
		{
			stackPop(&stack,&tree);
			tree = tree->rightChild;
		}
	}
	stackDestory(&stack);
}

void preOrderTraverse3(Tree tree){
	if (tree != NULL)
	{
		linkStack stack;
		stackInit(&stack);
		stackPush(&stack,tree);
		while (!stackEmpty(stack))
		{
			stackPop(&stack,&tree);
			printf("%d\t",tree->data);
			if (tree->rightChild != NULL)
			{
				stackPush(&stack,tree->rightChild);
			}
			if (tree->leftChild != NULL)
			{
				stackPush(&stack,tree->leftChild);
			}
		}
	}
}

//中序非递归
void inOrderTraverse1(Tree tree){
	linkStack stack;
	stackInit(&stack);
	stackPush(&stack,tree);
	while (!stackEmpty(stack))
	{
		while (stackGetTop(stack,&tree) && tree) stackPush(&stack,tree->leftChild);
		stackPop(&stack,&tree);
		if (!stackEmpty(stack))
		{
			stackPop(&stack,&tree);
			printf("%d\t",tree->data);
			stackPush(&stack,tree->rightChild);
		}
	}
	stackDestory(&stack);
}

void inOrderTraverse2(Tree tree){
	linkStack stack;
	stackInit(&stack);
	while (tree || !stackEmpty(stack))
	{
		if (tree)
		{
			stackPush(&stack,tree);
			tree = tree->leftChild;
		}
		else
		{
			stackPop(&stack,&tree);
			printf("%d\t",tree->data);
			tree = tree->rightChild;
		}
	}
	stackDestory(&stack);
}



void postOrderTraverse1(Tree tree){
	if (tree != NULL)
	{
		linkStack stack;
		stackInit(&stack);
		stackPush(&stack,tree);
		Tree pre = NULL;
		while (!stackEmpty(stack))
		{
			stackGetTop(stack,&tree);
			//左右子树都为空，或者 左子树刚访问过，并且 右子树为空，或者 刚访问过 右子树. 可以直接访问
			if ((tree->leftChild == NULL && tree->rightChild == NULL) || (pre != NULL && (tree->leftChild == pre || tree->rightChild == pre)))
			{
				printf("%d\t",tree->data);
				stackPop(&stack,&tree);
				pre = tree;
			}
			else
			{
				if (tree->rightChild != NULL)
				{
					stackPush(&stack,tree->rightChild);
				}
			    if(tree->leftChild != NULL)
				{
					stackPush(&stack,tree->leftChild);
				}
			}
		}
	}
}

//层序
//利用队列
void levelOrderTraverse(Tree tree){
	if (tree != NULL)
	{
		LinkQueue queue;
		queueInit(&queue);
		enqueue(&queue,tree);
		while (dequeue(&queue,&tree) && tree)
		{
			printf("%d\t",tree->data);
			if (tree->leftChild != NULL)
			{
				enqueue(&queue,tree->leftChild);
			}
			if (tree->rightChild != NULL)
			{
				enqueue(&queue,tree->rightChild);
			}
		}
		queueDestory(&queue);
	}
}


int _tmain(int argc, _TCHAR* argv[])
{
	Tree tree;
	printf("---------------创建树（先序,0代表子树为空）-----------------\n");
	treeCreate(&tree);
	printf("------------先序递归遍历----------------\n");
	preOrderTraverse(tree);
	printf("------------先序非递归遍历1----------------\n");
	preOrderTraverse1(tree);
	printf("------------先序非递归遍历2----------------\n");
	preOrderTraverse2(tree);
	printf("------------先序非递归遍历3----------------\n");
	preOrderTraverse3(tree);
	printf("\n------------中序递归遍历----------------\n");
	inOrderTraverse(tree);
	printf("\n------------中序非递归遍历1----------------\n");
	inOrderTraverse1(tree);
	printf("\n------------中序非递归遍历2----------------\n");
	inOrderTraverse2(tree);
	printf("\n------------后序递归遍历----------------\n");
	postOrderTraverse(tree);
	printf("\n------------后序非递归遍历1----------------\n");
	postOrderTraverse1(tree);
	printf("\n------------层序遍历----------------\n");
	levelOrderTraverse(tree);
	//及时释放内存是个好习惯..
	treeDestory(&tree);
	return 0;
}

运行截图：

技术分享

看数据结构写代码(24) 二叉链表的递归遍历和非递归遍历算法总结

原文：http://blog.csdn.net/fuming0210sc/article/details/44587009

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)

看数据结构写代码(24) 二叉链表的递归遍历 和 非递归遍历 算法 总结

看数据结构写代码(24) 二叉链表的递归遍历和非递归遍历算法总结