二叉树的遍历的递归与非递归算法

一.二叉树的遍历：

按照一定规律对二叉树的每个结点进行访问且仅访问一次；

这里的访问：可以是计算二叉树中的结点数据，打印该结点的信息，也可以是对结点进行的任何其它操作！

为什么需要遍历二叉树？

从过遍历可以得到访问结点的顺序序列，遍历操作就是将二叉树的结点按一定的规律线性化，目的就在于将非线性化的结构变成线性化的访问序列。

二.3种遍历方式：

1.先序遍历：（DLR）根——左——右

若二叉树非空：

首先访问根结点，其次按先序遍历左子树，最后按先序遍历右子树

下面我们给出一个例子：

如图所示的二叉树：根据先序遍历的特点，我们先访问根结点：A，再访问其左子树,而其左子树又可以看成一个二叉树，我们依然用先序遍历A的左子树，此时B为这个左子树的根结点，于是我们访问B，A的左子树此时还没有访问完成，因此我们继续访问，此时B已经访问过，那么我们接着访问B的左孩子，而B没有左孩子，所以我们接着访问B的右孩子，D作为右孩子的根结点，直接访问，对于D来说，接着访问D的左孩子F，最后访问D的右孩子G；此时A的左孩子遍历完成；

那么我们接着遍历A的右孩子，C作为右子树的根结点直接访问，C没有左孩子，接着访问C的右孩子，E作为C的右孩子的根节点，直接访问，E没有左孩子，访问E的右孩子H；

综上所述：上述二叉树的先序遍历的顺序就为：A-B-D-F-G-C-E-H

2.中序遍历：LDR（左——根——右）

我们仍然以上述二叉树为例来看：

根据 中序遍历的特点：首先按中序遍历左子树：此时首先访问A的左子树，我们将二叉树的左子树单独拿出来看：如图：B作为左子树的根节点，我们要找此时这个二叉树的左孩子，而此时这个二叉树没有左孩子，因此我们直接访问这个二叉树的根节点B，之后访问这个二叉树的右孩子：同样把这个二叉树的右孩子单独拿出来：此时我们依然以中序遍历：首先访问这个二叉树的左孩子，即F，接着访问这个二叉树的根节点D,最后访问这个二叉树的右孩子G；

那么此时整个二叉树的左孩子访问完成，继续访问整个二叉树的根节点A；

接着访问整个二叉树的右孩子：

此时C作为整个二叉树的右孩子的根节点，我们首先访问这个二叉树的左孩子，显然这个二叉树没有左孩子，因此我们先访问根结点C；

此时：E作为二叉树的根结点，此时该二叉树没有左孩子，直接访问根节点E，最后访问右孩子H

综上所述：按照中序遍历访问上述二叉树的顺序：B-F-D-G-A-C-E-H

3.后序遍历：LRD（左——右——根）

仍然以上述二叉树作为例子来看：首先访问整个二叉树的左子树：

按照后序遍历访问：B作为根结点，访问这个二叉树的左子树，左子树为空，接着访问这个二叉树的右孩子：

此时D作为根结点，先访问其左孩子F，接着访问其右孩子G，最后访问根节点D；

那么经过上述过程，该二叉树的右孩子访问完成，接着访问根节点B，此时整个二叉树的左子树遍历完成；

那么我们接着访问整个二叉树的右子树：

C作为此时这个二叉树的根结点，先访问这个二叉树的左子树，但是左子树为空，接着访问右孩子：

E为此时这个二叉树的根结点，此时这个二叉树没有左子树，那么我们访问其右孩子H，接着访问根节点E；

此时这个二叉树的右孩子也访问完成，所以我们访问根结点C；

整个二叉树的左右子树均已遍历完成，于是我们最后访问根结点A；

综上所述：按照后续遍历访问上述二叉树的顺序为：F-G-D-B-H-E-C-A

总结：

看了以上三种方式遍历二叉树的例子，应该就能明白三种遍历方式的本质与区别，其实我们可以看出，无论以何种方式，我们只要把握好访问的顺序，并且将每一个根结点下的子树都看成一个新树，再按照某种遍历方式访问这个这个新树即可！

例子：中缀表达式转后缀表达式；（前缀表达式：波兰表达式；后缀表达式：逆波兰表达式）

