递归实现二叉树的遍历
class BinaryTree{
public int value;
public BinaryTree left;
public BinaryTree right;
public BinaryTree(int data){
this.value = data;
}
//先序遍历二叉树
public void preOrderRecur(BinaryTree head){
if(head==null){
return;
}
System.out.println(head.value+" ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
//中序遍历二叉树
public void inOrderRecur(BinaryTree head){
if(head==null){
return;
}
inOrderRecur(head.left);
System.out.println(head.value+" ");
inOrderRecur(head.right);
}
//后序遍历二叉树
public void postOrderRecur(BinaryTree head){
if(head==null){
return;
}
postOrderRecur(head.left);
postOrderRecur(head.right);
System.out.println(head.value+" ");
}
}
用递归方法实现二叉树的遍历，那么也可以非递归来实现。递归方法是利用栈来保存信息的，栈是具有记忆功能的数据结构。我个人不怎么喜欢用递归，建议尽量不要用递归来解决问题。因为递归涉及到重复计算，还有当数据规模很大时就会导致内存溢出。下面介绍用非递归的方法来实现二叉树遍历。
1.非递归先序遍历二叉树
a.申请一个栈stack，将头结点head压入stack中；
b.从stack中弹出栈顶节点元素cur,然后打印节点元素的值，再将节点cur的右子树先压入stack中，最后将cur的左子树压入stack中，前提是左子树和右子树不为空
c.不断重复步骤b，一直到stack为空，全部过程结束
举例说明（这里要说明的是栈是后进先出，所以先是右子树进栈，然后再左子树进栈，这样就可以使左子树的元素先打印出来）
二叉树
第一步，1进栈，弹出来并打印，3进栈，2进栈（栈顶到栈底依次是2,3）
第二步，2弹出并打印，5进栈，4进栈（栈顶到栈底依次是4,5,3）
第三步，4弹出来并打印（栈顶到栈底依次是5,3）
第四步，5弹出来并打印（栈中只有3）
第五步，3弹出来并打印，7进栈，6进栈（栈顶到栈底依次是6,7）
第六步，6弹出并打印
第七步，7弹出并打印
非递归的先序遍历代码如下：
public void preOrderUnRecur(BinaryTree head){
System.out.println("非递归先序遍历：");
if(head!=null){
Stack<BinaryTree> stack = new Stack<BinaryTree>();
stack.add(head);
while(!stack.isEmpty()){
head = stack.pop();//头结点元素出栈
System.out.println(head.value+" ");
if(head.right!=null){
stack.push(head.right);
}
if(head.left!=null){
stack.push(head.left);
}
}
}
System.out.println();
}
就写到这里了，实验室要关门了，不往下写了。非递归的关键点就是要利用栈的性质，还有就是输出的结果跟元素进栈的顺序是相反的，这里还是栈的性质，非递归的中序遍历和后序遍历跟这差不多。希望各位前辈同仁指正！谢谢...
网友评论