Java实现树结构数据的递归与非递归遍历

coding

树结构的递归与非递归的遍历

递归在很多情况下我们都会使用,比如著名的汉诺塔问题、二分查找等,有时候我们遍历一棵树形数据结构的数据也会需要用到递归,但并不是绝对。原因是:以递归遍历一棵树型结构的数据为例,递归会不断的调用当前方法,以深度遍历方式沿着一条支路走到底,然后再回来执行下一条支路。这种情况下在调用当前方法之后,编译器将这个方法的所有参数和返回地址压入栈中,在这种情况下当前线程若又去调用了一遍当前这个方法,而当这个支路又足够深,那么积攒起来的栈中内容就会越来越多,直到发生内存溢出。

因此在树形数据结构足够深的时候,我们需要用另一种方法来遍历这些数据,这种方法是通过宽度遍历,从树的顶层开始遍历,遍历完这一层后,遍历下一层,当下一层都遍历到后再遍历下一层,依次继续向下遍历,这种方式可以用while循环来实现。

树形结构的数据的递归遍历的Java伪代码:

// 深度遍历代码

TreeNode parent; // 要遍历的顶层节点

pubic void traverse(TreeNode parent) {

List<TreeNode> childs = getChilds(parent); // parent的所有直接子节点

if (childs != null) {

for (child : childs) {

// ------------

// 获取child内容,或其他处理

// ------------

traverse(child);

}

}

}

private List<TreeNode> getChilds(TreeNode parent) {

// 给定父节点获取直接子节点

}

以下是树形结构的数据的非递归遍历的Java伪代码:

//宽度遍历代码

TreeNode parent; // 要遍历的顶层节点

List<TreeNode> childs = getChilds(parent); // parent的所有直接子节点

while (childs != null) {

List<TreeNode> tempChilds;

for (child : childs) { // 遍历子节点

// ------------

// 获取child内容,或其他处理

// ------------

if (getChilds(child) != null) {

tempChilds.add(child);

}

}

childs = tempChilds;

}

private List<TreeNode> getChilds(TreeNode parent) {

// 给定父节点获取直接子节点

}


以上内容仅供参考,如有疑问或错误,还望提出,大家共同进步。


以上是 Java实现树结构数据的递归与非递归遍历 的全部内容, 来源链接: utcz.com/z/510240.html

回到顶部