前缀表达式：-+a*bc/de（也就是以先序遍历访问上述二叉树的顺序）

中缀表达式：a+b*c-d/e（也就是以中序遍历访问上述二叉树的顺序）

后缀表达式：abc*+de/-（也就是以后序遍历访问上述二叉树的顺序）

我们其实可以看出：中缀表达式是我们在数学计算中的习惯顺序，但是其实在计算机种，后缀表达式才是计算机能理解的表达式；

（关于中缀表达式转后缀表达式的例题：

有兴趣的读者可以自行尝试：下面给出利用栈来解决逆波兰表达式的代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MaxSize 1010

typedef struct
{
    char* ch;
    int top;

}CharStack;

typedef struct
{
    double* num;
    int top;
}NumStack;

CharStack S;
NumStack St;

void InitCharStack(CharStack& S);
void InitNumStack(NumStack& St);
void PushCharStack(CharStack& S, char c);
void PushNumStack(NumStack& St, double num);
char PopCharStack(CharStack& S);
double PopNumStack(NumStack& St);
char GetStackTop(CharStack& S);
bool PriorJudge(char c1, char c2);//priority优先级 judge判断
char* InfixToSuffex(char* a, char* b);//infix前缀 suffex后缀 
double CaculatValue(char* b, NumStack& St);

int main()
{
    InitCharStack(S);

    char a[MaxSize] = { 0 };
    char b[MaxSize] = { 0 };
    InfixToSuffex(a, b);

    double ans = CaculatValue(b, St);

    printf("%.2f\n", ans);

    return 0;
}

void InitCharStack(CharStack& S)
{
    S.ch = (char*)malloc(MaxSize * sizeof(char));

    if (S.ch == NULL)
    {
        printf("内存分配失败！");
        return;
    }
    S.top = -1;

    return;
}

void PushCharStack(CharStack& S, char c)
{
    if (S.top == MaxSize)
    {
        printf("栈已满");
        return;
    }
    S.top++;
    *++S.ch = c;

    return;
}

char PopCharStack(CharStack& S)
{
    if (S.top == -1)
    {
        printf("栈为空");;
        exit(1);
    }
    S.top--;
    char c = *S.ch--;

    return c;
}

char GetStackTop(CharStack& S)
{
    char c = *S.ch;

    return c;
}

bool PriorJudge(char c1, char c2)//priority优先级 judge判断 
{
    if (c1 == '*' || c1 == '/')
        if (c2 == '+' || c2 == '-' || c2 == '(')
            return true;
    if (c1 == '+' || c1 == '-')
        if (c2 == '(') return true;

    return false;
}

char* InfixToSuffex(char* a, char* b)//infix中缀 suffex后缀 
{
    fgets(a, MaxSize - 1, stdin);//从输入流中读取字符串 

    int t = strlen(a);

    int k = 0;
    //    12.25 + 25.02 / 2.36 + 8 * 2.01 =
    for (int i = 0; i < t; ++i)
    {
        if (a[i] >= '0' && a[i] <= '9')
        {
            b[k++] = a[i];
            if (a[i + 1] == '.') b[k++] = '.', ++i;
            else if (a[i + 1] < '0' || a[i + 1] > '9')
                b[k++] = '#';
        }

        else if (a[i] == ' ' || a[i] == '=') continue;

        else
        {
            if (S.top == -1 || a[i] == '(')
                PushCharStack(S, a[i]);

            else if (a[i] == ')')
            {
                while (S.top != -1 && GetStackTop(S) != '(')
                    b[k++] = PopCharStack(S);

                if (S.top != -1) PopCharStack(S);

            }

            else
            {
                while (S.top != -1 && !PriorJudge(a[i], GetStackTop(S)))
                    b[k++] = PopCharStack(S);

                PushCharStack(S, a[i]);
            }
        }

    }

    b[k] = '\0';//这句话加不加应该无所谓，因为该字符数组已初始化为0 

    return b;
}

void InitNumStack(NumStack& St)
{
    St.num = (double*)malloc(MaxSize * sizeof(double));
    St.top = -1;

    return;
}

void PushNumStack(NumStack& St, double n)
{
    if (St.top == MaxSize)
    {
        printf("栈已满");
        return;
    }

    St.top++;

    *++St.num = n;

    return;
}

