二叉树前序,中序,后序遍历的非递归实现
程序员文章站
2022-05-16 14:21:15
...
两天前遇到一道二叉树非递归前序遍历的题目,结果没做出来,很受打击,在这里记录一下。
题目:有一个String数组,存储了一棵二叉树,现在请以非递归实现二叉树的前序遍历。数组直接给出:
String[] a={"A","B","J","F","C","#","M"};
解:
首先我们知道String数组是棵二叉树,它在数组中是以层次遍历的形式表示的。由此可知道根节点与它的左孩子和右孩子在数组中的对应索引为2n+1和2n+2(n为根节点在数组中的索引)。非递归的前序遍历可用栈来实现,而栈是先进后出,所以应先压入右节点再压入左节点。
前序遍历:
public static void PreTraverse(String[] a){
Stack<Integer> stack=new Stack<Integer>();
int temp=0;
stack.push(temp);
while(temp<a.length&&!stack.isEmpty()){
temp=stack.pop();
System.out.print(a[temp]);
//判断是否超过数组长度和对应数组值是否为空
if((2*temp+2)<a.length&&a[2*temp+2]!="#"){
stack.push(2*temp+2);
}
if((2*temp+1)<a.length&&a[2*temp+1]!="#"){
stack.push(2*temp+1);
}
}
}
中序遍历(两种方法):
(1)
public static void InOrderTraverse2(String[] a){
Stack<Integer> stack=new Stack<Integer>();
int temp=0;
stack.push(temp);//根指针进栈
while(!stack.isEmpty()){
while(temp<a.length&&a[stack.peek()]!="#"){
stack.push(temp*2+1);//向左走到尽头
temp=temp*2+1;
}
stack.pop();//空指针退栈
if(!stack.isEmpty()){//访问节点,向右一步
temp=stack.pop();
if(temp<a.length)
System.out.print(a[temp]);
stack.push(temp*2+2);
temp=2*temp+2;
}
}
}
(2)
public static void InOrderTraverse(String[] a){
Stack<Integer> stack=new Stack<Integer>();
int temp=0;
//stack.push(temp);
while(temp<a.length||!stack.isEmpty()){
if(temp<a.length&&a[temp]!="#"){//遍历左子树
stack.push(temp);
temp=temp*2+1;
}else {//遍历右子树
temp=stack.pop();
System.out.print(a[temp]);
temp=temp*2+2;
}
}
}
后序遍历:
后序遍历的非递归实现比前序、中序的非递归实现 要复杂。需要一个标识来标记某结点是否第一次位于栈顶(该结点的左子树已经遍历完毕,从左子树返回准备遍历它的右子树)。
对于后序遍历而言,结点的左右子树都遍历完成之后,才访问该结点。某结点会两次位于栈顶,第一次是该结点的左子树都遍历完了,然后 获取 栈顶结点,切换到该结点的右孩子,准备遍历它的右子树,当该结点的右子树也都遍历完后,它就会第二次位于栈顶,此时将栈顶元素出栈。
//二叉树的结构
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
boolean flag=false;//判断是否第一次位于栈顶的标记
public TreeNode(int val) {
this.val = val;
}
}
public void postNonRecurTraverse(TreeNode root){
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode curr,temp;
curr=root;
while(curr!=null||!stack.isEmpty()){
while(curr!=null){
stack.push(curr);
curr=curr.left;//向左走到尽头
}
if(!stack.isEmpty()){
temp=stack.peek();
//从左子树返回,需要判断它的右子树是否已经访问了
if(temp.flag==false){//右子树还未被访问的情况
temp.flag=true;
curr=temp.right;
}else{//右子树已经访问
temp=stack.pop();
System.out.println(temp.val);
}
}
}
}
上一篇: 树莓派,运行python+opencv+pyqt5编写的程序报错[g_object_new_with_properties: assertion ‘G_TYPE_IS_OBJECT (object_]
推荐阅读
-
Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】
-
Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
Python利用前序和中序遍历结果重建二叉树的方法
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
【算法】二叉树的前序、中序、后序、层序遍历和还原。
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例