数据结构中的二叉树中的递归怎么理解?

 我来答
liuranghuan123
2018-01-06 · 超过14用户采纳过TA的回答
知道答主
回答量:46
采纳率:0%
帮助的人:55.8万
展开全部
//递归方法实现创建
status createbitree(bitree *t)
{
int ch=0;
cin>>ch;
if(ch==0)(*t)=NULL;
else
{
(*t)=(bitree)malloc(sizeof(binode));
(*t)->data=ch;
createbitree(&(*t)->lchild);
createbitree(&(*t)->rchild);
}
return OK;
}
这是个按条件先序遍历的顺序输入的二叉树,你必须理解的是这些代码中的递归有一个隐含的条件就是利用栈来进行存储,有一个压栈和出栈的过程,栈起了一个保护现场的作用,左孩子是优先的,一直到这个结点为空,才进行弹栈将这个结点的父亲结点,并且进入这个父亲结点的右孩子,对这个过程重复。
有什么问题可以继续找我,数据结构我学的还可以的
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
光点科技
2023-08-15 广告
通常情况下,我们会按照结构模型把系统产生的数据分为三种类型:结构化数据、半结构化数据和非结构化数据。结构化数据,即行数据,是存储在数据库里,可以用二维表结构来逻辑表达实现的数据。最常见的就是数字数据和文本数据,它们可以某种标准格式存在于文件... 点击进入详情页
本回答由光点科技提供
hkylliu
2018-05-28 · TA获得超过5855个赞
知道小有建树答主
回答量:63
采纳率:0%
帮助的人:4.1万
展开全部

数据结构中的二叉树中的递归理解如下:

具体实现代码

1 function preorder(node){

2       if(!!node){//转换为布尔值

3            divlist.push(node);

4           preorder(node.firstElementChild);

5           preorder(node.lastElementChild);    

6        }

7    }

对代码的几点说明:

divlist为一个数组,是一个全局变量,存储最终遍历结果。可能有的同学不熟悉JavaScript,node.firstElementChild与node.lastElementChild分别指父节点的第一个元素节点和最后一个元素节点,即对应父节点的左孩子和右孩子。

二叉树是以DOM树的形式模拟

所谓递归可以分为两部分来理解:“递”和“归”。 

“递”指按照代码执行顺序执行,这个和我们正常的思维一致不难理解。但有一点需要注意的是,在“递”的同时会把节点按照访问的顺序逐次压入到一个堆栈中。 

“归”是指“递”进行到尽头时,开始根据“递”的过程中形成的堆栈进行出栈,最终得到结果。

对于二叉树的先序遍历,可以看出包含了两个对自己的调用,及包含两个遍历。 

我们首先传进去的node是1,根据程序执行过程,我们可以知道在执行到一个阶段的尽头时,将会形成这样一个堆栈 

由于左子树已经到了尽头,所以第一个遍历暂告一段落。按照代码执行的顺序,接下来需要执行preorder(node.lastElementChild);也就是右子树的遍历,因为4依然没有右孩子,所以按照出栈的顺序依次遍历2和1的右子树。为了说明简单,再次贴一下代码

1 function preorder(node){

2        if(!!node){//转换为布尔值

3          divlist.push(node);

4            preorder(node.firstElementChild);

5           preorder(node.lastElementChild);    

6      }

7   }

再来具体分析一下遍历2的右孩子时的过程。 

当把2的节点传给preorder函数时,只执行了preorder(node.firstElementChild);,preorder(node.lastElementChild);还没有执行,按照程序执行顺序此时需要执行。 

具体的执行步骤如下: 

此时堆栈内又依次被压入了5,6,7三个元素节点

总结 

递归也没有那么可怕,该执行的代码还是会执行,不过顺序可能和我们平常的思维不一致。它会不断的调用自身直到一个停止条件的满足,然后再回溯会第一个节点。

已赞过 已踩过<
你对这个回答的评价是?
评论 收起
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式