double PopNumStack(NumStack& St)
{
    if (St.top == -1)
    {
        printf("栈为空");
        exit(1);
    }
    St.top--;
    double num = *St.num--;

    return num;
}

double CaculatValue(char* b, NumStack& St)
{
    InitNumStack(St);
    int t = strlen(b);
    char str[MaxSize] = { 0 };

    for (int i = 0, k = 0; i < t; ++i)
    {
        if (b[i] == '.' || (b[i] >= '0' && b[i] <= '9'))
        {
            str[k++] = b[i];
            if (b[i + 1] == '#')
            {
                str[k] = '\0';
                double num = atof(str);
                PushNumStack(St, num);
                k = 0;
            }
        }

        else
        {
            if (b[i] == '#') continue;

            double n = PopNumStack(St);
            double m = PopNumStack(St);

            if (b[i] == '+') PushNumStack(St, m + n);

            else if (b[i] == '-') PushNumStack(St, m - n);

            else if (b[i] == '*') PushNumStack(St, m * n);

            else PushNumStack(St, m / n);
        }

    }

    return PopNumStack(St);
}

三.二叉树的遍历算法：

在理解了上述所说的遍历过程之后，我们来看二叉树的遍历算法，可以分为递归算法与非递归算法

1.递归算法：

（1）先序遍历的递归算法

首先定义二叉树的链表结点结构：

#define DataType int 
//首先定义二叉树：

typedef struct Node
{
	DataType data;
	struct Node* LChild;
	struct Node* RChild;
}BiTNode,*BiTree;

//先序遍历二叉树的递归算法

void PreOrder(BiTree root)
{
	//root为指向二叉树或者其某一子树的根结点的指针

	if (root != NULL)
	{
		printf("%d", root->data);//访问根结点；//文章开头就已经说过，二叉树的遍历可以是多种形式
		PreOrder(root->LChild);//按照先序遍历访问左子树
		PreOrder(root->RChild);//按照先序遍历访问右子树
	}
}

（2）中序遍历递归算法

void InOrder(BiTree root)
{
	if (root != NULL)
	{
		InOrder(root->LChild);//首先按中序遍历左子树
		printf("%d", root->data);//访问根结点
		InOrder(root->RChild);//中序遍历右子树
	}
}

（3）后续遍历递归算法

void PostOrder(BiTree root)
{
	if (root != NULL)
	{
		PostOrder(root->LChild);//首先按照后序遍历左子树
		PostOrder(root->RChild);//按照后序遍历右子树
		printf("%d", root->data);//访问根结点
	}
}

递归：把复杂问题变成相同性质的子问题，因此递归算法表面上看上去很简单，其实整个的逻辑十分复杂；

比如：当访问到的结点不为空时，我们先访问其左子树，再访问其右子树；但是当根结点为空时，就不需要参与递归运算，那此时访问的为空，应该返回什么值？在这里程序就会自动设置堆栈来保存本层地址（涉及到堆栈的知识：当递归函数调用时，应按照“后调用先返回”（因为大问题一直在分解成小问题，当分解为基问题时，才会返回一个值，因此最后调用的先返回）的原则处理调用过程，因此函数之间的信息传递和控制转移必须通过栈来实现（符合栈的特点：last in first out）

整个递归过程其实与上述所描述的遍历算法类似，读者可尝试分析；

递归算法的时间复杂度分析：

假设二叉树有n个结点，对每个结点都要进行一次入栈和出栈的操作，即入栈和出栈均执行了n此，对结点的访问也是n次，这些二叉树的递归遍历算法的时间复杂度就为O(n)；

A.递归遍历算法的应用：

a.输出二叉树中的结点：

//输出二叉树的结点

void PreOrder(BiTree root)
{
	if (root != NULL)
	{
		printf("%d",root->data);
		PreOrder(root->LChild);
		PreOrder(root->RChild);
	}
}

输出二叉树的结点并没有次序要求，因此三种次序均可以使用

b.输出二叉树中的叶子结点：

相比于上述应用，叶子节点：无后继，因此有条件限制

//输出叶子结点数

