遍历是树结构算法中的重要部分，前面发了有关递归遍历的内容，要知道：递归就是函数调用函数本身，运行起来就是函数嵌套函数，层层嵌套，所以函数调用、参数堆栈都是不小的开销，但是程序简单。然而，非递归即不断地对参数入栈、出栈，省去了函数层层展开、层层调用的开销。虽然参数出入栈次数多了，但是一般都开辟固定的足够大的内存来一次性开辟、重复使用。
一、 先序遍历（非递归）
遍历步骤
先序遍历的最终访问次序是：根 - 左 - 右 ，具体步骤如下：
1. 设有一棵如下结构的树，并申请一个栈stack，用于存放树结点；
image.png
-
将根节点'1'（如果有的话）入栈；
image.png
-
以下操作为一个循环，注：入栈时 先右后左
while(stack不为空){ 从栈中弹出一个栈顶元素root； 访问该结点root；(本例中将此添加到res数组中) if (root结点有右儿子) 将右儿子结点入栈； if (root结点有左儿子) 将左儿子结点入栈； }
image.png
image.png
image.png
image.png
image.png
image.png
stack栈为空，循环结束，先序遍历完毕！
直接上代码
/**
* 非递归先序遍历，根左右（1，2,4,5,3,6,7）
*
*/
public void preTraversal(TreeNode node) {
if (node == null) {
return;
}
List<TreeNode> preOrderList = new ArrayList<>();
Stack<TreeNode> stack = new Stack();
stack.push(node);
while (!stack.isEmpty()) {
TreeNode treeNode = stack.pop();
preOrderList.add(treeNode);
if (treeNode.right != null) {
stack.push(treeNode.right);
}
if (treeNode.left != null) {
stack.push(treeNode.left);
}
}
for (TreeNode treeNode : preOrderList) {
Log.i(TAG, "preTraversal==>treeNode.value="+treeNode.value);
}
}
二、 中序遍历（非递归）
遍历步骤
中序遍历的最终访问次序是：左 - 根 - 右 ，具体步骤如下：
-
设有一棵如下结构的树，并申请一个栈stack，用于存放树结点；
-
以下操作为一个循环，
while(stack不为空 ){ if (当前结点head不为空) ： head结点入栈； head = head.left； else： head = 栈顶出栈； 访问该结点head；(本例中将此添加到res数组中) head = head.right； }
image.png
image.png
image.png
image.png
image.png
stack1栈为空，循环结束，中序遍历完毕！
直接上代码
/**
* 非递归中序遍历，左跟右（4,2，5,1，6,3,7）
* @param node
*/
public void middleTraversal(TreeNode node) {
if (node == null) {
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
while (!stack.isEmpty() || node != null) {
if (node != null) {
stack.push(node);
node = node.left;
} else {
node = stack.pop();
Log.i(TAG, "middleTraversal==>node.value="+node.value);
node = node.right;
}
}
}
三、 后序遍历（非递归）
遍历步骤
后序遍历的最终访问次序是：左 - 右 - 根 ，具体步骤如下：
1. 设有一棵如下结构的树，并申请两个栈s1用于临时存放树结点、s2_res用于存放最终结点序列；
2. 将根节点'1'（如果有的话）入栈；
image.png
-
以下操作为一个循环，注：s1入栈时 先左后右
while(stack不为空) { 从栈中弹出一个栈顶元素root； 访问该结点root；(本例中将此压入到s2_res栈中) if (root结点有左儿子) 将左儿子结点入栈； if (root结点有右儿子) 将右儿子结点入栈； }
image.png
image.png
image.png
image.png
image.png
最后将s2所有结点出栈：4 ，5 ，2 ，6 ，7 ，3 ，1 ; 即为后序遍历序列。
直接上代码
/**
* 非递归后序遍历：左右根（4,5,2，6,7,3,1）
* @param node
*/
public void postTraversal(TreeNode node) {
if (node == null) {
return;
}
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
s1.push(node);
while (!s1.isEmpty()) {
node = s1.pop();
s2.push(node);
if (node.left != null) {
s1.push(node.left);
}
if (node.right != null) {
s1.push(node.right);
}
}
while (!s2.isEmpty()) {
TreeNode node1 = s2.pop();
if (node1 != null) {
Log.i(TAG, "postTraversal==>"+node1.value);
}
}
}
————————————————
版权声明：本文为CSDN博主「尘封的CPU」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/kndjg/article/details/126290142
网友评论