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

hkylliu · 2018-4-30 01:48:43

数据结构中的二叉树中的递归理解如下：
具体实现代码
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三个元素节点
总结聽
递归也没有那么可怕，该执行的代码还是会执行，不过顺序可能和我们平常的思维不一致。它会不断的调用自身直到一个停止条件的满足，然后再回溯会第一个节点。

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

1 个回复