首页 > 搜索 > 递归树的遍历算法,二叉树递归遍历算法分析-入栈及出栈(调用堆栈窗口)

递归树的遍历算法,二叉树递归遍历算法分析-入栈及出栈(调用堆栈窗口)

互联网 2020-10-21 15:27:54
在线算命,八字测算命理

前言:

本文作者意在分析,递归算法在二叉树遍历中的执行过程,主要分析多重递归算法是如何一步步调用自身(保存现场)和调用返回(恢复现场)。

在分析过程中,借用了设置断点,查看堆栈窗口中入栈和出栈情况。并绘制了两种分析图。

下图 1 既是要从键盘输入的二叉树,先序遍历结果为 ABDFCE。@表示 NULL。关于二叉树遍历算法请读者自行学习,本文不做详细解读。运行程序如下。

                                                                                                   图 1. 二叉树遍历图

算法分析:

栈是实现递归时最常用的辅助结构,利用一个栈来记录尚待遍历的结点,以备以后访问。对于先序遍历来说,对二叉树各结点的访问顺序是沿其左链一路访问下来,在访问结点的同时将其入栈,直到左链为空。然后结点出栈,对于每个出栈结点,即表示该结点和其左子树已被访问结束,应该访问该结点的右子树。具体步骤如下:

当前指针指向跟结点;打印当前结点,当前指针指向其左孩子并进栈,重复本步骤,直到左孩子为 NULL;依次退栈,将当前指针指向右孩子;若栈非空或当前指针非 NULL,执行步骤(2),否则结束。

简单来说,遇到一个结点,就访问该结点,并把此结点推入栈中,然后去遍历他的左子树。遍历完它的左子树后,从栈顶弹出这个结点,并按照它的右链接指示的地址再去遍历该结点的右子树结构。

 

// Tree.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"////main.cpp//二叉树递归遍历算法执行过程分析////Created by 刘一丁 on 2019/4/26.//Copyright © 2019年 LGD. All rights reserved.//#include #include typedef char datatype;/*===================================================函数功能:二叉树结构链表定义函数输入:无函数输出:无===================================================*/typedef struct node{datatype data;struct node *lchild, *rchild;}BinTreeNode;/*===================================================函数功能:用先序遍历的方法建立二叉链表函数输入:二叉链表的根节点函数输出:二叉链表根节点。最先入栈的为根节点,所以最后出栈 的也是根节点。键盘输入:输的先序遍历序列,子树为空时输入@===================================================*/BinTreeNode *CreatBTree_DLR(BinTreeNode *root){char ch;scanf("%c", &ch);if(ch == '@' ) root = NULL;else{root = (BinTreeNode*) malloc (sizeof(BinTreeNode));root->data = ch;root->lchild = CreatBTree_DLR(root->lchild);root->rchild = CreatBTree_DLR(root->rchild);}return root;}/*===================================================函数功能:先序遍历递归算法函数输入:树的根节点函数输出:无屏幕输出:树的先序遍历序列===================================================*/void PreOder(BinTreeNode *t){if(t != NULL){putchar(t->data);PreOder(t->lchild);PreOder(t->rchild);}}int main(){BinTreeNode *RPtr = (BinTreeNode*) malloc (sizeof(BinTreeNode));printf("建立树,输入树的先序遍历序列\n");RPtr = CreatBTree_DLR(RPtr);printf("递归先序遍历结果\n");PreOder(RPtr);return 0;}

从根节点开始遍历, 当前指针指向其左孩子,并入栈,直至左孩子为NULL。从图中可以看出,入栈3个结点,分别为A、B、D,D无左孩子,所以不在入栈,开始出栈。

由此可以得出,每次函数调用自身会进行入栈,即每次执行 root->lchild = CreatBTree_DLR(root->lchild);语句会将当前“模块名、参数类型、参数名、参数值、行号、字节偏移量”等信息保存到栈中(保存现场),总共执行三次自身调用,所以栈中有三条信息。

执行第一次恢复现场(出栈/返回操作)后,可以从下图中看到“自动窗口”中存储的是栈顶的信息(存储 D 的相关信息)。

逐语句执行,执行恢复现场后的一条语句,见下图断点下面第一个黄色箭头。由此可以得出,当程序第一次恢复现场后,紧接着会执行其后的语句,即 root->rchild = CreatBTree_DLR(root->rchild);语句,开始查询右子树。

在执行root->rchild = CreatBTree_DLR(root->rchild);语句时,函数会调用自身,所以会保存现场(入栈),即图中行 36 的信息,其中保存的是字符 F。

紧接着会顺序执行,首先遇到root->lchild = CreatBTree_DLR(root->lchild);语句,则执行相应的自调用,查询其左子树,见下图。

因为 F 结点后再无结点,所以会一直出栈,一直到 B 结点,即地址为0x013518f0行 35 。

下图为 F 结点左子树返回(出栈),左子树返回后查询右子树(调用自身,会经历保存现场操作,保存信息为 F结点)。

下图为右子树返回(恢复现场,F 结点),然后会继续出栈(恢复现场)像上级返回,返回到 D结点。

继续向上级返回,返回到 B 结点(左子树返回)。然后开始查找右子树(会进行保存现场操作,保存 B 结点值)。

因为 B无右子树,会继续返回(出栈\恢复现场)直到返回到 A结点(左子树返回),开始寻找右子树。下图可以看到,在查询右子树时,保存的现场信息中除了根节点A的信息外,还存储了其左子树 B的信息。

 

                                                                                                图 2. DLR 递归过程示意图

                                                                                                图 3. DLR 递归过程示意图

                                                                                                图 4. DLR 递归过程示意图

                                                                                              图 5. D到 F 入栈过程

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多