void PreOrder(BiTree root)
{
	if (root != NULL)
	{
		if (root->LChild == NULL && root->RChild == NULL)
		{
			printf("%d", root->data);
		}
		PreOrder(root->LChild);
		PreOrder(root->RChild);
	}
}

c.统计叶子结点数目

（1）一般的后序遍历

void leaf(BiTree root)
{
	if (root != NULL)
	{
		leaf(root->LChild);
		leaf(root->RChild);
		if (root->LChild == NULL && root->RChild == NULL)
		{
			leafCount++;//保存叶子结点数目的全局变量，调用之前的初始化为0；别忘了在main函数中先调用初始化函数
		}
	}
}

在这里：根据文章开头所说的，究竟什么才是对根结点进行访问？在这里leafCount++就可以是，因此在这里，我们使用的是后续遍历；

（2）分治算法：

如果二叉树为空树，返回0，如果二叉树只有一个根结点，返回1，否则返回左子树和右子树的叶子节点数之和（也是递归算法）

int leaf1(BiTree root)
{
	int leafCount;
	if (root == NULL)
	{
		leafCount = 0;
	}
	else if (root->LChild == NULL && root->RChild == NULL)
	{
		leafCount = 1;
	}
	else
	{
		leafCount = leaf1(root->LChild) + leaf1(root->RChild);
	}
	return leafCount;
}

在这里也是后序遍历：根据表达式：C=A+B，在C语言中是先计算A，再计算B，最后计算A+B，赋值给C，因此依然是先遍历左子树，再遍历右子树，最后访问根；

（关于求二叉树的高度：读者可尝试）

int PostTreeDepth(BiTree bt)
{
	int hl, hr,max;
	if (bt != NULL)
	{
		hl=PostTreeDepth(bt->LChild);
		hr=PostTreeDepth(bt->RChild);
		max = hl > hr ? hl : hr;
		return(max + 1);//还要加上第一个根结点
	}
	else
	{
		return 0;
	}
}

d:按横向树形显示二叉树：

其实就是按照“逆中序”的方式来遍历整个二叉树（所谓的逆中序，就是先访问右子树，再访问根，最后访问右子树，与正常的中序遍历相反）

（在这里只给出思路，具体代码实现，读者可以自行尝试，有问题欢迎在评论区交流！）

2.非递归算法：

基于栈的递归消除：

关于递归的消除：我们可以将这些递归问题，转化为重复的循环问题，即用循环代替递归，但是在工作量大，复杂的情况下，就不适宜采用循环，因此我们可以采用工作栈的方式来消除递归。

（1）中序遍历二叉树的非递归算法

下面我们以中序遍历二叉树的非递归算法为例来看：

整个过程都依据在上述框图下进行：

 （以此二叉树为例）

首先：A：A不为空——进栈；p=A的LChild，到B；B不为空——进栈；p指向B的左子树，到C；C不为空，C进栈；p指向C的左子树；C的左子树为空，判断栈是否为空，栈此时非空，C出栈，p指向C的右子树，D，C的右子树不为空，D入栈，p指向D的左子树，p为空，那么判断栈是否为空，栈非空，D退栈，p指向D的右子树，D的右子树为空，栈非空，退栈到B，p指向B的右子树，为E，不是空，那么E进栈，E的左子树为空，栈非空，那么E出栈，p指向E的右子树，E的右子树为空，栈非空，A出栈，A的右子树为F，不为空F进栈，p指向F的左子树，F的左子树为G不为空，G进栈，p指向G的左子树，G的左子树为空，栈非空，G出栈，p指向G的右子树，G的右子树为空，栈非空，F出栈，p指向F的右子树，F的右子树为空，栈为空，那么遍历结束；（出栈的同时访问根结点，在这里我省略了，注意一下！！！）（可能有点长，可以耐心看一下）

此时：我们需要自己设置栈来保存结点的信息；为什么能够实现中序？基于栈的一些特点，我们可以直到，先进栈的后出栈，因此左子树先进栈后，一直保存在栈中，而到退栈的地步时，说明左子树一定为空，所以此时来访问右子树；并且在结点判断为非空时，其一直保存在栈中，并没有对其进行访问，所以一定是先访问左子树的，直到判断左子树为空时，我们才将左子树对应的根结点出栈，先访问根结点，再去访问右子树。

