数据结构中的二叉树中的递归怎么理解?
发布网友
发布时间：2022-04-23 10:01
共2个回答
热心网友
时间：2022-04-22 13:40
数据结构中的二叉树中的递归理解如下：
具体实现代码
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三个元素节点
总结
递归也没有那么可怕，该执行的代码还是会执行，不过顺序可能和我们平常的思维不一致。它会不断的调用自身直到一个停止条件的满足，然后再回溯会第一个节点。
热心网友
时间：2022-04-22 14:58
//递归方法实现创建
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;
}
这是个按条件先序遍历的顺序输入的二叉树，你必须理解的是这些代码中的递归有一个隐含的条件就是利用栈来进行存储，有一个压栈和出栈的过程，栈起了一个保护现场的作用，左孩子是优先的，一直到这个结点为空，才进行弹栈将这个结点的父亲结点，并且进入这个父亲结点的右孩子，对这个过程重复。
有什么问题可以继续找我，数据结构我学的还可以的
