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

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

具体实现代码

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三个元素节点

总结

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

靠，缩进全被百度搞乱了，自己排版

#include <iostream>

using namespace std

//二叉树节点

struct BiTreeNode{

int data

BiTreeNode *left

BiTreeNode *right

}

//写一个类，方便二叉树的建立和删除

class BiTree{

private:

void deleteAllNode(BiTreeNode *root)

public:

BiTreeNode *root

BiTree()

~BiTree()

void CreateTree()

void deleteLeaves(BiTreeNode *root)

bool DepthOfTheNode(BiTreeNode *currentNode,BiTreeNode *p, int depthOfFather)

void FindMaxValue(BiTreeNode *currentNode, int *maxValue)

void ExchangeLeftAndRight(BiTreeNode *currentNode)

void OutputValueAndDepthByQIANXU(BiTreeNode *currentNode, int depthOfFather)//不好意思，用了拼音

}

BiTree::BiTree()

{

root = NULL

}

BiTree::~BiTree()

{

deleteAllNode(root)

}

void BiTree::deleteAllNode(BiTreeNode *root)

{

if (root == NULL) return

deleteAllNode(root->left)

deleteAllNode(root->right)

cout <<root->data <<' '//用来查看当前节点是不是被删除。

delete root

}

//手动建立一个二叉树用于测试

// 1

// / \

// 2 3

// \ /

//4 5

void BiTree::CreateTree()

{

if (root) return

root = new BiTreeNode

root->data = 1

root->left = new BiTreeNode

root->left->data = 2

root->right = new BiTreeNode

root->right->data = 3

BiTreeNode *p

p = root->left

p->left = NULL

p->right = new BiTreeNode

p->right->data = 4

p->right->left = p->right->right = NULL

p= root->right

p->left = new BiTreeNode

p->left->data = 5

p->left->left = p->left->right = NULL

p->right = NULL

}

//用递归算法删除叶子

void BiTree::deleteLeaves(BiTreeNode *root)

{

if (root == NULL) return

if (!root->left &&!root->right) return//表示是根节点(或者出错，跑到叶子节点了，这种情况应该不会)，不删除

if (root->left) //当前节点有左子树

{

if (root->left->left || root->left->right) //左子树不是叶子

deleteLeaves(root->left)

else //当前节点的左子节点是叶子

{

delete root->left

root->left = NULL

}

}

if (root->right)

{

if (root->right->left || root->right->right)

deleteLeaves(root->right)

else //当前节点的右子节点是叶子

{

delete root->right

root->right = NULL

}

}

}

int depth = 0//一个用来存储深度的全局变量，虽然在实际编程中这样用不好

//但一切为了方便。

//节点p的深度,递归法

bool BiTree::DepthOfTheNode(BiTreeNode *currentNode,BiTreeNode *p, int depthOfFather)

{

if (currentNode == NULL) return false

if (currentNode == p) //当前节点为要找的节点

{

depth = depthOfFather + 1

return true

}

if (DepthOfTheNode(currentNode->left, p, depthOfFather+1)) //找当前节点的左子树

return true

else

return DepthOfTheNode(currentNode->right, p, depthOfFather+1)

}

//用递归找最大值，最大值存储在maxValue所指的内存 ,这里使用前序遍历

void BiTree::FindMaxValue(BiTreeNode *currentNode, int *maxValue)

{

if (currentNode == NULL) return

*maxValue = *maxValue >currentNode->data ? *maxValue : currentNode->data

FindMaxValue(currentNode->left, maxValue)//遍历左子树

FindMaxValue(currentNode->right, maxValue)

}

//交换左右，用前序遍历

void BiTree::ExchangeLeftAndRight(BiTreeNode *currentNode)

{

if (currentNode == NULL) return

BiTreeNode *temp

temp = currentNode->left

currentNode->left = currentNode->right

currentNode->right = temp

ExchangeLeftAndRight(currentNode->left)

ExchangeLeftAndRight(currentNode->right)

}

//以前序次序输出一棵二叉树所有结点的数据值及结点所在层次

void BiTree::OutputValueAndDepthByQIANXU(BiTreeNode *currentNode, int depthOfFather)

{

if (currentNode == NULL) return

cout <<"节点：" <<currentNode->data

cout <<"\t深度：" <<depthOfFather+1 <<endl

OutputValueAndDepthByQIANXU(currentNode->left, depthOfFather+1)

OutputValueAndDepthByQIANXU(currentNode->right, depthOfFather+1)

}

int main()

{

BiTree bt

bt.CreateTree()

//求p的深度

bt.DepthOfTheNode(bt.root, bt.root->left->right, 0)

cout <<"深度:" <<depth <<endl

//找最大值

int maxValue

bt.FindMaxValue(bt.root, &maxValue)

cout <<"最大值为：" <<maxValue <<endl

//交换左右节点

bt.ExchangeLeftAndRight(bt.root)

//以前序次序输出一棵二叉树所有结点的数据值及结点所在层次

bt.OutputValueAndDepthByQIANXU(bt.root, 0)

//删除叶子节点

bt.deleteLeaves(bt.root)

return 0

}

你数据库设计好的话 应该就可以避开递归的需求

你的树 分级查询的时候做到分级 就可以直接根据你选中的节点的信息查询到你需要的信息了（分级不多的情况下）

要是没那样的话（级别什么的都自定义 随便设置）

递归 就是按照你节点是否有子节点 进行一级级的眼神，就像你选中根节点，对应的他下面的子节点 都用递归的方法 添加到查询条件里 就能查到你要的结果了

递归把对应的节点 都加在成一串字符串 中间用 OR 相连

串成一个字符串 字段名=‘节点1’ or 字段名=‘节点2’or ....

最后sql 语句执行 应该就是你要的结果了

2楼的 where in 更简单点~

---