在这里其实进栈的一直都是根结点！

上述便是中序遍历的非递归算法；（极大地利用了栈的特点！！！）

（先序遍历的非递归算法与中序类似，与中序遍历的不同之处在于，中序保存根结点，而先序遍历我们可以保存右孩子的地址，这样比较简单，我们不再赘述；）

（2）后序遍历二叉树的非递归算法

我们首先说明一下：中序遍历的非递归与后序遍历的非递归算法的异同：

（1）相同点：根结点进栈

（2）而后序遍历在p=NULL时，不能直接出栈访问根结点，因为此时我们不能判断右孩子是否已经访问；

那我们该在什么时候访问？

（1）根的右子树为空；（2）根有右孩子，但是根的右子树已经访问过了；

对于第二中情况，我们如何判断根的右子树是否已经访问？那我们就可以多设置一个指针，记忆之前已经访问的结点；

(以此二叉树为例）

我们初始时设置p,q两个指针，p用于移动，q用于记忆已访问过的结点，q初始值设置为NULL

首先：根结点A不为空，入栈，p指向A的左子树：

此时p为B,B不为空，那么B入栈，p指向B的左子树，那么p为空，栈非空，并且此时B的右子树不为空，并且q=NULL,并不等于B的右子树，说明B的右子树还没有访问过，那么我们不访问根结点，p指向B的右子树；

p此时指向D，D的左子树不为空D入栈，p指向D的左子树，此时p指向E，E不为空，E入栈，p指向E的左子树，p此时为空，栈非空，读取栈顶元素E，并且q指向E的右子树，E的右子树为空，那么满足可以访问根结点的条件，因此我们访问E，E出栈，此时设置q为E，上面已经判断E的右子树为空，p为空，栈非空，那么读取栈顶元素D，此时D的右子树不为空，并且q也不等于D的右子树，那么说明D的右子树没有访问过，此时p=D的右子树F，p的右子树不为空，F入栈，p指向F的左子树，F的左子树为空，栈非空，读取栈顶元素F，p指向F的右子树，且F的右子树为空，那么我们访问结点F，F出栈，并且令q=F，并且由于p为空，栈非空，读取栈顶元素D，此时q=D的右子树F，满足访问条件，访问D，并且令q=D，D出栈；（下面分析：出栈之后读取栈顶元素）读取栈顶元素，B，此时q=B的右子树，满足访问的条件，我们访问B，并将q=B，B出栈（分析：访问完就出栈），读取栈顶元素，A，此时A的右子树不为空，并且q不等于A的右子树，不满足访问根的条件，因此我们访问A的右子树。

此时p=C，不为空，C入栈，p指向C的左子树，C的左子树为空，p=NULL，栈非空，且C的右子树不为空，q也不等于C的右子树G，那么不满足访问的条件，令p=C的右子树G，G不为空，G入栈，p=G的左子树，G的左子树为空，栈非空，G的右子树为空，满足访问的条件，因此访问G，令q=G，G出栈；再读取栈顶元素C，此时q=C的右子树G，满足访问的条件，访问C，并且令q=C，C出栈；读取栈顶元素A，此时q=A的右子树，那么满足访问的条件，访问A，令q=A，A出栈，此时栈为空且q=A，说明已经访问到最后一个结点处。遍历结束！

经过以上过程的分析：我们其实可以发现，每次在有元素出栈后，我们就开始读取栈顶元素；而在我们访问完成结点后，就进行出栈操作！

综上所述：就是后续遍历二叉树的非递归算法，与中序遍历不同的是：

加了一个起到记忆的作用的指针q，用于记忆已经访问过的结点；

加了一个读取栈顶元素的操作：因为不能立即访问根结点，出栈，所以要先确定访问之后，再出栈，所以我们先读取，不出栈即可。

除了上述区别之外，中序遍历与后序遍历大同小异！（后续遍历更为复杂！！！）读者可以跟着上述内容，自己走一遍这个二叉树的遍历的过程，就能够理解上述思想！

以上就是我对于二叉树的遍历的递归与非递归算法的一些个人总结与理解，欢迎读者有更好的方法再评论区交流！文章来源地址https://www.toymoban.com/news/detail-852494.html

到了这里，关于二叉树的遍历的递归与非递归算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！