您的位置: 首页  >  IT文章  >  瞥数据结构写代码(24) 二叉链表的递归遍历 和 非递归遍历 算法 总结

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

分类: IT文章 • 2022-06-11 21:01:23
看数据结构写代码(24) 二叉链表的递归遍历 和 非递归遍历 算法 总结

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

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

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

算法思路 有两类：

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) 二叉链表的递归遍历 和 非递归遍历 算法 总结

相关推荐