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

Z时代
2024-01-10
分类：综合

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) {
	// 给定父节点获取直接子节点}